Catalan-számok

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\geq 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

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

$C_{n}={2n \choose n}-{2n \choose n-1},\quad {\mbox{ ahol }}n\geq 1.$

Ebből látszik, hogy C_n 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\geq 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

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 C₃ = 5 esetet mutatják be.

• C_n 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:

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• A fenti X szimbólumot nyitó, Y-t pedig záró zárójelként értelmezve C_n azoknak a kifejezéseknek a számát adja meg, amelyben n db helyesen párosított zárójel szerepel.

((()))     ()(())     ()()()     (())()     (()())

• C_n 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 C_n azoknak rendezett bináris fáknak a száma, amelyeknek n + 1 levelük van:

• C_n 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.)
• C_n 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ó.

• 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. C_n 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”.

• C_n 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:

• C_n 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:

• C_n 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

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

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