Catalan-számok elemi tárgyalása

Alternatív definíciók

Definíció: Tn={konvex sokszög n háromszöges triangulációi}= {(n+2)-szög triangulációi}

Példa: T4 elemeinek listája:

Definíció: Bn={n belső ponttal rendelkező gyökeres bináris síkfák}= {2n éllel rendelkező gyökeres bináris síkfák}=

Példa: B4 elemeinek listája:

Definíció: Dn={2n lépéses Dyck-utak}

Példa: D4 elemeinek listája:

Tétel: |Tn|=|Bn|=|Dn|.

Bizonyítás: A három halmaz között bijekció adható meg.

Megjegyzés: Ezek alapján a Catalan-számoknak három alternatív definíciója is adható. Ezek mellett további más ekvivalens definíciója is van. Ezek a definíciók közül sok elérhető az interneten.

A legteljesebb listája a Catalan-számok alternatív definícióinak Richard Stanley alapvető fontosságú Enumertaive Combinatorics könyvében szerepel egy feladatsorozatként.


Dyck-utak megszámlálása tükrözési trükkel


Polinomiális rekurziók