Catalan-számok

A Wikipédiából, a szabad enciklopédiából
(Catalan-szám szócikkből átirányítva)

A kombinatorikában a Catalan-számok egy természetes számokból álló sorozatot alkotnak, amely több, legtöbbször rekurziót tartalmazó probléma megoldásakor lép fel.

Az n-edik Catalan-szám a következőképpen számítható ki:

C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}, \qquad\mbox{ ahol }n\ge 0.

Az első néhány Catalan-szám (A000108 sorozat az OEIS-ben) n = 0, 1, 2, 3, … esetén a következő:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

A sorozat nevét Eugène Charles Catalan (1814–1894) belga matematikusról kapta.

Tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

Cn kiszámításának alternatív módja a

C_n = {2n\choose n} - {2n\choose n-1}, \quad\mbox{ ahol }n\ge 1.

Ebből látszik, hogy Cn természetes szám, amely a fent megadott első képletből nem állapítható meg azonnal. Ez a második képlet szolgál André bizonyításának alapjául. Lásd második bizonyítás).

A Catalan-számok kiszámíthatóak az alábbi rekurzív sorozat segítségével:

C_0 = 1 \quad \mathrm{\acute{e}s} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i},\quad\mbox{ahol }n\ge 0.

Továbbá igaz rájuk, hogy:

C_0 = 1 \quad \mathrm{\acute{e}s} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

amely sokszor egyszerűbb mód az adott érték kiszámítására.

Csak azok a C_n Catalan-számok páratlanok, ahol igaz, hogy n=2^k-1, az összes többi páros.

Alkalmazása kombinatorikai problémákra[szerkesztés | forrásszöveg szerkesztése]

Számos kombinatorikai probléma megoldása során alkalmazhatóak a Catalan-számok. Richard P. Stanley Enumerative Combinatorics című könyvének második kötete a Catalan-számok 66 különbözőféle értelmezésére tartalmaz példákat. Az alább néhány alkalmazási példa olvasható; az ábrák a C3 = 5 esetet mutatják be.

  • Cn a 2n hosszúságú Dyck-szavak száma. A Dyck-szó olyan karakterlánc amelyben n db X és n db Y szerepel oly módon, hogy a szó semelyik kezdeti szakaszában nincs több Y mint X. Lásd még Dyck nyelv. Példaként a 6 karakter hosszúságú Dyck-szavak:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
  • A fenti X szimbólumot nyitó, Y-t pedig záró zárójelként értelmezve Cn azoknak a kifejezéseknek a számát adja meg, amelyben n db helyesen párosított zárójel szerepel.
((()))     ()(())     ()()()     (())()     (()())
  • Cn azt a számot adja meg, amennyiféleképpen n+1 szorzótényezőt zárójelezhetünk egyértelműen. Általánosabban annak a száma, ahányféleképpen egy bináris műveletet n-szer alkalmazhatunk. Például n = 3 esetén az alábbi 5 módon zárójelezhetjük a szorzótényezőket:
((ab)c)d \quad (a(bc))d \quad(ab)(cd) \quad a((bc)d) \quad a(b(cd))
  • Egy bináris művelet egymásutáni alkalmazásait leírhatjuk egy bináris fa segítségével is. Ebből következően a Cn azoknak rendezett bináris fáknak a száma, amelyeknek n + 1 levelük van:
Catalan number binary tree example.png
  • Cn az n+1 csúcson megadott egymással nem izomorf rendezett fák száma. (A rendezett fa olyan gyökeres fa, amelyben a csúcsok leszármazottai között valamilyen sorrendet értelmezünk, tehát beszélünk első, második stb. leszármazottról. Ez a sorrend általában a balról jobbra való rendezés.)
  • Cn megadja egy n × n-es négyzetrács élein haladó azon monoton utak számát, melyek nem lépik át az átlót. Monoton úton olyan utat értünk, mely a bal alsó sarokban kezdődik, a jobb felső sarokban végződik, és fölfelé vagy jobbra mutató éleken vezet. Másképp megfogalmazva az út mentén haladva a rácspontokon mind az x, mind az y koordináták sorozata monoton növekvő. Ez a számolási mód ekvivalens a Dyck-szavak számolásával, ahol X jelenti a „jobbra lépést”, Y pedig a „felfele lépést”. A következő ábrán az n=4 eset látható.
Catalan number 4x4 grid example.svg
  • A fentivel ekvivalens megfogalmazási mód: Egy mozi pénztáránál 2n ember áll sorba az 1000 Ft-os jegyekért. Közülük n-nek 1000 Ft-os, n-nek 2000 Ft-os bankjegye van. A kasszában nincs váltópénz. Cn megadja, hogy hány olyan sorrendje van az embereknek, amikor a sor nem akad el, azaz a pénztáros mindig tud visszaadni. Az előző pontban vázolt számolási módot alkalmazva: egy 1000 Ft-os ember jelenti a „jobbra lépést”, egy 2000 Ft-os pedig a „felfele lépést”.
  • Cn az n + 2 oldalú konvex sokszög háromszögeléseinek (egymást nem metsző átlókkal való háromszögekre bontása) száma. Az alábbi hatszögek az n=4 esetet szemléltetik:
Catalan-Hexagons-example.svg
  • Cn megadja, hogy egy n magasságú lépcsőzetes alakzat hányféle csempézése (átfedés- és hézagmentes lefedés) adható meg n db téglalappal. A következő ábra az n=4 esetet mutatja be:
Catalan stairstep 4.png
  • Cn az {1, ..., n} számok olyan permutációinak száma, amik elkerülik az 123 mintát (vagy bármely egyéb 3 hosszúságú mintát); azaz megadja az olyan permutációk számát, melyekben nincs 3 hosszú növekvő részsorozat. Ezek a permutációk n=3 esetén az 132, 213, 231, 312 és 321; n=4-re pedig az 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 és 4321.

Története[szerkesztés | forrásszöveg szerkesztése]

A Catalan-sorozatot először Leonhard Euler írta le a 18. században, mikor azt vizsgálta, hányféleképpen lehet háromszögekre bontani egy sokszöget. Nevét Eugène Charles Catalan belga matematikusról kapta, aki felismerte a sorozat zárójelezett kifejezésekkel való kapcsolatát, miközben a hanoi tornyok problémáját vizsgálta. Alkalmazását a Dyck-szavak számolására D. André írta le 1887-ben.

További információk[szerkesztés | forrásszöveg szerkesztése]