In mathematics, the nth Motzkin number is the number of different ways of drawing non-intersecting chords between n points on a circle (not necessarily touching every point by a chord). The Motzkin numbers are named after Theodore Motzkin and have diverse applications in geometry, combinatorics and number theory. The Motzkin numbers M n {\displaystyle M_{n}} for n = 0 , 1 , … {\displaystyle n=0,1,\dots } form the sequence:
1, 1, 2, 4, 9, 21, 51, 127, 323, 835, ... (sequence A001006 in the OEIS)
Examples The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle (M4 = 9):
The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle (M5 = 21):
Properties The Motzkin numbers satisfy the recurrence relations
M n = M n − 1 + ∑ i = 0 n − 2 M i M n − 2 − i = 2 n + 1 n + 2 M n − 1 + 3 n − 3 n + 2 M n − 2 . {\displaystyle M_{n}=M_{n-1}+\sum _{i=0}^{n-2}M_{i}M_{n-2-i}={\frac {2n+1}{n+2}}M_{n-1}+{\frac {3n-3}{n+2}}M_{n-2}.}
The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:
M n = ∑ k = 0 ⌊ n / 2 ⌋ ( n 2 k ) C k , {\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k},}
and inversely,
C n + 1 = ∑ k = 0 n ( n k ) M k {\displaystyle C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}}
This gives
∑ k = 0 n C k = 1 + ∑ k = 1 n ( n k ) M k − 1 . {\displaystyle \sum _{k=0}^{n}C_{k}=1+\sum _{k=1}^{n}{\binom {n}{k}}M_{k-1}.}
The generating function m ( x ) = ∑ n = 0 ∞ M n x n {\displaystyle m(x)=\sum _{n=0}^{\infty }M_{n}x^{n}} of the Motzkin numbers satisfies
x 2 m ( x ) 2 + ( x − 1 ) m ( x ) + 1 = 0 {\displaystyle x^{2}m(x)^{2}+(x-1)m(x)+1=0}
and is explicitly expressed as
m ( x ) = 1 − x − 1 − 2 x − 3 x 2 2 x 2 . {\displaystyle m(x)={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.}
An integral representation of Motzkin numbers is given by
… excerpt ends here. Continue reading the full article.
