Catalan-számok (1.)
KöMaL Gy. 2947. alapján
http://db.komal.hu/KomalHU/felhivatkoz.phtml?id=41664
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]](https://beta.geogebra.org/resource/sa92twmt/fTfbRlpt8rzevkHX/material-sa92twmt.png)
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.