info prev up next book cdrom email home

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

\end{displaymath} (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,
\end{displaymath} (2)

or by the Recurrence Relation
M_n=a_{n-1}+\sum_{k=0}^{n-2} M_k M_{n-2-k}
\end{displaymath} (3)

with $M_0=1$. The Motzkin number $M_n$ is also given by
$\displaystyle M_n$ $\textstyle =$ $\displaystyle -{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)
  $\textstyle =$ $\displaystyle {(-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},$  

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

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


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.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein