Catalan-számok (1.)

Szerző:: Tarcsay Tamás

Témák:: Kombinatorika, Számok, Sorozatok és sorok

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 C_n-nel! 2 pontot egyféleképpen lehet párba állítani és összekötni, így C₁=1.

n = 2

C₂=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

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.