Motzkin-számok

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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.[1] 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.[2]

Kapcsolódó szócikkek[szerkesztés]

Jegyzetek[szerkesztés]

  1. Donaghey, R. & Shapiro, L. W. (1977), "Motzkin numbers", Journal of Combinatorial Theory, Series A 23 (3): 291–301, DOI 10.1016/0097-3165(77)90020-6
  2. Guibert, O.; Pergola, E. & Pinzani, R. (2001), "Vexillary involutions are enumerated by Motzkin numbers", Annals of Combinatorics 5 (2): 153–174, ISSN 0218-0006, DOI 10.1007/PL00001297

Fordítás[szerkeszté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.

További információk[szerkesztés]