Catalan-számok
2014/08/04 08:00
1080 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.

A matematika nevezetes számai közül a Fibonacci-számokat szinte mindenki ismeri. A Catalan-számok szinte ismeretlenek, pedig az ő atyjuk Leonhard Euler - ő írta le a számokat a XVIII. században, mikor azt vizsgálta, hányféleképpen lehet háromszögekre bontani egy sokszöget.

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?

autotolatás

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égekLehetőségek száma
01
a1
ab, ba2
abc, bca, cab, bac, cba5
abcd, bcda, bcad, cdab, cdba, bacd, bcda, cabd, cbad, dabc, dbca, dbac, dcab, dcba14

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

tabela5

Oldalak száma3456789
Hányféleképpen bontható fel háromszögekre1251442132429

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:

formula_cat

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:

Zsigó Zsolt cikke

Csoportot ajánlunk

Kapcsolódó oldalak

Scientix A természettudományos oktatás közössége
All you need is code Minden a kódolás tanulásáról
A National Geographic A National Geographic honlapja.
Interpress Magazin Az IPM honlapja archívummal
Világtudomány.hu A magyar és nemzetközi tudományos élet hírei
Űr világ Asztronautikai hírportál