Catalan-számok (1.)

KöMaL Gy. 2947. alapján

Egy félsík határoló egyenesén adott 2n darab pont. Hányféleképpen lehet a pontokat párba állítani úgy, hogy az egymással párba állított pontok összeköthetők legyenek a félsík belsejében haladó, egymást nem metsző vonalakkal? Jelöljük a keresett számot Cn-nel! 2 pontot egyféleképpen lehet párba állítani és összekötni, így C1=1.

n = 2

C2=2

n=4

Rekurzió:

Ha megállapodunk abban, hogy , akkor a következő rekurzió sejthető meg: Az igazolás történhet úgy, hogy a jó párosításokat aszerint csoportosítjuk, hogy a az 1. pontot melyik ponttal kötjük össze. Nyilvánvaló, hogy az 1. pontot olyan pontokkal köthetjük össze, hogy a összekötésen belül páros sok pont maradjon. Ebből következően az 1. pontot a 4,, 6., ..., 2n. pontokkal köthetjük össze. az összekötéseken belül a korábbi számú összekötések lehetségesek.

Catalan-számok

A sorozat tagjait Catalan-számoknak nevezzük. Az első néhány Catalan-szám itt található.

2. probléma

Hányféleképpen juthatunk el a Descartes-féle koordinátarendszer origójából az pontba, úgy, hogy minden lépésben egyet "jobbra" vagy egyet "felfelé" léphetünk úgy, hogy nem léphetünk olyan pontba, aminek első koordinátája nagyobb, mint a második koordinátája? .

Lépegessünk!

Jő lépés sorrendek

n = 1  1 db n = 2  2 db n = 3  5 db
A lépegetéseknél és a speciális esetekben vizsgált jó sorrendeknél tapasztaltak alapján gondolható, hogy a két probléma között kapcsolatot lehet felfedezni. A Gy.2947. minden jó párba állításához kölcsönösen egyértelműen hozzárendelhető egy jó lépés sorrend a 2. problémából és viszont. Az összekötések kezdőpontjához rendeljük a "felfelé" lépést a végpontjához pedig a "jobbra" lépést. Ennek következtében e probléma megoldásai is a Catalan-számok.

3. probléma

A Gy. 2947. feladatban szereplő 2n pont közül n-et pirosra festjük. Hányféleképpen tehetjük meg ezt? Az ismétlés nélküli kombinációról tanultak szerint a kifestések száma: Vizsgáljuk az F és C sorozatok első néhány tagját!
[size=85]Észre lehet venni valamilyen kapcsolatot a két sorozat tagjai között?[/size]
Észre lehet venni valamilyen kapcsolatot a két sorozat tagjai között?

Sejtés

A fentiekben látott rekurzióval és teljes indukcióval a sejtés igazolható?

Hanyag pénztáros

Egy moziban a jegyek egységesen 1000 forintba kerülnek. A lusta/hanyag pénztáros nem törődik azzal, hogy felkészüljön a munkájára, így váltópénz nélkül kezdi a napot. Nyitáskor 2n ember áll sorban a pénztár előtt, n-nél egy darab kétezres, n-nélegy darab ezres van. Hányféleképpen állhatnak sorba úgy, hogy mindenki tud jegyet venni? Ha az ezreseknek megfeleltetjük a 2. probléma "felfelé" lépéseit, a kétezreseknek megfeleltetjük a "jobbra" lépéseket, akkor láthatjuk, hogy ennek a problámának is a megoldási a Catalan-számok.