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 <math>M_n</math> for <math>n = 0, 1, \dots</math> 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 (Template:Math):

File:MotzkinChords4.svg

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

File:MotzkinChords5.svg

Properties

The Motzkin numbers satisfy the recurrence relations

<math>M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_iM_{n-2-i}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}.</math>

The Motzkin numbers can be expressed in terms of binomial coefficients and Catalan numbers:

<math>M_n=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k} C_k,</math>

and inversely,<ref>Template:Cite journal</ref>

<math>C_{n+1}=\sum_{k=0}^{n} \binom{n}{k} M_k</math>

This gives

<math>\sum_{k=0}^{n}C_{k} = 1 + \sum_{k=1}^{n} \binom{n}{k} M_{k-1}.</math>

The generating function <math>m(x) = \sum_{n=0}^\infty M_n x^n</math> of the Motzkin numbers satisfies

<math>x^2 m(x)^2 + (x - 1) m(x) + 1 = 0</math>

and is explicitly expressed as

<math>m(x) = \frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}.</math>

An integral representation of Motzkin numbers is given by

<math>M_{n}=\frac{2}{\pi}\int_0^\pi \sin(x)^2(2\cos(x)+1)^n dx</math>.

They have the asymptotic behaviour

<math>M_{n}\sim \frac{1}{2 \sqrt{\pi}}\left(\frac{3}{n}\right)^{3/2} 3^n,~ n \to \infty</math>.

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

2, 127, 15511, 953467954114363 (sequence A092832 in the 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

• {{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web

|_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:MotzkinNumber%7CMotzkinNumber.html}} |title = Motzkin Number |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}