Combinatorics of Generalized Motzkin Numbers

Yi Wang and Zhi-Hai Zhang School of Mathematical Sciences Dalian University of Technology Dalian 116024 PR China

                      wangyi@dlut.edu.cn
                    zzhdlut008@dlut.edu.cn

Abstract The generalized Motzkin numbers are common generalizations of the Motzkin numbers and the Catalan numbers. We investigate their combinatorial properties, including the combinatorial interpretation, the recurrence relation, the binomial transform, the Hankel transform, the log-convexity, the continued fraction of the generating function, and the total positivity of the corresponding Hankel matrix.

1 Introduction

The Motzkin numbers M_{n} count the number of lattice paths from (0, 0) to (n, 0) with steps H = (1, 0), U = (1, 1) and D = (1, −1), never going below the x-axis [1, 6]. It is well known that the Motzkin numbers satisfy the recursion

(n + 3)M_{n+1} = (2n + 3)M_{n} + 3nM_{n−1}

(see [16] for a combinatorial proof). The Motzkin numbers are closely related to the ubiquitous Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n}, which count the number of lattice paths from (0, 0) to (2n, 0) with steps U and D, never falling below the x-axis. For example,

M_{n} = ∑_{k} \binom{n}{2k}C_{k}, C_{n+1} = ∑_{k} \binom{n}{k}M_{k}.

It follows that

C_{n+1} = ∑_{k} \binom{n}{2k}C_{k}2^{n−2k}.

See [5, 6] for combinatorial interpretations of these identities. On the other hand, the Motzkin numbers and the Catalan numbers enjoy some similar properties, including the recurrence relations

M_{n+1} = M_{n} + ∑_{k=0}^{n−1} M_{k}M_{n−1−k}, C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k}

and the generating functions

∑_{n≥0} M_{n}x^{n} = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}} ,  ∑_{n≥0} C_{n}x^{n} = \frac{1 − \sqrt{1 − 4x}}{2x}.

Very recently, Z.-W. Sun [18] introduced the generalized Motzkin numbers

M_{n}(b, c) := ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}C_{k}b^{n−2k}c^{k}, n = 0, 1, 2, …,  (1)

where b, c ∈ ℕ. Clearly, the generalized Motzkin numbers are common generalizations of the Motzkin numbers and the Catalan numbers:

M_{n}(1, 1) = M_{n}, M_{n}(2, 1) = C_{n+1}.

It is also known that M_{n}(3, 1) = H_{n} are the restricted hexagonals numbers described in Harary and Read [7] and M_{n}(0, 1) form the sequence (C_{0}, 0, C_{1}, 0, C_{2}, 0, …) of the Catalan numbers.

Sun [18] established the recursion

(n + 3)M_{n+1}(b, c) = b(2n + 3)M_{n}(b, c) − (b^{2} − 4c)nM_{n−1}(b, c),

the generating function

M(b, c; x) := ∑_{n≥0} M_{n}(b, c)x^{n} = \frac{1 − bx − \sqrt{(1 − bx)^{2} − 4cx^{2}}}{2cx^{2}} ,  (2)

and applied them to study arithmetic properties of the generalized Motzkin numbers. The object of this paper is to investigate combinatorial properties of the generalized Motzkin numbers, including the combinatorial interpretation, the recurrence relation, the binomial transform, the Hankel transform, the log-convexity, the continued fraction of the generating function, and the total positivity of the corresponding Hankel matrix.

Let α = (a_{n})_{n≥0} be a sequence of nonnegative numbers. We say that the sequence is log-convex if a_{i}a_{j+1} ≥ a_{i+1}a_{j} for 0 ≤ i < j. Many well-known combinatorial numbers form a log-convex sequence, including the Catalan numbers C_{n} and the Motzkin numbers M_{n}. See [11, 19, 21] for details. Define the Hankel matrix H(α) of a sequence α = (a_{n})_{n≥0} by

H(α) = [a_{i+j}]_{i,j≥0} = [ \begin{matrix}a_{0} & a_{1} & a_{2} & a_{3} & ⋯ \\ a_{1} & a_{2} & a_{3} & a_{4} & ⋯ \\ a_{2} & a_{3} & a_{4} & a_{5} & ⋯ \\ a_{3} & a_{4} & a_{5} & a_{6} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} ] .

A matrix is called totally positive of order r (TP_{r} for short), if its minors of all orders ≤ r are nonnegative. It is TP if all minors are nonnegative. Clearly, a sequence is log-convex if and only if its Hankel matrix is TP_{2}. We refer the reader to [10, 13] for more information about TP matrices.

Theorem 1. Let M_{n} := M_{n}(b, c) be the generalized Motzkin numbers defined by (1). Then we have the following.

(i) The recurrence relation

M_{n+1}(b, c) = bM_{n}(b, c) + c ∑_{i=0}^{n−1} M_{i}(b, c)M_{n−1−i}(b, c)

for n ≥ 1.

(ii) The generating function

M(b, c; x) = \frac{1}{1 − bx − \frac{cx^{2}}{1 − bx − \frac{cx^{2}}{1 − bx − ⋯}}} .

(iii) The binomial transform

∑_{k=0}^{n} \binom{n}{k}M_{k}(b, c) = M_{n}(b + 1, c).

(iv) The Hankel transform

det [ \begin{matrix}M_{0} & M_{1} & ⋯ & M_{n} \\ M_{1} & M_{2} & ⋯ & M_{n+1} \\ ⋮ & ⋮ & ... & ⋮ \\ M_{n} & M_{n+1} & ⋯ & M_{2n} \end{matrix} ] = c^{\binom{n+1}{2}}.

(v) The Hankel matrix

[ \begin{matrix}M_{0} & M_{1} & M_{2} & ⋯ \\ M_{1} & M_{2} & M_{3} & ⋯ \\ M_{2} & M_{3} & M_{4} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ]

is totally positive if b^{2} ≥ 4c.

(vi) The sequence (M_{n})_{n≥0} is log-convex if b^{2} ≥ c.

2 Proof of Theorem 1

The generalized Motzkin triangle is an infinite lower triangular matrix M(b, c) = [M_{n,k}(b, c)] defined by

M_{0,0}(b, c) = 1, M_{n+1,k}(b, c) = M_{n,k−1}(b, c) + bM_{n,k}(b, c) + cM_{n,k+1}(b, c), k ≥ 1. (3)

Such a triangle has occurred in the literature. For example, it is called the (b, c/b)-Motzkin triangle in He [8]. In particular, M(1, 0) is the famous Pascal triangle, M(1, 1) is the Motzkin triangle [2], and M(2, 1) is the Catalan triangle of Aigner [3]. Following Aigner [3], M(b, c) is a recursive matrix and the entries M_{n,0}(b, c) of its first column are the corresponding Catalan-like numbers. In this section, we first demonstrate that the generalized Motzkin numbers M_{n}(b, c) is precisely the Catalan-like numbers corresponding to the generalized Motzkin triangle M(b, c), i.e., M_{n}(b, c) = M_{n,0}(b, c), and then apply this result to prove Theorem 1.

The generalized Motzkin triangle is also a Riordan array. A Riordan array, denoted by (g(x), f(x)), is an infinite lower triangular matrix whose generating function of the kth column is x^{k}f^{k}(x)g(x) for k = 0, 1, 2, …, where g(0) = 1 and f(0) ≠ 0. A basic example of Riordan array is the Pascal triangle

P = [\binom{n}{k}]_{n,k≥0} = (\frac{1}{1 − x}, \frac{1}{1 − x}) .

It is well known [14, 15] that all Riordan arrays form a group under the matrix multiplication:

(g(x), f(x)) ∗ (d(x), h(x)) = (g(x)d(xf(x)), f(x)h(xf(x))).  (4)

A Riordan array R = (g(x), f(x)) = [r_{n,k}]_{n,k≥0} can be characterized by two sequences A = (a_{n})_{n≥0} and Z = (z_{n})_{n≥0} such that

r_{0,0} = 1, r_{n+1,0} = ∑_{j≥0} z_{j}r_{n,j}, r_{n+1,k+1} = ∑_{j≥0} a_{j}r_{n,k+j}  (5)

for n, k ≥ 0 (see [9] for instance). Let A(x) and Z(x) be the generating functions of A- and Z- sequences respectively. Then it follows from (5) that

g(x) = \frac{1}{1 − xZ(xf(x))},  f(x) = A(xf(x)).  (6)

See [9] for details. Now M(b, c) is a Riordan array with A(x) = 1+bx+cx^{2} and Z(x) = b+cx. Let M(b, c) = (M(x), m(x)). Then by (6),

M(x) = \frac{1}{1 − bx − cx^{2}m(x)},  m(x) = 1 + bxm(x) + cx^{2}m^{2}(x).  (7)

Note that m(0) = 1. Solve (7) to obtain

M(x) = m(x) = \frac{1 − bx − \sqrt{(1 − bx)^{2} − 4cx^{2}}}{2cx^{2}} .

Comparing with (2), we have M(b, c; x) = M(x). Thus M_{n}(b, c) = M_{n,0}(b, c). Furthermore,

M(b, c; x) = 1 + bxM(b, c; x) + cx^{2}M^{2}(b, c; x).  (8)

Now we are in a position to prove Theorem 1.

(i) Comparing coefficients of x^{n+1} on both sides of (8), we have M_{0}(b, c) = 1 and

M_{n+1}(b, c) = bM_{n}(b, c) + c ∑_{i=0}^{n−1} M_{i}(b, c)M_{n−1−i}(b, c)

for n ≥ 1.

(ii) Rewrite (8) as

M(b, c; x) = \frac{1}{1 − bx − cx^{2}M(b, c; x)},

which leads to the continued fraction

M(b, c; x) = \frac{1}{1 − bx − \frac{cx^{2}}{1 − bx − \frac{cx^{2}}{1 − bx − ⋯}}} .

(iii) Let P be the Pascal triangle. Then by (4),

P · M(b, c) = (\frac{1}{1 − x}, \frac{1}{1 − x}) · (M(b, c; x); M(b, c; x))
= (\frac{1}{1 − x}M (b, c; \frac{x}{1 − x}) , \frac{1}{1 − x}M (b, c; \frac{x}{1 − x}))

Note that

\frac{1}{1 − x}M (b, c; \frac{x}{1 − x}) = \frac{1}{1 − x} \frac{1 − \frac{bx}{1−x} − \sqrt{(1 − \frac{bx}{1−x})^{2} − \frac{4cx^{2}}{(1−x)^{2}}}}{\frac{2cx^{2}}{(1−x)^{2}}}

= \frac{1 − x − bx − \sqrt{(1 − x − bx)^{2} − 4cx^{2}}}{2cx^{2}}
= M(b + 1, c; x).

Hence P · M(b, c) = M(b + 1, c). Comparing entries of the first columns on both sides, we obtain

∑_{k=0}^{n} \binom{n}{k}M_{k}(b, c) = M_{n}(b + 1, c).

(iv) Let H(b, c) = [M_{i+j}(b, c)]_{i,j≥0} be the Hankel matrix of the generalized Motzkin numbers and

H_{n} = [M_{i+j}(b, c)]_{0≤i,j≤n} = [ \begin{matrix}M_{0} & M_{1} & ⋯ & M_{n} \\ M_{1} & M_{2} & ⋯ & M_{n+1} \\ ⋮ & ⋮ & ... & ⋮ \\ M_{n} & M_{n+1} & ⋯ & M_{2n} \end{matrix} ]

the nth leading principal submatrices of H. The fundamental theorem of Aigner on recursive matrices states that

M_{m+n}(b, c) = M_{m+n,0}(b, c) = ∑_{k} c^{k}M_{m,k}(b, c)M_{n,k}(b, c),

or equivalently,

H = MT M^{t},

where T = diag[1, c, c^{2}, c^{3}, …] is a diagonal matrix [3, p. 351]. Since M is a lower triangular matrix with all diagonal entries are 1, we have

det(H_{n}) = c^{1+2+···+n} = c^{\binom{n+1}{2}}.

To prove (v) and (vi), we need the following result, which is a special case of [4, Theorem 2.8].

Lemma 2. If the sequence (1, b, c) is PF, then M(b, c) is TP. If the sequence (1, b, c) is log-concave, then the sequence (M_{n,0}(b, c))_{n≥0} is log-convex.

It is well known that a finite sequence of nonnegative numbers is PF if and only if its generating function has only real zeros (see [10, p. 399] for instance). So, if b^{2} ≥ 4c, then the matrix M is TP, and so is its transpose M^{t}. Clearly, the diagonal matrix T is TP. Also, the product of TP matrices is TP. Thus the Hankel matrix H = MT M^{t} is TP if b^{2} ≥ 4c by Lemma 2. This proves (v).

(vi) is an immediate consequence of Lemma 2. This completes the proof of the theorem.

3 Remarks

In this paper we investigate the generalized Motzkin numbers by setting them in a broader context (the generalized Motzkin triangle). This approach gives us more room to work and is often more effective because the theory of matrices is more fruitful.

Aigner [3] used (weighted) lattice path techniques to give combinatorial interpretations of entries of a recursive matrix, including the Catalan-like numbers. Here we present a combinatorial interpretation of the generalized Motzkin numbers from such a viewpoint.

Recall that a Motzkin path of length n is a lattice path from (0, 0) to (n, 0) with steps H = (1, 0), U = (1, 1) and D = (1, −1), never going below the x-axis. To the steps we assign weights w(U) = 1, w(H) = b, w(D) = c. Let P_{n} be the set of Motzkin paths of length n. For P ∈ P_{n}, define the weight w(P) = ∏ w(steps). Then

M_{n}(b, c) = ∑_{P ∈P_{n}} w(P).

Some combinatorial properties of the generalized Motzkin numbers follow immediately from the point of view of weighted lattice paths, including the recurrence relations, the generating functions and the log-convexity. We refer the reader to [3, 12, 17, 20] for more information.

4 Acknowledgments

The authors thank the anonymous referee for his/her careful reading and helpful comments. This work was supported in part by the National Natural Science Foundation of China (Grant No. 11371078) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20110041110039).

References

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

[2] M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999), 33–51.

[3] M. Aigner, Catalan and other numbers: A recurrent theme, in H. Crapo and D. Senato, eds., Algebraic Combinatorics and Computer Science, Springer, 2001, pp. 347–390.

[4] X. Chen, H. Liang, and Y. Wang, Total positivity of Riordan arrays, European J. Combin. 46 (2015), 68–74.

[5] R. Donaghey, Restricted plane tree representations for four Motzkin-Catalan equations, J. Combin. Theory Ser. B 22 (1977), 114–121.

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

[7] F. Harary and R. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. 17 (1970), 1–13.

[8] T.-X. He, Parametric Catalan numbers and Catalan triangles, Linear Algebra Appl. 438 (2013), 1467–1484.

[9] T.-X. He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), 3962–3974.

[10] S. Karlin, Total Positivity, Vol. 1, Stanford University Press, 1968.

[11] L. Liu and Y. Wang, On the log-convexity of combinatorial sequences, Adv. in Appl. Math. 39 (2007), 453–476.

[12] T. Mansour, M. Schork, and Y. Sun, Motzkin numbers of higher rank: Generating function and explicit expression, J. Int. Seq. 10 (2007), Article 07.7.4.

[13] A. Pinkus, Totally Positive Matrices, Cambridge University Press, 2010.

[14] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[15] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 32 (1994), 267– 290.

[16] R. A. Sulanke, Bijective recurrences for Motzkin paths, Adv. in Appl. Math. 27 (2001), 627–640.

[17] H. Sun and Y. Wang, A combinatorial proof of the log-convexity of Catalan-like numbers, J. Integer Seq. 17 (2014), Article 14.5.2.

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

[19] Y. Wang and Z.-H. Zhang, Log-convexity of Aigner-Catalan-Riordan numbers, Linear Algebra Appl. 463 (2014), 45–55.

[20] W. J. Woan, A relation between restricted and unrestricted weighted Motzkin paths, J. Integer Seq. 9 (2006), Article 06.1.7.

[21] B.-X. Zhu, Log-convexity and strong q-log-convexity for some triangular arrays, Adv. in Appl. Math. 50 (2013), 595–606.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19, 05A20. Keywords: generalized Motzkin number, Motzkin number, Catalan number, Hankel matrix, total positivity, log-convexity.

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

Received November 19 2014; revised versions received December 17 2014. Published in Journal of Integer Sequences, January 24 2015.

Return to Journal of Integer Sequences home page.