TOPICS
Search

Motzkin Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
MotzkinNumber

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., ->, ->, and ->.

The first are 1, 2, 4, 9, 21, 51, ... (OEIS A001006). The numbers of decimal digits in M_(10^n) for n=0, 1, ... are 1, 4, 45, 473, 4766, 47705, 477113, ... (OEIS A114473), where the digits approach those of log_(10)3=0.4771212547... (OEIS A114490).

The first few prime Motzkin numbers are 2, 127, 15511, 953467954114363, ... (OEIS A092832), which correspond to indices 2, 7, 12, 36, ... (OEIS A092831), with no others for n<=263000 (Weisstein, Mar. 29, 2005).

The Motzkin number generating function M(x) satisfies

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

and is given by

M(x)=(1-x-sqrt(1-2x-3x^2))/(2x^2)
(2)
=2/(1-x+sqrt(1-2x-3x^2))
(3)
=1+x+2x^2+4x^3+9x^4+21x^5+....
(4)

M(x) therefore is given by the continued fraction

M(x)=1/(1-x-(x^2)/(1-x-(x^2)/(1-x-(x^2)/...)))
(5)

(M. Somos, pers. comm., Apr. 15, 2006).

They are given by the recurrence relation

M_n=(3(n-1)M_(n-2)+(2n+1)M_(n-1))/(n+2)
(6)

with M_0=M_1=1, as well as the nested recurrence

M_n=M_(n-1)+sum_(k=0)^(n-2)M_kM_(n-2-k)
(7)

with M_0=1.

The Motzkin number M_n is also given by

M_n=-1/2sum_(a=0)^(n+2)(-3)^k(1/2; a)(1/2; b)
(8)
=((-1)^(n+1))/(2^(2n+5))sum_(a=0)^(n+2)((-3)^a)/((2a-1)(2b-1))(2a; a)(2b; b)
(9)
=_2F_1(1/2(1-n),-1/2n;2;4)
(10)
=1/(n+1)(n+1; 1)_2
(11)
=-(sqrt(pi)_2F^~_1(-1/2,-n-2;-n-1/2;-3))/(4Gamma(n+3))
(12)
=(i^n3^(n/2))/2[3P_n(-1/3isqrt(3))+2isqrt(3)P_(n+1)(-1/3isqrt(3))+3P_(n+2)(-1/3isqrt(3))],
(13)

where b=n+2-a, (n; k) is a binomial coefficient, (n; k)_2 is a trinomial coefficient, _2F_1(a,b;c;z) is a hypergeometric function, _2F^~_1(a,b;c;z) is a regularized hypergeometric function, Gamma(z) is a gamma function, and P_n(z) is a Legendre polynomial.

See also

Catalan Number, Delannoy Number, Integer Sequence Primes, Schröder Number, Trinomial Coefficient

Explore with Wolfram|Alpha

References

Barcucci, E.; Pinzani, R.; and Sprugnoli, R. "The Motzkin Family." Pure Math. Appl. Ser. A 2, 249-279, 1991.Dickau, R. M. "Delannoy and Motzkin Numbers." http://www.prairienet.org/~pops/delannoy.html.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. Sequences A001006/M1184, A092831, A092832, A114473, and A114490 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Motzkin Number

Cite this as:

Weisstein, Eric W. "Motzkin Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MotzkinNumber.html

Subject classifications