Motzkin Number

The Motzkin number , for a nonnegative integer , counts the lattice paths from (0, 0) to (, 0) which never dip below and use only the steps (1, 0), (1, 1), and (1, ), i.e., , , and . Donaghey and Shapiro (1977) give 14 different combinatorial interpretations of these numbers.

For , 1, 2, ..., the first values are 1, 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 decimal expansion of the digit count divided by approaches that of (OEIS A114490).

Inagaki and Luo (2026) proved that counts the 2-stack-sortable permutations of ending in 0, for every . Here, 2-stack-sortable means that at most two applications of the deterministic stack-sorting map put the permutation in increasing order.

The first few prime Motzkin numbers are 2, 127, 15511, 953467954114363, ... (OEIS A092832), which correspond to indices 2, 7, 12, 36, ... (OEIS A092831). S. Batalov reported that the next index, if it exists, exceeds (Feb. 2, 2022).

The Motzkin number generating function satisfies

(1)

and is given by

			(2)
			(3)
			(4)

If is the th Riordan number, then

(5)

(Bernhart 1999).

therefore is given by the continued fraction

(6)

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

They are given by the recurrence relation

(7)

for , with , as well as the nested recurrence relation

(8)

for , with and an empty sum when .

The Motzkin number is also given by

					(9)
					(10)
					(11)
					(12)
					(13)
					(14)

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.