A Catalan számokkal, vagy más néven a Catalan-sorozattal először Leonard Euler egyik munkájában találkozhatunk. Euler ebben azt vizsgálta, hogy hányféleképpen lehet háromszögekre bontani egy sokszöget. Mint a tudományos életben már sok esetben előfordult, ezt a sorozatot mégsem róla, hanem Eugène Charles Catalan belga matematikusról nevezték el. Catalan ismerte fel először ugyanis, hogy ezek a számok több problémára is közös megoldást adnak. Richard P. Stanley Enumerative Combinatorics című, 1999-ben megjelent munkájában 66 különböző definíciót adott a Catalan-számokra. Stanley nem ismeretlen magyar matematikus körökben, hiszen 1975-ben Pólya György díjat kapott, és nála volt doktorandusz három magyar matematikus is (Hetyei Gábor, Bóna Miklós és Mészáros Karola).
Az udvarias sofőr esete
Nézzünk egy példát. A járművek egy nagyon szűk, egysávos úton haladhatnak, ahol nem tudnak előzni. Az úthoz csatlakozik egy mellékút, ahová kiállhat az az autós, aki szeretné elengedni sietős társait. Ha még van olyan sofőr, aki szeretne kiállni, akkor ezen szúk mellékúton ő is megteheti, természetesen aki először kiállt, az egyre hátrébb kerül ebben a sorban.
A kérdés, hogy hány különböző sorrendben érkezhet meg az n db autó a szűk útszakasz végéhez?
Az autókat a, b, c-vel jelöltük az úton balról jobbra. A megérkező autósokat jobbról balra követjük figyelemmel!
| Lehetőségek | Lehetőségek száma |
| 0 | 1 |
| a | 1 |
| ab, ba | 2 |
| abc, bca, cab, bac, cba | 5 |
| abcd, bcda, bcad, cdab, cdba, bacd, bcda, cabd, cbad, dabc, dbca, dbac, dcab, dcba | 14 |
Euler alapfeladata - Háromszögekre bontás
Hányféleképpen lehet az n+2 szöget átlókkal háromszögre bontani? (Egy konvex sokszög egymást nem metsző átlókkal történő háromszögekre bontása.)
| Oldalak száma | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Hányféleképpen bontható fel háromszögekre | 1 | 2 | 5 | 14 | 42 | 132 | 429 |
Az első néhány Catalan-számot felírhatjuk a következőképpen: n=1, 2, ... esetén 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
Az n. Catalan-szám meghatározható a következő formula alapján:
Mire jók a Catalan-számok?
Az átlagos honpolgár valószínűleg nem tud sok mindent kezdeni velük. Néhány olyan alkalmazása létezik azonban, amit a számítástudomány használ:
Ha adott n, akkor Cn Catalan-szám:
- az n-csúcsú bináris fák száma,
- azon módok száma, ahányféleképpen lehet zárójelezni n+1, adott sorrendű számot, hogy kettesével összeszorozzuk őket,
- az n műveletet és n + 1 operandust tartalmazó (fordított) lengyel alakban felírt helyes kifejezések száma,
- egy rács (0,0) és (n,n) pontjai között húzható, főátlót át nem lépő, csak vízszintes és függőleges rács éleken haladó utak száma,
- a sík 2n pontját összekötő egymást nem metsző szakaszok száma,
- egy n+2 csúcsú sokszög n háromszögre való felosztásainak száma.
További érdekes oldalak:
- Nevezetes számok a matematikában
- Catalan számok
- Wikipédia - Catalan-számok
- A Surreptitious Sequence: The Catalan Numbers
Zsigó Zsolt cikke
