Motzkin Number

The Motzkin numbers enumerate various combinatorial objects. Donaghey and Shapiro (1977) give 14 different manifestations of these numbers. In particular, they give the number of paths from (0, 0) to ($n$, 0) which never dip below $y=0$ and are made up only of the steps (1, 0), (1, 1), and (1, $-1$), i.e., $\rightarrow$, $\nearrow$, and $\searrow$. The first are 1, 2, 4, 9, 21, 51, ... (Sloane's A001006). The Motzkin number Generating Function $M(z)$ satisfies

$$M=1+xM+x^2M^2$$ (1)

and is given by

$$M(x)={1-x-\sqrt{1-2x-3x^2}\over 2x^2}=1+x+2x^2+4x^3+9x^4+21x^5+\ldots,$$ (2)

or by the Recurrence Relation

$$M_n=a_{n-1}+\sum_{k=0}^{n-2} M_k M_{n-2-k}$$ (3)

with $M_0=1$. The Motzkin number $M_n$ is also given by

$$M_n = -{1\over 2}\sum_{\scriptstyle a+b=n+2\atop\scriptstyle a\geq 0, b\geq 0} (-3)^a{{\textstyle{1\over 2}}\choose a}{{\textstyle{1\over 2}}\choose b}$$ (4)

$$= {(-1)^{n+1}\over 2^{2n+5}}\sum_{\scriptstyle a+b=n+2\atop\scriptstyle a\geq 0, b\geq 0} {(-3)^a\over(2a-1)(2b-1)}{2a\choose a}{2b\choose b},$$ (5)

where ${n\choose k}$ is a Binomial Coefficient.

See also Catalan Number, King Walk, Schröder Number

References

Barcucci, E.; Pinzani, R.; and Sprugnoli, R. ``The Motzkin Family.'' Pure Math. Appl. Ser. A 2, 249-279, 1991.

Donaghey, R. ``Restricted Plane Tree Representations of Four Motzkin-Catalan Equations.'' J. Combin. Th. Ser. B 22, 114-121, 1977.

Donaghey, R. and Shapiro, L. W. ``Motzkin Numbers.'' J. Combin. Th. Ser. A 23, 291-301, 1977.

Kuznetsov, A.; Pak, I.; and Postnikov, A. ``Trees Associated with the Motzkin Numbers.'' J. Combin. Th. Ser. A 76, 145-147, 1996.

Motzkin, T. ``Relations Between Hypersurface Cross Ratios, and a Combinatorial Formula for Partitions of a Polygon, for Permanent Preponderance, and for Nonassociative Products.'' Bull. Amer. Math. Soc. 54, 352-360, 1948.

Sloane, N. J. A. Sequence A001006/M1184 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.