When Numerical Analysis Crosses Paths with Catalan and Generalized Motzkin Numbers

Paul Eloe and Catherine Kublik Department of Mathematics University of Dayton 300 College Park Dayton, OH 45469 USA

                  peloe1@udayton.edu
                 ckublik1@udayton.edu

Abstract

We study a linear doubly indexed sequence that contains the Catalan numbers and relates to a class of generalized Motzkin numbers. We obtain a closed form formula, a generating function and a nonlinear recursion relation for this sequence. We show that a finite difference scheme with compact stencil applied to a nonlinear differential operator acting on the Euclidean distance function is exact, and exploit this exactness to produce the nonlinear recursion relation. In particular, the nonlinear recurrence relation is obtained by using standard error analysis techniques from numerical analysis. This work shows a connection between numerical analysis and number theory, and illustrates an interesting occurrence of the Catalan and generalized Motzkin numbers in a context a priori void of combinatorial objects.

1 Introduction

In this paper, we study the doubly indexed sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} defined by the recursion relation and initial conditions

\begin{cases}γ_{0}^{n} = 1, & ∀ n ≥ 0; \\ γ_{n}^{2n−1} = 0, & ∀ n ≥ 1; \\ γ_{k}^{n} = (1 + \frac{2k}{n+2}) γ_{k}^{n−1} + \frac{2k−n−1}{n+2}γ_{k−1}^{n−1}, & ∀ n ≥ 2, 1 ≤ k ≤ ⌊\frac{n}{2}⌋ . \end{cases}  (1)

We observe that the recursion relation is linear in γ_{k}^{n} and that (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} is uniquely determined by (1).

In this paper, we show that the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} is related to the well-known Catalan and Motzkin numbers via its closed form formula, and show that (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} also satisfies a nonlinear recursion relation. We obtain the nonlinear recursion relation by using a finite difference scheme which is exact when applied to a specific differential operator acting on the Euclidean distance function.

In the western world, the first appearance of the Catalan numbers dates back to Euler around 1751. At that time Euler was considering the problem of counting triangulations of convex n + 2-gons. With the help of Segner and Goldbach, Euler showed that for n ≥ 0, the number of triangulations of a convex n + 2-gon is

C_{n} = \frac{(2n)!}{n!(n + 1)!} = \frac{1}{n + 1}\binom{2n}{n}.

A major element in the proof was the recursion relation (also known as Segner’s relation)

C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k}, n ≥ 0,  (2)

satisfied by C_{n}, the number of triangulations of an n + 2-gon. Segner proved the relation via a combinatorial argument. They also discovered the generating function for the Catalan numbers

A(x) = ∑_{n=0}^{∞} C_{n}x^{n} = \frac{1 − \sqrt{1 − 4x}}{x}, |x| < \frac{1}{4}.

The Catalan number C_{n} is named after Catalan, a French and Belgian mathematician who studied this sequence and was the first to obtain what are now standard formulas

C_{n} = \frac{(2n)!}{n!(n + 1)!} = \binom{2n}{n} − \binom{2n}{n − 1}, n ≥ 0.

Many mathematicians have studied the Catalan numbers and there is now a very large literature on that topic. For example, in addition to the triangulation problem of Euler, there are now more than two hundred known combinatorial problems that are counted by the Catalan numbers. See Stanley [16] for this enumeration. There is also a very large literature on generalizations of the Catalan numbers. Some of the well-known generalizations of the Catalan numbers include the Fuss-Catalan numbers [7, 9, 10, 11, 15] and their generalizations [2, 8]. We finish by a remark. In 1730, Ming Antu, a Chinese scientist and mathematician wrote a book that included a number of trigonometric identities, some which involved the Catalan numbers. This was observed by J. J. Luo [12, 13] in 1988. This is the earliest known appearance of what we now call Catalan numbers.

The Motzkin numbers are connected to the Catalan numbers by

C_{n+1} = ∑_{k=0}^{n} \binom{n}{k}M_{k}, n ≥ 0,

and are defined as

M_{n} = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n}{2k}C_{k},  (3)

for n ≥ 0. The Motzkin numbers first appeared in the seminal article by Motzkin [14] in which Motzkin enumerated the number of partitions of 2n points on a circle into n pairs without crossings. Later, Donaghey and Shapiro [6] presented fourteen combinatorial objects enumerated by the Motzkin numbers. We also refer the reader to Aigner [1] for some of the properties of the Motzkin numbers and Bernhart [4] for their relation with the Catalan numbers. In related papers, Dattoli and co-authors [3, 5] have employed hybrid polynomials to study Motzkin numbers and their associated forms. In 2014, Sun [17] introduced a generalized Motzkin number M_{n}(a, b) depending on two additional integer parameters a and b, defined as

M_{n}(a, b) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n}{2k}C_{k}b^{k}a^{n−2k},  (4)

for n ≥ 0 and a, b ∈ ℤ. In particular, Sun showed that M_{n}(a, b) satisfies the linear recursion relation

\begin{cases}M_{0}(a, b) = 1, \\ M_{1}(a, b) = a, \\ (n + 3)M_{n+1}(a, b) = b(2n + 3)M_{n}(a, b) − (a^{2} − 4b)nM_{n−1}(a, b), & n ≥ 1, \end{cases}  (5)

which enabled him to obtain the generating function

M_{a,b}(x) = ∑_{n=0}^{∞} M_{n}(a, b)x^{n} = \frac{1 − ax − \sqrt{(1 − ax)^{2} − 4bx^{2}}}{2bx^{2}} .  (6)

We refer the reader to Wang et al. [18] and Zhao et al. [19] for some of the properties of these generalized Motztkin numbers.

Throughout the literature, the development of the Catalan numbers, the Motzkin numbers and their generalizations were primarily motivated by the process of enumerating combinatorial objects. The motivation in this paper is different, to our knowledge new, and represents the primary contribution of this manuscript. We apply a finite difference scheme with compact stencil to a nonlinear differential operator acting on a function of two variables. When the function of two variables is the Euclidean distance function, the application of the finite difference algorithm is exact and the sequence (1) is generated in a corresponding error analysis. To our knowledge, the observation of Catalan and Motzkin-like numbers in numerical analysis is new.

The paper is organized as follows. In Section 2 we give results on rising polynomials and Catalan numbers that are used later on in the paper. In Section 3 we establish the relationship between the two-dimensional Euclidean distance function and the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}. We obtain the closed form formula (exhibiting the Catalan numbers) for the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} in Section 4 and derive its nonlinear recursion relation in Section 5. We finish in Section 6 by presenting the generating function for (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}, and conclude in Section 7.

2 Preliminaries

In this section we discuss two results that are needed to preserve the completeness of the paper. The first result is the binomial theorem for special polynomials, called rising polynomials or Pochhammer symbols. The second result is the recursion relation for the Catalan numbers.

Definition 1 (Rising polynomial). For t, n ∈ ℝ, we define the rising polynomial t\overline{n} as

t\overline{n} = \frac{Γ(t + n)}{Γ(t)},

with the convention that if t is a nonpositive integer then t\overline{n} = 0, and if n = 0 then t\overline{0} = 1. If n is a positive integer then

t\overline{n} = t(t + 1) ⋯ (t + n − 1).

We note that t\overline{n} is also known as the Pochhammer symbol, denoted (t)_{n}. Also, just like the regular polynomial t^{n}, the rising polynomial t\overline{n} satisfies the binomial theorem.

Theorem 2 (Binomial theorem for rising polynomials). Assume n denotes a nonnegative integer and let a, b be real. Then

(a + b)\overline{n} = ∑_{k=0}^{n} \binom{n}{k}a\overline{k}b\overline{n−k}.  (7)

Proof. The proof is done by induction.

1. Consider the base case n = 0. Then (a + b)\overline{0} = 1 and ∑_{k=0}^{0} \binom{n}{k}a\overline{k}b\overline{n−k} = \binom{0}{0}a\overline{0}b\overline{0} = 1.

2. Assume n is a nonnegative integer and assume (7) is true. Then

(a + b)\overline{n+1} = (a + b + n)(a + b)\overline{n} = (a + b + n) ∑_{k=0}^{n} \binom{n}{k}a\overline{k}b\overline{n−k}

= ∑_{k=0}^{n} \binom{n}{k}(a + k)a\overline{k}b\overline{n−k} + ∑_{k=0}^{n} \binom{n}{k}a\overline{k}(b + n − k)b\overline{n−k}

= ∑_{k=0}^{n} \binom{n}{k}a\overline{k+1}b\overline{n−k} + ∑_{k=0}^{n} \binom{n}{k}a\overline{k}b\overline{n+1−k}

= a\overline{n+1} + ∑_{k=0}^{n−1} \binom{n}{k}a\overline{k+1}b\overline{n−k} + ∑_{k=1}^{n} \binom{n}{k}a\overline{k}b\overline{n+1−k} + b\overline{n+1}

= a\overline{n+1} + ∑_{k=1}^{n} \binom{n}{k − 1}a\overline{k}b\overline{n+1−k} + ∑_{k=1}^{n} \binom{n}{k}a\overline{k}b\overline{n+1−k} + b\overline{n+1}

= a\overline{n+1} + ∑_{k=1}^{n} (\binom{n}{k − 1} + \binom{n}{k}) a\overline{k}b\overline{n+1−k} + b\overline{n+1}

= ∑_{k=0}^{n+1} \binom{n + 1}{k}a\overline{k}b\overline{n+1−k}.

Thus (7) is true for n + 1 and therefore for all n ≥ 0. Theorem 3. For n ≥ 0, the n-th Catalan number is defined as

C_{n} = \frac{(2n)!}{n!(n + 1)!}.

Then (C_{n})_{n≥0} can be defined recursively as

\begin{cases}C_{0} = 1, \\ C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k}, & n ≥ 0. \end{cases}  (8)

Proof. We verify (8) by using the generating function for the Catalan numbers. Assume (v_{n})_{n≥0} denotes a sequence of real numbers satisfying (3), namely

v_{0} = 1, v_{n+1} = ∑_{k=0}^{n} v_{k}v_{n−k}.  (9)

Note that (v_{n})_{n≥0} is uniquely determined by the recursion (9).

Let

p(x) = ∑_{n=0}^{∞} v_{n}x^{n}

be the generating function for the sequence (v_{n})_{n≥0}. Employ (9) to obtain

xp^{2}(x) = x (∑_{n=0}^{∞} v_{n}x^{n})^{2} = x ∑_{n=0}^{∞} (∑_{k=0}^{n} v_{k}v_{n−k}) x^{n} = ∑_{n=0}^{∞} v_{n+1}x^{n+1} = p(x) − 1.

Thus p satisfies the quadratic equation

xp^{2}(x) − p(x) + 1 = 0.

In particular,

p(x) = \frac{1 − \sqrt{1 − 4x}}{2x} = ∑_{n=0}^{∞} \frac{(2n)!}{n!(n + 1)!}x^{n}, |x| < \frac{1}{4}.

Thus, since (v_{n})_{n≥0} is unique, we obtain that

v_{n} = \frac{(2n)!}{n!(n + 1)!} = C_{n},

and thus (8) holds.

3 Distance function and the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}

In this section we show that the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} naturally arises in the derivatives of the two-dimensional Euclidean distance function to a fixed point. Indeed, let (x_{0}, y_{0}) ∈ ℝ^{2}. We define d : ℝ^{2} → ℝ^{+} to be the Euclidean distance from any point x = (x, y) ∈ ℝ^{2} to the point (x_{0}, y_{0}), namely

d(x) = d(x, y) = \sqrt{(x − x_{0})^{2} + (y − y_{0})^{2}}.

Without loss of generality, we take x_{0} = y_{0} = 0 and consider the distance function to the origin

d(x) = d(x, y) = \sqrt{x^{2} + y^{2}}.  (10)

We define the quantities

X := x^{2},  (11)
Y := y^{2},  (12)

and

D := X + Y.  (13)

It follows that the distance d defined in (10) can be written as

d = D^{\frac{1}{2}} ,  (14)

and that

D_{x} = 2x, D_{y} = 2y, and D_{xx} = D_{yy} = 2.  (15)

Definition 4. For m ∈ ℕ_{0}, we define the homogeneous polynomials of degree m in X and Y, P_{m}^{2m+2} and P_{m}^{2m+3}, as

P_{m}^{2m+2}(X, Y) = ∑_{k=0}^{m} γ_{k}^{2m}Y^{k}X^{m−k},

and

P_{m}^{2m+3}(X, Y) = ∑_{k=0}^{m} γ_{k}^{2m+1}Y^{k}X^{m−k},

where (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} is defined in (1).

Note that the two polynomials P_{m}^{2m+2} and P_{m}^{2m+3} can be defined by the single equation

P⌊\frac{n}{2}⌋^{n+2}(X, Y) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} γ_{k}^{n}Y^{k}X^{⌊^{\frac{n}{2}}⌋−k}.

for n ≥ 0 and (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} as defined in (1).

The following theorem establishes the connection between the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} and the higher order derivatives of the distance function d defined in (10).

Theorem 5. Let d be the distance function defined in (10). Then for m ≥ 0, the partial derivatives of d with respect to x can be written as

\frac{∂^{(2m+2)}d}{∂x^{2m+2}} = \frac{(2m + 2)!}{2}Y D^{− \frac{4m+3}{2}} P_{m}^{2m+2}(X, Y),  (16)

\frac{∂^{(2m+3)}d}{∂x^{2m+3}} = −\frac{(2m + 3)!}{2}xY D^{− \frac{4m+5}{2}} P_{m}^{2m+3}(X, Y),  (17)

where P_{m}^{2m+2} and P_{m}^{2m+3} are defined in Definition 4 and (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} is defined in (1). Similarly, the partial derivatives of d with respect to y can be written as

\frac{∂^{(2m+2)}d}{∂y^{2m+2}} = \frac{(2m + 2)!}{2}XD^{− \frac{4m+3}{2}} P_{m}^{2m+2}(Y, X),

and

\frac{∂^{(2m+3)}d}{∂y^{2m+3}} = −\frac{(2m + 3)!}{2}yXD^{− \frac{4m+5}{2}} P_{m}^{2m+3}(Y, X).

Proof. The proof is done by induction.

First, we remark that since d is symmetric in x and y (and hence in X and Y), the derivatives of d with respect to y can be obtained from the derivatives of d with respect to x by simply interchanging the roles of x and y (and hence X and Y). Thus we only prove the formulas for the partial derivatives of d with respect to x.

1. Consider the base case m = 0.

d_{xx} = (D^{\frac{1}{2}} )_{xx} = \frac{1}{2} (D^{− \frac{1}{2}} D_{x})_{x} = \frac{1}{2} (−\frac{1}{2}D^{− \frac{3}{2}} \underbrace{D_{x}^{2}}_{=4X} +D^{− \frac{1}{2}} \underbrace{D_{xx}}_{=2})

= D^{− \frac{3}{2}} (D − X) = Y D^{− \frac{3}{2}} = \frac{(2)!}{2}Y D^{− \frac{3}{2}} γ_{0}^{0}X^{1−1},

where γ_{0}^{0} = 1.
d_{xxx} = \underbrace{Y_{x}}_{=0} D^{− \frac{3}{2}} − \frac{3}{2}Y D^{− \frac{5}{2}} \underbrace{D_{x}}_{=2x} = −3xY D^{− \frac{5}{2}}

= −\frac{3!}{2}xY D^{− \frac{4(1)+1}{2}} γ_{0}^{1}X^{1−1},

with γ_{0}^{1} = 1.

2. For the induction hypothesis, assume (16) and (17) both hold for m ≥ 0. Then for m + 1 ≥ 0 we have

\frac{∂^{(2m+4)}d}{∂x^{2m+4}} = \frac{∂}{∂x} (\frac{∂^{(2m+3)}d}{∂x^{2m+3}})

= −\frac{(2m + 3)!}{2}Y (xD^{− \frac{4m+5}{2}} P_{m}^{2m+3})_{x}

= −\frac{(2m + 3)!}{2}Y (\frac{∂}{∂x} (xD^{− \frac{4m+5}{2}} ) P_{m}^{2m+3} + xD^{− \frac{4m+5}{2}} (P_{m}^{2m+3})_{x}) .

By using Equations (11), (12), (13), and (15) we can calculate the product rule above as follows:

(xD^{− \frac{4m+5}{2}} ) P_{m}^{2m+3} + xD^{− \frac{4m+5}{2}} (P_{m}^{2m+3})_{x}

= D^{− \frac{4m+7}{2}} (D − (4m + 5)x^{2}) P_{m}^{2m+3}

+ xD^{− \frac{4m+7}{2}} D ∑_{k=0}^{m} γ_{k}^{2m+1}(m − k)Y^{k}X^{m−k−1}X_{x}

= D^{− \frac{4m+7}{2}} (X + Y − (4m + 5)X) P_{m}^{2m+3}

+ 2X(X + Y)D^{− \frac{4m+7}{2}} ∑_{k=0}^{m} γ_{k}^{2m+1}(m − k)Y^{k}X^{m−k−1}

= D^{− \frac{4m+7}{2}} E,

where

E = (Y − 4(m + 1)X)P_{m}^{2m+3} + 2X(X + Y) ∑_{k=0}^{m} γ_{k}^{2m+1}(m − k)Y^{k}X^{m−1−k}.

Note that

E = ∑_{k=0}^{m} (1 + 2(m − k)) γ_{k}^{2m+1}Y^{k+1}X^{m−k}

+ ∑_{k=0}^{m} (2(m − k) − 4(m + 1)) γ_{k}^{2m+1}Y^{k}X^{m+1−k}

= ∑_{k=1}^{m+1} (2m + 3 − 2k) γ_{k−1}^{2m+1}Y^{k}X^{m+1−k} − 2 ∑_{k=0}^{m} (k + 2 + m) γ_{k}^{2m+1}Y^{k}X^{m+1−k}

= γ_{m}^{2m+1}Y^{m+1} − 2(m + 2)γ_{0}^{2m+1}X^{m+1}

+ ∑_{k=1}^{m} ((2m + 3 − 2k) γ_{k−1}^{2m+1} − 2 (k + 2 + m) γ_{k}^{2m+1}) Y^{k}X^{m+1−k}.

Thus we can write

\frac{∂^{(2m+4)}d}{∂x^{2m+4}} = −\frac{(2m + 3)!}{2}Y D^{− \frac{4m+7}{2}} E

= \frac{(2m + 4)!}{2}Y D^{− \frac{4m+7}{2}} \frac{−E}{2m + 4},

where

\frac{−E}{2m + 4} = \underbrace{γ_{0}^{2m+1}}_{=1} X^{m+1} + ∑_{k=1}^{m} (2\frac{k + 2 + m}{2m + 4}γ_{k}^{2m+1} − \frac{2m + 3 − 2k}{2m + 4} γ_{k−1}^{2m+1}) Y^{k}X^{m+1−k}

− \frac{γ_{m}^{2m+1}}{2m + 4}Y^{m+1}

= X^{m+1} + ∑_{k=1}^{m} ((1 + \frac{2k}{2m + 4}) γ_{k}^{2m+1} + \frac{2k − 2m − 3}{2m + 4}γ_{k−1}^{2m+1}) Y^{k}X^{m+1−k}

− \frac{γ_{m}^{2m+1}}{2m + 4}Y^{m+1}

= ∑_{k=0}^{m+1} γ_{k}^{2m+2}Y^{k}X^{m+1−k},

where for m ≥ 0 we have

\begin{cases}γ_{0}^{2m+2} = 1, \\ γ_{m+1}^{2m+2} = −\frac{1}{2m+4}γ_{m}^{2m+1}, \\ γ_{k}^{2m+2} = (1 + \frac{2k}{2m+4}) γ_{k}^{2m+1} + \frac{2k−2m−3}{2m+4}γ_{k−1}^{2m+1}, & for 1 ≤ k ≤ m. \end{cases}

By definition, γ_{m+1}^{2m+1} = 0 for any m ≥ 0; thus

γ_{k}^{2m+2} = (1 + \frac{2k}{2m + 4}) γ_{k}^{2m+1} + \frac{2k − 2m − 3}{2m + 4}γ_{k−1}^{2m+1} for 1 ≤ k ≤ m,  (18)

is still true for k = m + 1 and reduces to

γ_{m+1}^{2m+2} = −\frac{1}{2m + 4}γ_{m}^{2m+1}.

Recognizing (18) as the recursion relation for the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} for an even index n, it follows that (16) is true for m + 1 and thus is true for all m ≥ 0. Similarly, we can show Equation (17) for m + 1 ≥ 0, namely

\frac{∂^{(2m+5)}d}{∂x^{2m+5}} = \frac{(2m + 5)!}{2}Y xD^{− \frac{4m+9}{2}} ∑_{k=0}^{m+1} γ_{k}^{2m+3}Y^{k}X^{m+1−k}

with for m ≥ 0,

\begin{cases}γ_{0}^{2m+3} = 1, \\ γ_{k}^{2m+3} = ((1 + \frac{2k}{2m+3})γ_{k}^{2m+2} + \frac{2k−2m−4}{2m+3}γ_{k−1}^{2m+2}) , & for 1 ≤ k ≤ m + 1, \end{cases}  (19)

Recognizing the recursion relation for the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} for an odd index n, it follows that (17) is true for m + 1 and thus is true for all m ≥ 0.

We will exploit the relationship between the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} and the derivatives of the distance function to prove that (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} also satisfies a nonlinear recursion relation. This will be done by employing a finite difference scheme on ∇ · (d∇d), where d is the Euclidean distance function defined in (10).

4 Closed form formula for (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}

In this section, we obtain a closed form formula for the general term of the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}.

Theorem 6. Let (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} be defined by the recursion relation and initial conditions given in (1). Then the general term of the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} is

γ_{k}^{n} = (−\frac{1}{4})^{k} \binom{n}{2k}C_{k},

where C_{k} = \frac{(2k)!}{k!(k + 1)!} = \frac{1}{k + 1}\binom{2k}{k} for k ≥ 0, is the k-th Catalan number.

Remark 7. Observe that n ≥ 0, 0 ≤ k ≤ ⌊\frac{n}{2}⌋ is equivalent to k ≥ 0, n ≥ 2k. Thus, the binomial coefficient \binom{n}{2k} represents the number of ways 2k objects (and 2k ≤ n) can be

taken from a set of n objects. In the case 2k > n, we define \binom{n}{2k} to be 0.

Remark 8. Note that the term \binom{n}{2k}C_{k} can be recognized as the summand of the Motzkin number M_{n} defined in (3).

Proof. Define

u_{k}^{n} := (−\frac{1}{4})^{k} \binom{n}{2k}C_{k}, n ≥ 0, 0 ≤ k ≤ ⌊\frac{n}{2}⌋ .

We will show that the sequence (u_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} coincides with the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}.

1. Let’s first calculate u_{0}^{n} for all n ≥ 0 and u_{n}^{2n−1} for all n ≥ 1.

For n ≥ 0, we have

u_{0}^{n} = (−\frac{1}{4})^{0} \binom{n}{0}C_{0} = 1.

For n ≥ 1, we have

u_{n}^{2n−1} = (−\frac{1}{4})^{n} \underbrace{\binom{2n − 1}{2n}}_{=0} C_{n} = 0.

Thus we have

\begin{cases}u_{0}^{n} = 1, & ∀ n ≥ 0; \\ u_{n}^{2n−1} = 0, & ∀ n ≥ 1. \end{cases}

2. Suppose n ≥ 2 and 1 ≤ k ≤ ⌊\frac{n}{2}⌋. Then we have

(1 + \frac{2k}{n + 2}) u_{k}^{n−1} + \frac{2k − n − 1}{n + 2}u_{k−1}^{n−1}

= (−\frac{1}{4})^{k} (\frac{n + 2 + 2k}{n + 2} \binom{n − 1}{2k}C_{k} + 4\frac{n + 1 − 2k}{n + 2} \binom{n − 1}{2k − 2}C_{k−1}) .

Using the definition of the Catalan numbers we can write

C_{k−1} = \frac{k + 1}{2(2k − 1)}C_{k}, k ≥ 1.

Similarly, using the definition of the binomial coefficients, we can write

\binom{n − 1}{2k} = \frac{n − 2k}{n} \binom{n}{2k}, n ≥ 2, 1 ≤ k ≤ ⌊\frac{n}{2}⌋ ,

and

\binom{n − 1}{2k − 2} = \frac{2k(2k − 1)}{n(n + 1 − 2k)}\binom{n}{2k}, n ≥ 2, 1 ≤ k ≤ ⌊\frac{n}{2}⌋ .

Consequently,

(1 + \frac{2k}{n + 2}) u_{k}^{n−1} + \frac{2k − n − 1}{n + 2}u_{k−1}^{n−1}

= (−\frac{1}{4})^{k} (\frac{n + 2 + 2k}{n + 2} \frac{n − 2k}{n} \binom{n}{2k}C_{k} + 4\frac{n + 1 − 2k}{n + 2} \frac{2k(2k − 1)}{n(n + 1 − 2k)}\binom{n}{2k}\frac{k + 1}{2(2k − 1)}C_{k})

= (−\frac{1}{4})^{k} \binom{n}{2k}C_{k} \underbrace{\frac{(n + 2 − 2k)(n − 2k) + 4k(k + 1)}{n(n + 2)}}_{=1}

= (−\frac{1}{4})^{k} \binom{n}{2k}C_{k} = u_{k}^{n}.

Remark 9. The calculations above include the case n = 2m and k = m. Note that in this case, we have \binom{n − 1}{2k} = \binom{2m − 1}{2m} = 0, but the calculations above still hold in

that case since

(1 + \frac{2k}{n + 2}) u_{k}^{n−1} + \frac{2k − n − 1}{n + 2}u_{k−1}^{n−1} = (−\frac{1}{4})^{k} \binom{n}{2k}C_{k} \frac{4k(k + 1)}{n(n + 2)}

= (−\frac{1}{4})^{k} \binom{n}{2k}C_{k} \frac{4m(m + 1)}{2m(2m + 2)}

= (−\frac{1}{4})^{k} \binom{n}{2k}C_{k}.

This shows that the sequence (u_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} satisfies

\begin{cases}u_{0}^{n} = 1, & ∀ n ≥ 0; \\ u_{n}^{2n−1} = 0, & ∀ n ≥ 1; \\ u_{k}^{n} = (1 + \frac{2k}{n+2}) γ_{k}^{n−1} + \frac{2k−n−1}{n+2}γ_{k−1}^{n−1}, & ∀ n ≥ 2, 1 ≤ k ≤ ⌊\frac{n}{2}⌋ , \end{cases}

which is the recursion and initial conditions for (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} defined by (1). Since (1) defines a unique sequence, it follows that the sequence (u_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} is the same

as the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}. Thus for all n ≥ 0 and 0 ≤ k ≤ ⌊\frac{n}{2}⌋,

γ_{k}^{n} = (−\frac{1}{4})^{k} \binom{n}{2k}C_{k}.

5 Nonlinear recursion relation for (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}

In this section we obtain a nonlinear recursion relation for the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} by using its relationship with the partial derivatives of the two-dimensional distance function. Specifically, we introduce a numerical scheme and apply it to ∇ · (d∇d), where d is the distance function defined in (10). We will show that the scheme is exact on (∇ · (d∇d)) (x, y) (as long as (x, y) ≠ (0, 0)) which will enable us to obtain the nonlinear recursion relation for (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}.

5.1 Two-dimensional finite difference scheme

In this section we introduce a finite difference scheme for discretizing the differential operator ∇ · (f∇f) where f is a C^{∞} function on ℝ^{2} except possibly at finitely many points in ℝ^{2}. Let α < β and assume (0, 0) ∉ [α, β]^{2}. Assume N ∈ ℕ. We consider the uniform discretization of [α, β]^{2}, where h = \frac{β−α}{N} is the grid size in each of the coordinate directions. Then for a grid point (x_{i}, y_{j}), 0 ≤ i, j ≤ N, and a C^{∞} function f defined on [α, β]^{2}, we define the forward difference operator in x as

D_{+}^{x} (f_{i,j}) := \frac{f(x_{i+1}, y_{j}) − f(x_{i}, y_{j})}{h} = \frac{f(x_{i} + h, y_{j}) − f(x_{i}, y_{j})}{h},

and the forward difference operator in y as

D_{+}^{y} (f_{i,j}) := \frac{f(x_{i}, y_{j+1}) − f(x_{i}, y_{j})}{h} = \frac{f(x_{i}, y_{j} + h) − f(x_{i}, y_{j})}{h}.

Similarly, we define the backward difference operator in x as

D_{−}^{x} (f_{i,j}) := \frac{f(x_{i}, y_{j}) − f(x_{i−1}, y_{j})}{h} = \frac{f(x_{i}, y_{j}) − f(x_{i} − h, y_{j})}{h},

and the backward difference operator in y as

D_{−}^{x} (f_{i,j}) := \frac{f(x_{i}, y_{j}) − f(x_{i}, y_{j−1})}{h} = \frac{f(x_{i}, y_{j}) − f(x_{i}, y_{j} − h)}{h}.

We now define

f_{i− \frac{1}{2} ,j} := \frac{1}{2} (f_{i−1,j} + f_{i,j}) ,

and

f_{i,j− \frac{1}{2}} := \frac{1}{2} (f_{i,j} + f_{i,j−1}) ,

and construct the numerical scheme

D_{+}^{x} (f_{i− \frac{1}{2} ,j}D_{−}^{x}(f_{i,j})) + D_{+}^{y} (f_{i,j− \frac{1}{2}} D_{−}^{y}(f_{i,j})) .  (20)

This scheme (20) is a discretized version of ∇ · (f∇f). We note that this scheme uses a compact stencil in the sense that the stencil used is the smallest stencil on which we can construct a second order convergent discretization scheme for the differential operator ∇·(f∇f). Indeed, for a smooth function f, we can show that this numerical scheme is second order. However, with the choice f = d, this discretization coincides with its non-discretized version ∇ · (d∇d). Now in the case of the distance function, the scalar (∇ · (d∇d)) (x, y) can be calculated to be 2 at every point (x, y) ≠ (0, 0).

Theorem 10. Let d be the distance function defined in (10). Choose [α, β]^{2} such that (0, 0) ∉ [α, β]^{2} and discretize [α, β]^{2} uniformly with grid spacing h = \frac{β−α}{N} in each coordinate direction. Then

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) + D_{+}^{y} (d_{i,j− \frac{1}{2}} D_{−}^{y}(d_{i,j})) = 2.

Proof. We prove that D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) = 1. Since the distance function d and the

numerical scheme are symmetric in x and y, we can obtain D_{+}^{y} (d_{i,j− \frac{1}{2}} D_{−}^{y}(d_{i,j})) = 1 by interchanging the roles of x and y.

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) = D_{+}^{x} (\frac{d_{i,j} + d_{i−1,j}}{2} \frac{d_{i,j} − d_{i−1,j}}{h} )

= \frac{1}{2h}D_{+}^{x} (d_{i,j}^{2} − d_{i−1,j}^{2})

= \frac{1}{2h^{2}} (d_{i+1,j}^{2} − d_{i,j}^{2} − d_{i,j}^{2} + d_{i−1,j}^{2})

= \frac{d_{i+1,j}^{2} − 2d_{i,j}^{2} + d_{i−1,j}^{2}}{2h^{2}} .

Now recall that

d_{i,j}^{2} = x_{i}^{2} + y_{j}^{2},
d_{i+1,j}^{2} = x_{i+1}^{2} + y_{j}^{2} = (x_{i} + h)^{2} + y_{j}^{2}

and

d_{i−1,j}^{2} = x_{i−1}^{2} + y_{j}^{2} = (x_{i} − h)^{2} + y_{j}^{2}.

Thus,

d_{i+1,j}^{2} − 2d_{i,j}^{2} + d_{i−1,j}^{2} = (x_{i} + h)^{2} + y_{j}^{2} − 2x_{i}^{2} − 2y_{j}^{2} + (x_{i} − h)^{2} + y_{j}^{2}
= x_{i}^{2} − 2hx_{i} + h^{2} − 2x_{i}^{2} + x_{i}^{2} − 2hx_{i} + h^{2}
= 2h^{2}.

Consequently, we obtain

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) = \frac{d_{i+1,j}^{2} − 2d_{i,j}^{2} + d_{i−1,j}^{2}}{2h^{2}} = 1.

Remark 11. Since the proof of Theorem 10 is done coordinate-wise, it follows that the result still holds if we use a different grid spacing in each coordinate direction. In other words, as long as the discretization is uniform in each coordinate direction, it is not necessary to take the same grid spacing.

5.2 Nonlinear recursion relation

In this section, we obtain the nonlinear recursion relation for (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}.

Theorem 12. Let (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} be defined by the recursion relation and initial conditions given in (1). Then the sequence satisfies the nonlinear recursion relation

\begin{cases}γ_{0}^{n} = 1, & ∀ n ≥ 0; \\ γ_{n}^{2n−1} = 0, & ∀ n ≥ 1; \\ γ_{k}^{n} = γ_{k}^{n−1} − \frac{1}{4} ∑_{i=0}^{k−1} ∑_{j=2i}^{n+2(i−k)} γ_{i}^{j}γ_{k−i−1}^{n−2−j}, & ∀ n ≥ 2, 1 ≤ k ≤ ⌊\frac{n}{2}⌋ . \end{cases}  (21)

For the sake of clarity, we shall first prove several lemmas, which will then be employed to obtain the result of Theorem 12.

Let’s first start with a brief discussion of our method. The basic idea is very simple and comes from standard numerical analysis techniques. In numerical analysis, it is important to obtain the convergence rate of a specific numerical scheme, namely we would like to know how fast the finite difference approximation converges to the true solution as the grid size h decreases to 0. In other words, we want to obtain a relation of the type

Finite Difference Scheme = True Solution + O(h^{p}),  (22)

where h is the grid spacing in each coordinate direction (assumed to be the same in each coordinate direction here) and p ∈ ℕ. p is called the order of convergence of the scheme. The higher p is, the more accurate the scheme is, since it converges faster to the true solution. To obtain such a relation, the standard procedure in numerical analysis is to use Taylor expansion for the finite difference scheme.

We do the same with our finite difference scheme and note that in our case (22) is valid for all p ∈ ℕ. Using a Taylor expansion, we write the finite difference scheme as a power series in h, knowing that all the coefficients are zero except for the constant term (since the scheme is exact by Theorem 10). Using the general term for the sequence of coefficients and setting it to zero will give us the nonlinear recursion.

We note that it suffices to consider D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) to obtain the nonlinear recursion relation. Thus from now on, we only consider the finite difference in x

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) .

since an analysis of D_{+}^{y} (f_{i,j− \frac{1}{2}} D_{−}^{y}(f_{i,j})) generates the same nonlinear recursion relation. For the sake of clarity, we introduce some notation.

Definition 13. For d defined in (10), we define the sequences of functions (p_{k}(x, y))_{k≥0} and (q_{k}(x, y))_{k≥0} as

p_{k}(x, y) := \begin{cases}d, & if k = 0; \\ \frac{(−1)^{k}}{2k!} \frac{∂^{(k)}d}{∂x^{k}}, & if k ∈ ℕ, \end{cases}

and

q_{k}(x, y) := \frac{(−1)^{k}}{(k + 1)!} \frac{∂^{(k+1)}d}{∂x^{k+1}}, for k ∈ ℕ_{0}.

Note that we dropped the dependence on x and y in d above. From now on, if the dependence on x and y is clear from context we will not write it. Definition 14. We define, for an integer i ≥ 0,

S_{i} := ∑_{ℓ=0}^{i} p_{ℓ}q_{i−ℓ},

where (p_{k}(x, y))_{k≥0} and (q_{k}(x, y))_{k≥0} are defined in Definition 13.

We are now ready to state our first lemma. Lemma 15. Let d be the distance function defined in (10). Then we have

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) = ∑_{n=0}^{∞} a_{n}h^{n},  (23)

where

a_{n} = ∑_{k=0}^{n} \frac{1}{(n − k + 1)!} \frac{∂^{(n−k+1)}S_{k}}{∂x^{n−k+1}} ,  (24)

with S_{k} defined in Definition 14. Proof. Let (x_{i}, y_{j}) be any point in [α, β]^{2} such that (0, 0) ∉ [α, β]^{2}. Since d is C^{∞} in a neighborhood of (x_{i}, y_{j}) ≠ (0, 0), we can expand D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) with Taylor series expansions. For simplicity in the exposition, we drop the argument (x_{i}, y_{j}) from the distance function d. It is thus assumed that the distance function d and any of its derivatives are evaluated at the grid node (x_{i}, y_{j}).

D_{−}^{x}(d_{i,j}) = \frac{d_{i,j} − d_{i−1,j}}{h} = \frac{d(x_{i}, y_{j}) − d(x_{i} − h, y_{j})}{h}

= \frac{1}{h} (d(x_{i}, y_{j}) − (d(x_{i}, y_{j}) + ∑_{k=1}^{∞} \frac{1}{k!} \frac{∂^{(k)}d}{∂x^{k}}(−1)^{k}h^{k}))

= ∑_{k=1}^{∞} \frac{(−1)^{k−1}h^{k−1}}{k!} \frac{∂^{(k)}d}{∂x^{k}}

= ∑_{k=0}^{∞} \frac{(−1)^{k}}{(k + 1)!} \frac{∂^{(k+1)}d}{∂x^{k+1}}h^{k}

= ∑_{k=0}^{∞} q_{k}h^{k},

by Definition 13. Now

d_{i− \frac{1}{2} ,j} = \frac{1}{2} (d_{i,j} + d_{i−1,j})

= \frac{1}{2} (d_{i,j} + d_{i,j} + ∑_{k=1}^{∞} \frac{(−1)^{k}h^{k}}{k!} \frac{∂^{(k)}d}{∂x^{k}}(x_{i}, y_{j}))

= d_{i,j} + \frac{1}{2} ∑_{k=1}^{∞} \frac{(−1)^{k}h^{k}}{k!} \frac{∂^{(k)}d}{∂x^{k}}

= ∑_{k=0}^{∞} p_{k}h^{k},

by Definition 13 again. Applying the Cauchy product, we obtain

d_{i− \frac{1}{2} ,j}D_{−}^{x}(d) = ∑_{k=0}^{∞} (∑_{ℓ=0}^{k} p_{ℓ}q_{k−ℓ}) h^{k} = ∑_{k=0}^{∞} S_{k}h^{k},

using Definition 14. Now since the Taylor series expansion of the forward difference D_{+}^{x} of a function f at (x_{i}, j_{j}) is

∑_{m=0}^{∞} \frac{1}{(m + 1)!} \frac{∂^{(m+1)}f}{∂x^{m+1}} h^{m},

we can write

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d)) = ∑_{m=0}^{∞} \frac{1}{(m + 1)!} ∑_{k=0}^{∞} \frac{∂^{(m+1)}S_{k}}{∂x^{m+1}} h^{k+m}.

Changing variables in the above sum, we obtain

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d)) = ∑_{m+k=n,n≥0} \frac{1}{(m + 1)!} \frac{∂^{(m+1)}S_{k}}{∂x^{m+1}} h^{n}

= ∑_{n=0}^{∞} \underbrace{∑_{k=0}^{n} \frac{1}{(n − k + 1)!} \frac{∂^{(n−k+1)}S_{k}}{∂x^{n−k+1}}}_{=a_{n}} h^{n}

= ∑_{n=0}^{∞} a_{n}h^{n}.

Lemma 16. We have

p_{2m} = \begin{cases}D^{\frac{1}{2}} , & if m = 0; \\ \frac{1}{4}Y D^{− \frac{4m−1}{2}} P_{m−1}^{2m}(X, Y), & if m ≥ 1. \end{cases}

p_{2m+1} = \begin{cases}−\frac{1}{2}D^{− \frac{1}{2}} x, & if m = 0; \\ \frac{1}{4}xY D^{− \frac{4m+1}{2}} P_{m−1}^{2m+1}(X, Y), & if m ≥ 1. \end{cases}

q_{2m} = \begin{cases}D^{− \frac{1}{2}} x, & if m = 0; \\ −\frac{1}{2}xY D^{− \frac{4m+1}{2}} P_{m−1}^{2m+1}(X, Y), & if m ≥ 1. \end{cases}

q_{2m−1} = −\frac{1}{2}Y D^{− \frac{4m−1}{2}} P_{m−1}^{2m}(X, Y), if m ≥ 1.

Proof. These relations are consequences of combining Definition 13 and the result of Theorem 5. Lemma 17. For p, q defined in Definition 13, we have

p_{2k}q_{2m−2k} = \begin{cases}−\frac{1}{2}xY D^{−2m}P_{m−1}^{2m+1}, & k = 0, m ≥ 1; \\ −\frac{1}{2}xY D^{−2m} (\frac{1}{4}Y P_{k−1}^{2k}P_{m−k−1}^{2m−2k+1}) , & k ≥ 1, m ≥ k + 1. \end{cases}

p_{2k+1}q_{2m−2k−1} = \begin{cases}−\frac{1}{2}xY D^{−2m} (−\frac{1}{2}P_{m−1}^{2m}) , & k = 0, m ≥ 1; \\ −\frac{1}{2}xY D^{−2m} (\frac{1}{4}Y P_{k−1}^{2k+1}P_{m−k−1}^{2m−2k}) , & k ≥ 1, m ≥ k + 1. \end{cases}

p_{2k}q_{2m+1−2k} = \begin{cases}−\frac{1}{2}Y D^{−(2m+1)}P_{m}^{2m+2}, & k = 0, m ≥ 0; \\ −\frac{1}{2}Y D^{−(2m+1)} (\frac{1}{4}Y P_{k−1}^{2k}P_{m−k}^{2(m−k+1)}) , & k ≥ 1, m ≥ k. \end{cases}

p_{2k+1}q_{2m−2k} = \begin{cases}−\frac{1}{2}Y D^{−(2m+1)} (−\frac{1}{2}XP_{m−1}^{2m+1}) , & k = 0, m ≥ 1; \\ −\frac{1}{2}Y D^{−(2m+1)} (\frac{1}{4}XY P_{k−1}^{2k+1}P_{m−k−1}^{2(m−k)+1}) , & k ≥ 1, m ≥ k + 1. \end{cases}

Proof. These relations are consequences of Lemma 16. Lemma 18. For ℓ ≥ 1,k ≥ ℓ, we have

p_{ℓ}q_{k−ℓ} = p_{k−ℓ+1}q_{ℓ−1}.  (25)

Proof. Suppose ℓ ≥ 1,k ≥ ℓ. Then

p_{ℓ}q_{k−ℓ} = \frac{(−1)^{ℓ}}{2ℓ!} \frac{∂^{(ℓ)}d}{∂x^{ℓ}} \frac{(−1)^{(k−ℓ)}}{(k − ℓ + 1)!} \frac{∂^{(k−ℓ+1)}d}{∂x^{k−ℓ+1}}

= \frac{(−1)^{k}}{2ℓ!(k − ℓ + 1)!} \frac{∂^{(ℓ)}d}{∂x^{ℓ}} \frac{∂^{(k−ℓ+1)}d}{∂x^{k−ℓ+1}}.

Thus

p_{k−ℓ+1}q_{ℓ−1} = \frac{(−1)^{k−ℓ+1}}{2(k − ℓ + 1)!} \frac{∂^{(k−ℓ+1)}d}{∂x^{k−ℓ+1}} \frac{(−1)^{ℓ−1}}{ℓ!} \frac{∂^{ℓ}d}{∂x^{ℓ}}

= \frac{(−1)^{k}}{2ℓ!(k − ℓ + 1)!} \frac{∂^{ℓ}d}{∂x^{ℓ}} \frac{∂^{(k−ℓ+1)}d}{∂x^{k−ℓ+1}}

= p_{ℓ}q_{k−ℓ}.

Lemma 19. For m ≥ 0,

S_{2m+2} = (−\frac{1}{2}xY D^{−(2m+2)}) A_{m},

where A_{m} is a homogeneous polynomial of degree m in X and Y. Similarly for m ≥ 0,

S_{2m+3} = (−\frac{1}{2}Y D^{−(2m+3)}) B_{m+1},

where B_{m+1} is a homogeneous polynomial of degree m + 1 in X and Y. In addition, we have the following:

• The coefficient of X^{m} in A_{m} is

γ_{0}^{2m+1} − γ_{0}^{2m}.

• The coefficient of Y^{n}X^{m−n} in A_{m}, for 1 ≤ n ≤ m is

γ_{n}^{2m+1} − γ_{n}^{2m} + \frac{1}{4} ∑_{k=0}^{n−1} ∑_{j=2k}^{2m+1+2(k−n)} γ_{k}^{j}γ_{n−k−1}^{2m−1−j}.

• The coefficient of X^{m+1} in B_{m+1} is

γ_{0}^{2m+2} − γ_{0}^{2m+1}.

• The coefficient of Y^{n}X^{m+1−n} in B_{m+1}, for 1 ≤ n ≤ m is

γ_{n}^{2m+2} − γ_{n}^{2m+1} + \frac{1}{4} ∑_{k=0}^{n−1} ∑_{j=2k}^{2m+2+2(k−n)} γ_{k}^{j}γ_{n−k−1}^{2m−j}.

• The coefficient of Y^{m+1} in B_{m+1} is

γ_{m+1}^{2m+2} + \frac{1}{4} ∑_{k=0}^{m} γ_{k}^{2k}γ_{m−k}^{2(m−k)}.

Proof. Let m ≥ 0. We shall show the proof for S_{2m+3}. The argument is similar (and slightly simpler) for S_{2m+2}.

Using Definition 14, the symmetry stated in Lemma 18 and the result of Lemma 17, we can write

S_{2m+3} = p_{0}q_{2m+3} + 2p_{1}q_{2m+2} + ∑_{ℓ=2}^{2m+2} p_{ℓ}q_{2m+3−ℓ}

= p_{0}q_{2m+3} + 2p_{1}q_{2m+2} + ∑_{j=1}^{m+1} p_{2j}q_{2m+3−2j} + ∑_{j=1}^{m} p_{2j+1}q_{2m+2−2j}

= (\frac{−1}{2}Y D^{−(2m+3)}) B_{m+1},

where

B_{m+1} = (P_{m+1}^{2m+4} − XP_{m}^{2m+3} + \frac{Y}{4} ∑_{j=1}^{m+1} P_{j−1}^{2j}P_{m+1−j}^{2m−2j+4} + \frac{XY}{4} ∑_{j=1}^{m} P_{j−1}^{2j+1}P_{m−j}^{2m−2j+3})

= ∑_{n=0}^{m+1} γ_{n}^{2m+2}Y^{n}X^{m+1−n} − X ∑_{n=0}^{m} γ_{n}^{2m+1}Y^{n}X^{m−n}

+ \frac{Y}{4} ∑_{j=1}^{m+1} (∑_{k=0}^{j−1} γ_{k}^{2j−2}Y^{k}X^{j−1−k}) ( ∑_{i=0}^{m+1−j} γ_{i}^{2m−2j+2}Y^{i}X^{m+1−j−i})

+ \frac{XY}{4} ∑_{j=1}^{m} (∑_{k=0}^{j−1} γ_{k}^{2j−1}Y^{k}X^{j−1−k}) (∑_{i=0}^{m−j} γ_{i}^{2m−2j+1}Y^{i}X^{m−j−i}) .

B_{m+1} = ∑_{n=0}^{m+1} γ_{n}^{2m+2}Y^{n}X^{m+1−n} − X ∑_{n=0}^{m} γ_{n}^{2m+1}Y^{n}X^{m−n}

+ \frac{Y}{4} ∑_{j=1}^{m+1} ( ∑_{n=0}^{j−1+m+1−j} ( ∑_{k=max(0,n−m+j−1)}^{min(n,j−1)} γ_{k}^{2j−2}γ_{n−k}^{2m−2j+2}X^{j−1−k}X^{m+1−j−n+k}) Y^{n})

+ \frac{XY}{4} ∑_{j=1}^{m} ( ∑_{n=0}^{j−1+m−j} ( ∑_{k=max(0,n−m+j)}^{min(n,j−1)} γ_{k}^{2j−1}γ_{n−k}^{2m−2j+1}X^{j−1−k}X^{m−j−n+k}) Y^{n})

= ∑_{n=0}^{m+1} γ_{n}^{2m+2}Y^{n}X^{m+1−n} − X ∑_{n=0}^{m} γ_{n}^{2m+1}Y^{n}X^{m−n}

+ \frac{1}{4} ∑_{j=1}^{m+1} ∑_{n=0}^{m} ( ∑_{k=max(0,n−m+j−1)}^{min(n,j−1)} γ_{k}^{2j−2}γ_{n−k}^{2m−(2j−2)}) Y^{n+1}X^{m−n}

+ \frac{1}{4} ∑_{j=1}^{m} ∑_{n=0}^{m−1} ( ∑_{k=max(0,n−m+j)}^{min(n,j−1)} γ_{k}^{2j−1}γ_{n−k}^{2m−(2j−1)}) Y^{n+1}X^{m−n}

= ∑_{n=0}^{m+1} γ_{n}^{2m+2}Y^{n}X^{m−n+1} − ∑_{n=0}^{m} γ_{n}^{2m+1}Y^{n}X^{m−n+1}

+ \frac{1}{4} ∑_{n=1}^{m+1} ∑_{j=1}^{m+1} ( ∑_{k=max(0,n−m+j−2)}^{min(n−1,j−1)} γ_{k}^{2j−2}γ_{n−k−1}^{2m−(2j−2)}) Y^{n}X^{m−n+1}

+ \frac{1}{4} ∑_{n=1}^{m} ∑_{j=1}^{m} ( ∑_{k=max(0,n−m+j−1)}^{min(n−1,j−1)} γ_{k}^{2j−1}γ_{n−k−1}^{2m−(2j−1)}) Y^{n}X^{m−n+1}.

Consequently, the coefficient of X^{m+1} in B_{m+1} is

γ_{0}^{2m+2} − γ_{0}^{2m+1}.

Also, the coefficient of Y^{m+1} in B_{m+1} (n = m + 1) is

γ_{m+1}^{2m+2} + \frac{1}{4} ∑_{j=1}^{m+1} ∑_{k=max(0,j−1)=j−1}^{min(m,j−1)=j−1} γ_{k}^{2j−2}γ_{m−k}^{2m−(2j−2)}

= γ_{m+1}^{2m+2} + \frac{1}{4} ∑_{j=1}^{m+1} γ_{j−1}^{2j−2}γ_{m−j+1}^{2m−(2j−2)}

= γ_{m+1}^{2m+2} + \frac{1}{4} ∑_{j=0}^{m} γ_{j}^{2j}γ_{m−j}^{2(m−j)}.

Now for 1 ≤ n ≤ m, the coefficient of Y^{n}X^{m+1−n} is

γ_{n}^{2m+2} − γ_{n}^{2m+1} + \frac{1}{4} ∑_{j=1}^{m+1} (  ∑_{k=max(0,n−m+j−2)}^{min(n−1,j−1)} γ_{k}^{2j−2}γ_{n−k−1}^{2m−(2j−2)})

+ \frac{1}{4} ∑_{j=1}^{m} ( ∑_{k=max(0,n−m+j−1)}^{min(n−1,j−1)} γ_{k}^{2j−1}γ_{n−k−1}^{2m−(2j−1)})

= γ_{n}^{2m+2} − γ_{n}^{2m+1} + \frac{1}{4} ∑_{r=0}^{2m} ∑_{k=max(0,n−m−1+ \frac{r}{2} )}^{min(n−1, \frac{r}{2} )} γ_{k}^{r}γ_{n−k−1}^{2m−r}

= γ_{n}^{2m+2} − γ_{n}^{2m+1} + \frac{1}{4} ∑_{k=0}^{n−1} ∑_{r=2k}^{2m+2+2(k−n)} γ_{k}^{r}γ_{n−k−1}^{2m−r}.

Lemma 20. Let (S_{n})_{n≥0} be defined as in Definition 14. Then

\begin{cases}S_{0} = x, \\ S_{1} = −\frac{1}{2,} \\ S_{n} = 0, & n ≥ 2. \end{cases}  (26)

Proof. We start with S_{0} and S_{1} and obtain the result by a direct calculation. We then show that S_{n} = 0 for n ≥ 2 by induction.

We calculate S_{0} using the definitions of (p_{k}(x, y))_{k≥0} and (q_{k}(x, y))_{k≥0} given in Definition 13 and obtain

S_{0} = p_{0}q_{0} = d\frac{∂d}{∂x} = D^{\frac{1}{2}} \frac{x}{D^{\frac{1}{2}}} = x.  (27)

For S_{1} we use the results of Lemmas 16 and 17 to write

S_{1} = p_{0}q_{1} + p_{1}q_{0} = −\frac{1}{2}Y D^{−1} \underbrace{P_{0}^{2}}_{=γ_{0}^{0}=1} −\frac{1}{2}D^{− \frac{1}{2}} xD^{− \frac{1}{2}} x

= −\frac{1}{2}D^{−1} \underbrace{(Y + X)}_{=D} = −\frac{1}{2}.  (28)

The remainder of the proof focuses on S_{n}, for n ≥ 2. Combining the results of Theorem 10 and Lemma 15, we can write

D_{+}^{x} (d_{i− \frac{1}{2} ,j}D_{−}^{x}(d_{i,j})) = ∑_{n=0}^{∞} a_{n}h^{n} = 2,

where (a_{n})_{n≥0} is given in Equation (24). It follows that

\begin{cases}a_{0} = 2, \\ a_{n} = ∑_{k=0}^{n} \frac{1}{(n−k+1)!} \frac{∂^{(n−k+1)}S_{k}}{∂x^{n−k+1}} = 0, & n ≥ 1. \end{cases}  (29)

We now show by induction that Equation (29) implies S_{n} = 0, for all n ≥ 2.

1. First consider the base cases n = 2 and n = 3.

• For n = 2 we have

a_{2} = ∑_{k=0}^{2} \frac{1}{(3 − k)!} \frac{∂^{(3−k)}S_{k}}{∂x^{3−k}} = \frac{1}{6} \frac{∂^{3}S_{0}}{∂x^{3}} + \frac{1}{2} \frac{∂^{2}S_{1}}{∂x^{2}} + \frac{∂S_{2}}{∂x} .

Since S_{0} is a degree 1 polynomial in x and S_{1} is constant by (27) and (28), it

follows that \frac{∂^{3}S_{0}}{∂x^{3}} = \frac{∂^{2}S_{1}}{∂x^{2}} = 0. Consequently

a_{2} = \frac{∂S_{2}}{∂x} .

Additionally, since a_{2} = 0 by Equation (29), it follows that

\frac{∂S_{2}}{∂x} = 0.

Hence S_{2} is constant in x. Furthermore, using Lemma 19 we know that

S_{2} = −\frac{1}{2}xY D^{−2}A,

where A is constant. Note that −\frac{1}{2}xY D^{−2} is a known non-constant and non-zero rational function of x where the numerator is a polynomial of degree 1 in x and the denominator a polynomial of degree 4 in x. Since S_{2} is independent of x, it follows that necessarily A = 0. Thus

S_{2} = 0.

• For n = 3 we have

a_{3} = ∑_{k=0}^{3} \frac{1}{(4 − k)!} \frac{∂^{(4−k)}S_{k}}{∂x^{4−k}} = \frac{1}{24} \frac{∂^{4}S_{0}}{∂x^{4}} + \frac{1}{6} \frac{∂^{3}S_{1}}{∂x^{3}} + \frac{1}{2} \frac{∂^{2}S_{2}}{∂x^{2}} + \frac{∂S_{3}}{∂x} = 0.

Since S_{1} is a polynomial of degree 1, S_{0} is constant and S_{2} = 0, we have

a_{3} = \frac{∂S_{3}}{∂x} = 0.

Thus S_{3} is constant in x. Furthermore, using Lemma 19 we know that

S_{3} = −\frac{1}{2}Y D^{−3}B,

where B is a polynomial of degree 2 in x. Again we observe that −\frac{1}{2}Y D^{−3} is a known non-constant and non-zero rational function of x where the numerator is constant in x and the denominator a polynomial of degree 6 in x. Since S_{3} is independent of x it follows that necessarily B = 0. Hence

S_{3} = 0.

2. For the induction hypothesis, we let n ≥ 2 and assume that S_{k} = 0 for all 2 ≤ k ≤ n. Then we have

a_{n+1} = ∑_{k=0}^{n+1} \frac{1}{(n − k + 2)!} \frac{∂^{(n−k+2)}S_{k}}{∂x^{n−k+2}}

= \frac{1}{(n + 2)!} \frac{∂^{n+2}S_{0}}{∂x^{n+2}} + \frac{1}{(n + 1)!} \frac{∂^{n+1}S_{1}}{∂x^{n+1}} + \frac{1}{n!} \frac{∂^{n}S_{2}}{∂x^{n}} + ⋯ + \frac{∂^{2}S_{n}}{∂x^{2}} + \frac{∂S_{n+1}}{∂x} .

Since n ≥ 2, it follows that n + 2 ≥ 4 and n + 1 ≥ 3. Consequently, since S_{0} is a degree 1 polynomial in x and S_{1} is constant, we have

\frac{∂^{n+2}S_{0}}{∂x^{n+2}} = \frac{∂^{n+1}S_{1}}{∂x^{n+1}} = 0.

Additionally, using the induction hypothesis and Equation (29), we obtain

a_{n+1} = \frac{∂S_{n+1}}{∂x} = 0.

Thus S_{n+1} is constant in x. Using the result of Lemma 19, we see that S_{n+1} can be expressed as a product of a fixed non-constant and non-zero rational function of x and a polynomial in x. (The expression of the rational function and the degree of the polynomial will vary depending on whether n is even or odd). In any case, since S_{n+1} is independent of x it follows that the polynomial in S_{n+1} needs to be zero. Hence

S_{n+1} = 0.

Since S_{2} = S_{3} = 0 it follows that S_{n} = 0 for all n ≥ 2.

Proof. Proof of Theorem 12.

Let (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} be defined by (1). Combining Lemmas 19 and 20, we obtain for m ≥ 0

S_{2m+2} = S_{2m+3} = 0.

Thus

S_{2m+2} = (−\frac{1}{2}xY D^{−(2m+2)}) A_{m} = 0,

and A_{m} = 0 for m ≥ 0 (proved in the proof of Lemma 20).

Similarly,

S_{2m+3} = (−\frac{1}{2}Y D^{−(2m+3)}) B_{m+1} = 0,

and B_{m+1} = 0 for m ≥ 0 (proved in the proof of Lemma 20). Since A_{m} and B_{m+1} are polynomials, it follows that all their coefficients are zero. Hence by Lemma 19 we obtain

γ_{0}^{2m+1} − γ_{0}^{2m} = 0,  for m ≥ 0;
γ_{0}^{2m+2} − γ_{0}^{2m+1} = 0,  for m ≥ 0;
γ_{m+1}^{2m+2} + \frac{1}{4} ∑_{k=0}^{m} γ_{k}^{2k}γ_{m−k}^{2(m−k)} = 0,  for m ≥ 0;
γ_{n}^{2m+1} − γ_{n}^{2m} + \frac{1}{4} ∑_{k=0}^{n−1} ∑_{j=2k}^{2m+1+2(k−n)} γ_{k}^{j}γ_{n−k−1}^{2m−1−j} = 0, for m ≥ 1, 1 ≤ n ≤ m;
γ_{n}^{2m+2} − γ_{n}^{2m+1} + \frac{1}{4} ∑_{k=0}^{n−1} ∑_{j=2k}^{2m+2+2(k−n)} γ_{k}^{j}γ_{n−k−1}^{2m−j} = 0, for m ≥ 1, 1 ≤ n ≤ m.

We remark that we could also have obtained the first two equations by using γ_{0}^{n} = 1 for all n ≥ 0. Observe also that the last three equations correspond to the single equation

γ_{n}^{p} − γ_{n}^{p−1} + \frac{1}{4} ∑_{k=0}^{n−1} ∑_{j=2k}^{p+2(k−n)} γ_{k}^{j}γ_{n−k−1}^{p−2−j} = 0,  (30)

where p ≥ 2 and 1 ≤ n ≤ ⌊\frac{p}{2}⌋. The last equation corresponds to (30) for p = 2m + 2 and 1 ≤ k ≤ ⌊\frac{p}{2}⌋−1. The equation above it corresponds to (30) for p = 2m+1 and 1 ≤ k ≤ ⌊\frac{p}{2}⌋, and finally the third equation above corresponds to (30) for p = 2m + 2 and k = m + 1.

Thus, by rewriting (30) as

γ_{n}^{p} = γ_{n}^{p−1} − \frac{1}{4} ∑_{k=0}^{n−1} ∑_{j=2k}^{p+2(k−n)} γ_{k}^{j}γ_{n−k−1}^{p−2−j},

for p ≥ 2 and 1 ≤ n ≤ ⌊\frac{p}{2}⌋, we obtain the nonlinear recursion relation stated in Theorem 12.

Remark 21. The nonlinear recursion can also be verified by using the closed form formula for the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}

γ_{k}^{n} = (−\frac{1}{4})^{k} \binom{n}{2k}C_{k},

for n ≥ 0 and 0 ≤ k ≤ ⌊\frac{n}{2}⌋. In this case, for n ≥ 2 and 1 ≤ k ≤ ⌊\frac{n}{2}⌋, we can write

−\frac{1}{4} ∑_{i=0}^{k−1} ∑_{j=2i}^{n+2(i−k)} γ_{i}^{j}γ_{k−i−1}^{n−2−j} = (−\frac{1}{4})^{k} ∑_{i=0}^{k−1} C_{i}C_{k−1−i} ∑_{j=2i}^{n−2k+2i} \binom{j}{2i}\binom{n − 2 − j}{2k − 2 − 2i}.

Changing variables in the inner sum, we can write

∑_{j=2i}^{n−2k+2i} \binom{j}{2i}\binom{n − 2 − j}{2k − 2 − 2i} = ∑_{j=0}^{n−2k} \binom{j + 2i}{2i}\binom{n − 2 − (j + 2i)}{2k − 2 − 2i}.

Using Theorem 2 (binomial theorem for rising polynomials) we can rewrite the inner sum as

∑_{j=0}^{n−2k} \binom{j + 2i}{2i}\binom{n − 2 − (j + 2i)}{2k − 2 − 2i}

= \frac{1}{(n − 2k)!} ∑_{j=0}^{n−2k} \frac{(n − 2k)!}{j!(n − 2k − j)!} \frac{(j + 2i)!}{(2i)!} \frac{(n − 2 − (j + 2i))!}{(2k − 2i − 2)!}

= \frac{1}{(n − 2k)!} ∑_{j=0}^{n−2k} \binom{n − 2k}{j}(2i + 1)\overline{j}(2k − 2i − 1)\overline{n−k−j}

= \frac{1}{(n − 2k)!}(2k)\overline{n−2k}

= \frac{(n − 1)!}{(2k)!(n − 2k)!}

= \binom{n − 1}{2k − 1}.

Thus, the inner sum is simply the binomial coefficient \binom{n − 1}{2k − 1}. Consequently, we have

−\frac{1}{4} ∑_{i=0}^{k−1} ∑_{j=2i}^{n+2(i−k)} γ_{i}^{j}γ_{k−i−1}^{n−2−j} = (−\frac{1}{4})^{k} \binom{n − 1}{2k − 1} ∑_{i=0}^{k−1} C_{i}C_{k−1−i}.

We now employ the recursion relation for the Catalan numbers (2) to obtain

−\frac{1}{4} ∑_{i=0}^{k−1} ∑_{j=2i}^{n+2(i−k)} γ_{i}^{j}γ_{k−i−1}^{n−2−j} = (−\frac{1}{4})^{k} \binom{n − 1}{2k − 1}C_{k}.

Finally, since \binom{n − 1}{2k − 1} = \binom{n}{2k} − \binom{n − 1}{2k}, we have

−\frac{1}{4} ∑_{i=0}^{k−1} ∑_{j=2i}^{n+2(i−k)} γ_{i}^{j}γ_{k−i−1}^{n−2−j} = (−\frac{1}{4})^{k} C_{k} (\binom{n}{2k} − \binom{n − 1}{2k})
= γ_{k}^{n} − γ_{k}^{n−1}.

6 Generating function

In this section we calculate the generating function for the sequence (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋}. Interestingly, the calculations involve the generalized Motzkin numbers (4) and their generating function (6). We note that the generalized Motzkin numbers M_{n}(a, b) introduced by Sun [17] were only studied for a, b ∈ ℤ. Therefore, the generating function (6) was shown to exist for a, b ∈ ℤ. We first point out that the generalized Motzkin numbers as defined in (4) are well defined for a, b ∈ ℝ, as is their generating function (6). Secondly, we can show that the generalized Motzkin numbers (4) and the generating function (6) both imply the recurrence relation (5). Since there is a unique solution to the recurrence relation (5), it follows that the generating function for the generalized Motzkin numbers for a, b ∈ ℝ is the generating function (6) obtained by Sun. Finally, we remark that if x satisfies

|x| < min (\frac{1}{2|a|}, \frac{1}{|a + 2\sqrt{|b|}|}, \frac{1}{|a − 2\sqrt{|b|}|}) ,  (31)

then (6) holds and its series is absolutely convergent.

Theorem 22. Let (γ_{k}^{n})_{n≥0, 0≤k≤⌊\frac{n}{2}⌋} be defined by the recursion relation and initial conditions given in (1). Then its generating function is

F_{γ}(x, y) = ∑_{n=0}^{∞} \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} γ_{k}^{n}x^{k}y^{n−2k} = 2\frac{y − 1 + \sqrt{(1 − y)^{2} + x}}{x}.

Proof. The proof uses the generalized Motzkin numbers (4) and their generating function (6).

F_{γ}(x, y) = ∑_{n=0}^{∞} \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} γ_{k}^{n}x^{k}y^{n−2k}

= ∑_{n=0}^{∞} \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n}{2k}C_{k} (\frac{−x}{4})^{k} y^{n−2k}

= ∑_{n=0}^{∞} M_{n} (y, −\frac{x}{4}) .

This series is the generating function for the Motzkin numbers M_{n} (y, −\frac{x}{4}) at 1. Thus, using (31), we see that if we select x and y such that

\begin{cases}|y| < \frac{1}{2}, \\ |y + \sqrt{|x|}| < 1, \\ |y − \sqrt{|x|}| < 1, \end{cases}

then the series ∑_{n=0}^{∞} M_{n} (y, −\frac{x}{4}) converges absolutely to M_{y,− \frac{x}{4}} (1). Thus we have

F_{γ}(x, y) = ∑_{n=0}^{∞} M_{n} (y, −\frac{x}{4})

= M_{y,− \frac{x}{4}} (1)

= \frac{1 − y − \sqrt{(1 − y)^{2} − 4 (−\frac{x}{4})}}{2\frac{−x}{4}}

= 2\frac{y − 1 + \sqrt{(1 − y)^{2} + x}}{x}.

7 Conclusion

In this paper, we studied a doubly indexed sequence related to the Catalan and Motzkin numbers. We showed that this sequence satisfies both a linear and a nonlinear recursion relation. The nonlinear recursion relation was obtained by applying an exact finite difference scheme with compact stencil to the differential operator (∇ · (d∇d)) (x, y), where d is the two-dimensional Euclidean distance function. We also calculated the generating function associated with this doubly indexed sequence. This work is, to our knowledge, the first instance of the usage of a finite difference scheme to obtain identities about a sequence, and another demonstration of the ubiquity of the Catalan numbers.

References

[1] Martin Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[2] Drew Armstrong, Brendon Rhoades, and Nathan Williams, Rational Catalan combinatorics: the associahedron, Discrete Math. Theoret. Comput. Sci. (2013), 933–944.

[3] M. Artioli, G. Dattoli, S. Licciardi, and S. Pagnutti, Motzkin numbers: an operational point of view, preprint, 2017. Available at https://arxiv.org/abs/1703.07262.

[4] F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, Discrete Math. 204 (1999), 73–112.

[5] P. Blasiak, G. Dattoli, A. Horzela, K. A. Penson, and K. Zhukovsky, Motzkin numbers, central trinomial coefficients and hybrid polynomials, J. Integer Sequences 11 (2008), Article 08.1.1.

[6] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Comb. Theory Ser. A 23 (1977), 291–301.

[7] Nikolao Fuss, Solutio quaestionis, quot modis polygonum n laterum in polygona m laterum, per diagonales resolvi quaeat, Novi Acta Academiae. Scientiarum imperialis Petropolitanae 9 (1791), 243–251 (in Latin).

[8] H. Gould, Binomial coefficients, the bracket functions, and compositions with relatively prime summands, Fibonacci Quart. 4 (1964), 241–259.

[9] S. Heubach, N. Y. Li, and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math. 308 (2008), 5954–5964.

[10] P. Hilton and J. Pedersen, Catalan numbers, their generalization, and their uses, Math. Intelligencer 13 (1991), 64–75.

[11] D. Kim, On the (n, k)-th Catalan numbers, Commun. Korean Math. Soc. 23 (2008), 349–356.

[12] P. J. Larcombe, The 18-th century Chinese discovery of the Catalan numbers, Math. Spectrum 32 (1999), 5–7.

[13] J. J. Luo, Antu Ming, the first inventor of Catalan numbers of the world, Neimenggu Daxue Xuebao 19 (1988), 239–245 (in Chinese).

[14] T. Motzkin, Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products, Bull. Amer. Math. Soc. 54 (1948), 352–360.

[15] I. Pak, Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees, Discrete Math. 204 (1999), 329–335.

[16] R. Stanley, Catalan Numbers, Cambridge University Press, 2015.

[17] Z.-W. Sun, Congruences involving generalized central trinomial coefficients, Sci. China Math. 57 (2014), 1375–1400.

[18] Y. Wang and Z. Zhang, Combinatorics of generalized Motzkin numbers, J. Integer Sequences 18 (2015) Article 15.2.4.

[19] J. Zhao and F. Qi, Two explicit formulas for the generalized Motzkin numbers, J. Inequal. Appl. 19 (2017).

2000 Mathematics Subject Classification: Primary 11B37; Secondary 39A14, 65Q30, 05A15. Keywords: Catalan number, Motzkin number, generalized Motzkin number, recurrence relation, explicit formula, finite difference scheme, generating function.

(Concerned with sequences \underline{A000108} and \underline{A001006}.)

Received May 11 2018; revised version received August 27 2018. Published in Journal of Integer Sequences, November 24 2018.

Return to Journal of Integer Sequences home page.