Catalan-számok – Wikipédia
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:
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]Cn kiszámításának alternatív módja a
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:
Továbbá igaz rájuk, hogy:
amely sokszor egyszerűbb mód az adott érték kiszámítására.
Csak azok a Catalan-számok páratlanok, ahol igaz, hogy , az összes többi páros.
Alkalmazása kombinatorikai problémákra
[szerkesztés]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 kezdőszeletében nincs több Y mint X. Lásd még: Dyck-nyelv. Példaként a 6 karakter hosszúságú Dyck-szavak:
- 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:
- 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:
![](http://upload.wikimedia.org/wikipedia/commons/0/01/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ó.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Catalan_number_4x4_grid_example.svg/450px-Catalan_number_4x4_grid_example.svg.png)
- 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:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Catalan-Hexagons-example.svg/400px-Catalan-Hexagons-example.svg.png)
- 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:
![](http://upload.wikimedia.org/wikipedia/commons/c/cb/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]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]- Stanley, Richard P.: Catalan addendum to Enumerative Combinatorics, Volume 2
- Mathworld article on Catalan numbers.
- A000108 Catalan numbers on the On-Line Encyclopedia of Integer Sequences
- Dickau, Robert M.: Catalan numbers Further examples.
- Davis, Tom: Catalan numbers. Still more examples.