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

MotzkinChords4.svg

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

MotzkinChords5.svg

Tulajdonságai

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

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

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:

Motzkin4.svg

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

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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

Uses material from the Wikipedia article Motzkin-számok, released under the CC BY-SA 3.0 license.