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, ... (A001006 sorozat az OEIS-ben)

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 }{\binom {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 (A092832 sorozat az OEIS-ben)

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

• Bernhart, Frank R (1999), "Catalan, Motzkin, and Riordan numbers", Discrete Mathematics 204 (1-3): 73–112, DOI 10.1016/S0012-365X(99)00054-0
• Motzkin, T. S. (1948), "Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products", Bulletin of the American Mathematical Society 54 (4): 352–360, DOI 10.1090/S0002-9904-1948-09002-4

Fordítás

• Ez a szócikk részben vagy egészben a Motzkin number című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Weisstein, Eric W.: Motzkin Number (angol nyelven). Wolfram MathWorld