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 (, 0) which never dip below and are made up only of the steps (1, 0), (1, 1), and (1, ), i.e., , , and .

The first are 1, 2, 4, 9, 21, 51, ... (OEIS A001006). The numbers of decimal digits in for , 1, ... are 1, 4, 45, 473, 4766, 47705, 477113, ... (OEIS A114473), where the digits approach those of (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 (Weisstein, Mar. 29, 2005).

The Motzkin number generating function satisfies

(1)

and is given by

			(2)
			(3)
			(4)

therefore is given by the continued fraction

(5)

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

They are given by the recurrence relation

(6)

with , as well as the nested recurrence

(7)

with .

The Motzkin number is also given by

			(8)
			(9)
			(10)
			(11)
			(12)
			(13)

where , is a binomial coefficient, is a trinomial coefficient, is a hypergeometric function, is a regularized hypergeometric function, is a gamma function, and is a Legendre polynomial.