Some formulas for the central trinomial and Motzkin numbers

Dan Romik Department of Mathematics Weizmann Institute of Science Rehovot 76100 Israel romik@wisdom.weizmann.ac.il

Abstract We prove two new formulas for the central trinomial coefficients and the Motzkin

numbers.

1 Introduction

Let c_{n} denote the nth central trinomial coefficient, defined as the coefficient of x^{n} in the expansion of (1 + x + x^{2})^{n}, or more combinatorially as the number of planar paths starting at (0, 0) and ending at (n, 0), whose allowed steps are (1, 0), (1, 1), (1, −1). Let m_{n} denote the nth Motzkin number, defined as the number of such planar paths which do not descend below the x-axis. The first few c_{n}’s are 1, 3, 7, 19, 51, ..., and the first few m_{n}’s are 1, 2, 4, 9, 21, .... We prove

Theorem 1 m_{n} = ∑_{k=⌈(n+2)/3⌉}^{⌊(n+2)/2⌋} \frac{(3k − 2)!}{(2k − 1)!(n + 2 − 2k)!(3k − n − 2)!}  (1)

c_{n} = (−1)^{n+1} + 2n ∑_{k=⌈n/3⌉}^{⌊n/2⌋} \frac{(3k − 1)!}{(2k)!(n − 2k)!(3k − n)!}  (2)

It is interesting to compare these formulas with some of the other known formulas [6] for m_{n} and c_{n}:

m_{n} = ∑_{k=0}^{⌊n/2⌋} \frac{n!}{k!(k + 1)!(n − 2k)!}

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

c_{n} = ∑_{k=0}^{⌊n/2⌋} \frac{n!}{(k!)^{2}(n − 2k)!}

c_{n} = \frac{1}{2^{n}} ∑_{k=0}^{⌊n/2⌋} \frac{3^{k}(2n − 2k)!}{k!(n − k)!(n − 2k)!}

Formulas such as (1) and (2) can be proven automatically by computer, using the methods and software of Petkovšek, Wilf and Zeilberger [5]. We offer an independent, non-automatic proof that involves a certain symmetry idea which might lead to the discovery of other such identities. Two simpler auxiliary identities used in the proof are also automatically verifiable and shall not be proved.

2 Proof of the main result

Proof of (1). Our proof uses a variant of the generating function [6] for the numbers m_{n}, namely

f(x) = \frac{1 − x + \sqrt{1 + 2x − 3x^{2}}}{2} = 1 − x^{2} + ∑_{n=3}^{∞}(−1)^{n+1}m_{n−2}x^{n}

Then f satisfies f(0) = 1, f(1) = 0 and is decreasing on [0, 1]. Another property of f that will be essential in the proof is that it satisfies the functional equation

f(x)^{2} − f(x)^{3} = x^{2} − x^{3},  0 ≤ x ≤ 1,  (3)

as can easily be verified. A simple corollary of this is that f(f(x)) = x for x ∈ [0, 1]. Next, define

g(x) = ∑_{k=1}^{∞} \frac{2(3k − 2)!}{(2k)!(k − 1)!}(x^{2} − x^{3})^{k}

Since on [0, 1], the maximal value attained by x^{2} − x^{3} is 4/27 (at x = 2/3), by Stirling’s formula the series is seen to converge everywhere on [0, 1], to a function g(x) which is realanalytic except at x = 2/3. We now expand g(x) in powers of 1 − x; all rearrangement operations are permitted by absolute convergence:

g(x) = ∑_{k=1}^{∞} \frac{2(3k − 2)!}{(2k)!(k − 1)!}x^{2k}(1 − x)^{k} =

= ∑_{k=1}^{∞} \frac{2(3k − 2)!}{(2k)!(k − 1)!}(1 − x)^{k} ∑_{j=0}^{k} \binom{2k}{j}(−1)^{j}(1 − x)^{j} =

= ∑_{n=1}^{∞} ( ∑_{k=⌈n/3⌉}^{n} \binom{2k}{n − k}(−1)^{n+k} \frac{2(3k − 2)!}{(2k)!(k − 1)!}) (1 − x)^{n} = 1 − x,

where the last equality follows from the automatically verifiable [5] identity

∑_{k=⌈n/3⌉}^{n} \frac{(−1)^{k}(3k − 2)!}{(k − 1)!(n − k)!(3k − n)!} = 0, n > 1.

We have shown that g(x) = 1 − x near x = 1. But since g(x) is defined as a function of x^{2} − x^{3}, by (3) it follows that g(f(x)) = g(x), and therefore near x = 0 we have

g(x) = g(f(x)) = 1 − f(x) = x^{2} + ∑_{n=3}^{∞}(−1)^{n}m_{n−2}x^{n}.

Now to prove (1), we expand g(x) into powers of x, again using easily justifiable rearrangement operations

g(x) = ∑_{k=1}^{∞} \frac{2(3k − 2)!}{(2k)!(k − 1)!}x^{2k}(1 − x)^{k} =

= ∑_{k=1}^{∞} \frac{2(3k − 2)!}{(2k)!(k − 1)!}x^{2k} ∑_{j=0}^{k} \binom{k}{j}(−1)^{j}x^{j} =

= ∑_{n=2}^{∞} ((−1)^{n} ∑_{k=⌈n/3⌉}^{⌊n/2⌋} \frac{(3k − 2)!}{(2k − 1)!(n − 2k)!(3k − n)!}) x^{n}.

Equating coefficients in the last two formulas gives (1).

Proof of (2). We use a similar idea, this time using instead of the function f(x) the function − log f(x), which generates a sequence related to c_{n}. Since the generating function for c_{n} is well known [6] to be 1/\sqrt{1 − 2x − 3x^{2}}, it is easy to verify that

\frac{f′(x)}{f(x)} = ∑_{n=0}^{∞} \frac{(−1)^{n}c_{n+1} − 1}{2} x^{n}

and therefore

− log f(x) = ∑_{n=1}^{∞} \frac{(−1)^{n}c_{n} + 1}{2n} x^{n}.

Now define the function

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

which again converges for all x ∈ [0, 1] to a function which is analytic except at x = 2/3. Expanding h(x) into powers of 1 − x gives

h(x) = ∑_{k=1}^{∞} \frac{(3k − 1)!}{k!(2k)!}(1 − x)^{k} ∑_{j=0}^{2k} \binom{2k}{j}(−1)^{j}(1 − x)^{j} =

= ∑_{n=1}^{∞} ( ∑_{k=⌈n/3⌉}^{n} \binom{2k}{n − k}(−1)^{n−k} \frac{(3k − 1)!}{k!(2k)!}) (1 − x)^{n} =

= ∑_{n=1}^{∞} \frac{(1 − x)^{n}}{n} = − log x,

again making use of a verifiable identity [5], namely that

(−1)^{n} ∑_{k=⌈n/3⌉}^{n} \frac{(−1)^{k}(3k − 1)!}{k!(n − k)!(3k − n)!} = \frac{1}{n},  n ≥ 1.  (4)

So h(x) = − log x near x = 1, and therefore because of the symmetry property (3) we have that h(x) = − log f(x) near x = 0. Expanding h(x) in powers of x near x = 0 gives

− log f(x) = h(x) = ∑_{k=1}^{∞} \frac{(3k − 1)!}{k!(2k)!}x^{2k} ∑_{j=0}^{k} \binom{k}{j}(−1)^{j}x^{j} =

= ∑_{n=2}^{∞} ((−1)^{n} ∑_{k=⌈n/3⌉}^{⌊n/2⌋} \frac{(3k − 1)!}{(2k)!(n − 2k)!(3k − n)!}) x^{n}

Equating coefficients with our previous expansion of h(x) gives (2).

Remarks.

1. One obvious question on seeing formulas (1) and (2) is, Can they be explained combinatorially? That is, do there exist bijections between sets known to be enumerated by the numbers m_{n} and c_{n}, and sets whose cardinality is seen to be the right-hand sides of (1) and (2)? Such explanations elude us currently.

2. Identity (4) is a special case of a more general identity [4, Eq. (6)] that was discovered by Thomas Liggett.

3. See [1, 2, 3, 6] for some other formulas involving the central trinomial coefficients and the Motzkin numbers, and for more information on the properties, and the many different combinatorial interpretations, of these sequences.

3 Acknowledgments

Thanks to the anonymous referee for some useful suggestions and references.

References

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

[2] E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family. Pure Math. Appl. Ser. A 2 (1991), 249–279.

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

[4] A. E. Holroyd, D. Romik and T. M. Liggett, Integrals, partitions and cellular automata. To appear in Trans. Amer. Math. Soc.

[5] M. Petkovšek, H. S. Wilf and D. Zeilberger, A = B, A. K. Peters, 1996.

[6] N. J. A. Sloane, editor (2003), The On-Line Encyclopedia of Integer Sequences,

   http://www.research.att.com/˜ njas/sequences/, sequences A002426, A001006.

2000 Mathematics Subject Classification: 05A10, 05A15, 05A19. Keywords: central trinomial coefficients, Motzkin numbers, binomial identities.

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

Received March 25, 2003; revised version received June 20, 2003. Published in Journal of Integer Sequences July 8, 2003.

Return to Journal of Integer Sequences home page.