Motzkin number

Template:Short description Template:Infobox integer sequence In mathematics, the Template:Mvarth Motzkin number is the number of different ways of drawing non-intersecting chords between Template:Mvar 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$ for $n=0,1,\dots$ form the sequence:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, ... Template:OEIS

Examples

The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle (Template:Math):

Error creating thumbnail:

The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle (Template:Math):

Properties

The Motzkin numbers satisfy the recurrence relations

$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=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{2k})C_k,$

and inversely,

$C_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})M_k$

This gives

$\sum _{k=0}^n{C}_k=1+\sum _{k=1}^n(\genfrac{}{}{0ex}{}{n}{k})M_{k-1}.$

The generating function $m(x)=\sum _{n=0}^{\mathrm{\infty }}{M}_n{x}^n$ of the Motzkin numbers satisfies

$x^{2}m(x{)}^2+(x-1)m(x)+1=0$

and is explicitly expressed as

$m(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.$

An integral representation of Motzkin numbers is given by

$M_n=\frac{2}{\pi }\underset{0}{\overset{\pi }{\int }}\sin (x{)}^2(2\cos (x)+1{)}^{n}dx$.

They have the asymptotic behaviour

$M_n\sim \frac{1}{2\sqrt{\pi }}{\left(\frac{3}{n}\right)}^{3/2}{3}^n,n\to \mathrm{\infty }$.

A Motzkin prime is a Motzkin number that is prime. Four such primes are known:

2, 127, 15511, 953467954114363 Template:OEIS

Combinatorial interpretations

The Motzkin number for Template:Mvar is also the number of positive integer sequences of length Template:Math in which the opening and ending elements are either 1 or 2, and the difference between any two consecutive elements is −1, 0 or 1. Equivalently, the Motzkin number for Template:Mvar is the number of positive integer sequences of length Template:Math in which the opening and ending elements are 1, and the difference between any two consecutive elements is −1, 0 or 1.

Also, the Motzkin number for Template:Mvar gives the number of routes on the upper right quadrant of a grid from coordinate (0, 0) to coordinate (Template:Mvar, 0) in Template:Mvar steps if one is allowed to move only to the right (up, down or straight) at each step but forbidden from dipping below the Template:Mvar = 0 axis.

For example, the following figure shows the 9 valid Motzkin paths from (0, 0) to (4, 0):

File:Motzkin4.svg

There are at least fourteen different manifestations of Motzkin numbers in different branches of mathematics, as enumerated by Template:Harvtxt in their survey of Motzkin numbers. Template:Harvtxt showed that vexillary involutions are enumerated by Motzkin numbers.

See also

• Telephone number which represent the number of ways of drawing chords if intersections are allowed
• Delannoy number
• Narayana number
• Schröder number

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation

External links

• Template:MathWorld