Motzkin-számok

A matematika területén egy adott n természetes számhoz tartozó Motzkin-szám azt határozza meg, hogy egy körön elhelyezkedő n pont között hányféleképpen lehet egymást nem metsző húrokat rajzolni (nem feltétlenül minden pontba húrt rajzolva). A Motzkin-féle számokat Theodore Motzkin 20. századi matematikusról nevezték el, és a matematika nagyon távol eső területein alkalmazzák őket, köztük a geometriában, a kombinatorikában és a számelméletben.

A Motzkin-számok $M_n$ $n=0,1,\dots$-re a következő sorozatot alkotják:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... Sablon:OEIS

Példák

A következő ábrán látható a körön lévő 4 pont összesen 9 összekötési módja.

A következő ábrán látható a körön lévő 5 pont összesen 21 metszésmentes összekötési módja.

Tulajdonságai

A Motzkin-számok megfelelnek a következő rekurzív relációnak:

$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}.$

A Motzkin-számok kifejezhetők binomiális együtthatók és Catalan-számok segítségével:

$M_n=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{2k})C_k.$

A Motzkin-prím olyan Motzkin-szám, ami egyben prímszám. 2013 októberében négy ilyen prímszám volt ismeretes:

2, 127, 15511, 953467954114363 Sablon:OEIS

Kombinatorikai értelmezései

Az n-hez tartozó Motzkin-szám azoknak az n−1 hosszúságú, pozitív egészekből álló sorozatoknak a száma, melyeknél a legelső és legutolsó elem 1 vagy 2, és a két egymást követő elem közötti különbség −1, 0 vagy 1.

Egy négyzetrács jobb felső kvadránsában az n-hez tartozó Motzkin-szám megadja a (0, 0) és (n, 0) koordináták közötti n lépéshosszúságú útvonalaknak a számát, ha minden lépésben jobbra kell haladni (egyenesen, srégen felfelé vagy lefelé), de nem szabad az y = 0 tengely alá lemenni.

A következő ábra megmutatja a (0, 0) és a (4, 0) koordináták között vezető 9 érvényes Motzkin-útvonalat:

A matematika különböző területein a Motzkin-számoknak legalább 14 különböző megjelenési formájuk van, amint azt Donaghey és Shapiro 1977-es felmérésükben megállapították. in their survey of Motzkin numbers. Guibert, Pergola és Pinzani 2001-ben megmutatták, hogy a zászlószerű involúciók számát is a Motzkin-számok határozzák meg.

Kapcsolódó szócikkek

• Delannoy-szám
• Narayana-szám
• Schröder-szám

Jegyzetek

• Sablon:Citation
• Sablon:Citation

Fordítás

• Sablon:Fordítás

További információk

• Sablon:MathWorld