Representation of a Lie superalgebra

2014-01-15T13:09:20Z

194.44.37.253:

In [[mathematics]], a '''Motzkin number''' for a given number ''n'' (named after [[Theodore Motzkin]]) is the number of different ways of drawing non-intersecting [[Chord (geometry)|chords]] on a [[circle]] between ''n'' points. The Motzkin numbers have very diverse applications in [[geometry]], [[combinatorics]] and [[number theory]].

Motzkin numbers <math>M_n</math> for <math>n = 0, 1, \dots</math> form the sequence:

: 1, [[1 (number)|1]], [[2 (number)|2]], [[4 (number)|4]], [[9 (number)|9]], [[21 (number)|21]], [[51 (number)|51]], [[127 (number)|127]], 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... {{OEIS|id=A001006}}

== Examples ==

The following figure shows the 9 ways to draw non-intersecting chords between 4 points on a circle.

[[Image:MotzkinChords4.svg]]

The following figure shows the 21 ways to draw non-intersecting chords between 5 points on a circle.

[[Image:MotzkinChords5.svg]]

== Properties ==

Motzkin numbers satisfy the recurrence relation:

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

Motzkin numbers can be expressed in terms of [[binomial coefficient]]s and [[Catalan number]]s:

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

A '''Motzkin prime''' is a Motzkin number that is [[prime number|prime]]. {{Asof|2013|October}}, four such primes are known:

: 2, 127, 15511, 953467954114363 {{OEIS|id=A092832}}

== Combinatorial interpretations ==

The Motzkin number for ''n'' is also the number of positive integer sequences ''n''−1 long 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.

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

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

[[Image:Motzkin4.svg]]

There are at least fourteen different manifestations of Motzkin numbers in different branches of mathematics, as enumerated by {{harvtxt|Donaghey|Shapiro|1977}} in their survey of Motzkin numbers.
{{harvtxt|Guibert|Pergola|Pinzani|2001}} showed that [[vexillary involution]]s are enumerated by Motzkin numbers.

==See also==
*[[Delannoy number]]
*[[Narayana number]]
*[[Schröder number]]

==References==

*{{citation
| last1 = Donaghey
| first1 = R.
| last2 = Shapiro
| first2 = L. W.
| title = Motzkin numbers
| journal = Journal of Combinatorial Theory, Series A
| volume = 23
| issue = 3
| year = 1977
| pages = 291–301
| mr = 0505544
| doi = 10.1016/0097-3165(77)90020-6}}
*{{Citation | last1=Guibert | first1=O. | last2=Pergola | first2=E. | last3=Pinzani | first3=R. | title=Vexillary involutions are enumerated by Motzkin numbers | doi=10.1007/PL00001297 | year=2001 | journal=Annals of Combinatorics | issn=0218-0006 | volume=5 | issue=2 | pages=153–174 | mr=1904383}}
*{{citation
| last = Motzkin
| first = T. S.
| title = Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products
| journal = [[Bulletin of the American Mathematical Society]]
| volume = 54
| year = 1948
| pages = 352–360
| doi = 10.1090/S0002-9904-1948-09002-4
| issue = 4}}

==External links==
*{{MathWorld|title=Motzkin Number|urlname=MotzkinNumber}}

{{Classes of natural numbers}}
[[Category:Integer sequences]]
[[Category:Enumerative combinatorics]]

formulasearchengine - User contributions [en]

Representation of a Lie superalgebra