[size=85][url=http://db.komal.hu/KomalHU/felhivatkoz.phtml?id=41664]http://db.komal.hu/KomalHU/felhivatkoz.phtml?id=41664[/url][br]Egy félsík határoló egyenesén adott 2[i]n[/i] 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?[br][/size][size=85]Jelöljük a keresett számot [i]C[sub]n[/sub][/i]-nel![br][/size][size=85]2 pontot egyféleképpen lehet párba állítani és összekötni, így [i]C[sub]1[/sub][/i]=1.[/size]

[size=85][i]C[sub]2[/sub][/i]=2[/size]

[math]C_3=C_2+C_1\cdot C_1+C_2=2+1\cdot1+2=5[/math]

[math]C_4=C_3+C_1\cdot C_2+C_2\cdot C_1+C_3=5+1\cdot2+2\cdot1+5=14[/math]

[size=85]Ha megállapodunk abban, hogy [math]C_0=1[/math][/size], [size=85]akkor a következő rekurzió sejthető meg:[br][/size][math]C_{n+1}=C_0\cdot C_n+C_1\cdot C_{n-1}+C_2\cdot C_{n.-2}+...+C_{n-1}\cdot C_1+C_n\cdot C_0[/math][br][size=85]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., ..., 2[i]n. [/i]pontokkal köthetjük össze. az összekötéseken belül a korábbi számú összekötések lehetségesek.[/size]

A [math]C_n[/math] [size=85]sorozat tagjait [url=https://en.wikipedia.org/wiki/Eug%C3%A8ne_Charles_Catalan]Catalan[/url]-számoknak nevezzük. Az első néhány Catalan-szám [url=https://oeis.org/A000108]itt található[/url].[/size]

[size=85][url=https://www.komal.hu/feladat?a=feladat&f=B4928&l=hu]Hányféleképpen juthatunk [/url]el a Descartes-féle koordinátarendszer origójából az [math]\left\langle n;n\right\rangle[/math][/size] [size=85]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? [math]n\in\mathbb{Z}^+[/math][/size].

[size=85][i]n[/i] = 1 [math]\wedge\longrightarrow[/math][/size] [b][size=85]1 db[/size][br][/b][size=85][i]n [/i]= 2 [math]\wedge\wedge\longrightarrow\longrightarrow[/math][/size] [math]\wedge\longrightarrow\wedge\longrightarrow[/math] [b][size=85]2 db[br][/size][/b][size=85][i]n [/i]= 3 [math]\wedge\wedge\wedge\longrightarrow\longrightarrow\longrightarrow[/math][/size] [math]\wedge\wedge\longrightarrow\wedge\longrightarrow\longrightarrow[/math] [math]\wedge\wedge\longrightarrow\longrightarrow\wedge\longrightarrow[/math] [math]\wedge\longrightarrow\wedge\wedge\longrightarrow\longrightarrow[/math] [math]\wedge\longrightarrow\wedge\longrightarrow\wedge\longrightarrow[/math] [size=85][b]5 db[/b][/size]

[size=85]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. [br][/size][size=85]Ennek következtében e probléma megoldásai is a Catalan-számok.[/size]

[size=85]A Gy. 2947. feladatban szereplő 2[i]n[/i] pont közül [i]n[/i]-et pirosra festjük. Hányféleképpen tehetjük meg ezt?[br][br][/size][size=85]Az ismétlés nélküli kombinációról tanultak szerint a kifestések száma: [math]F_n=\binom{2n}{n}[/math][br][/size][size=85]Vizsgáljuk az [i]F[/i] és [i]C[/i] sorozatok első néhány tagját![/size]

[math]\left\langle n+1\right\rangle\cdot C_n=F_n[/math][br][math]\left\langle n+1\right\rangle\cdot C_n=\binom{2n}{n}[/math][br][math]C_n=\frac{\binom{2n}{n}}{n+1}[/math][br][math]C_n=\frac{\left\langle2n\right\rangle!}{n!\cdot\left\langle n+1\right\rangle!}[/math] [math]=\binom{2n}{n}-\binom{2n}{n-1}[/math][br][size=85]A fentiekben látott rekurzióval és teljes indukcióval a sejtés igazolható[b]?[/b][/size]

[size=85]Egy moziban a jegyek egységesen 1000 forintba kerülnek. A [url=https://www.geogebra.org/m/vw3sdjbs]lusta/hanyag pénztáros[/url] 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 2[i]n[/i] ember áll sorban a pénztár előtt, [i]n[/i]-nél egy darab kétezres, [i]n-[/i]nélegy darab ezres van. Hányféleképpen állhatnak sorba úgy, hogy mindenki tud jegyet venni?[/size][br][br][size=85]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.[/size]

[list=1][*][size=85][/size][size=85][url=https://web.cs.elte.hu/blobs/diplomamunkak/bsc_matelem/2013/nemeth_regina.pdf]Egy [i]n[/i] oldalú konvex sokszöget, hányféleképpen lehet felbontani háromszögekre az átlóival úgy, hogy az átlók nem metszik egymást?[/url][/size][br][/*][*][size=85][url=https://docplayer.hu/39691193-Rekurziv-sorozatok-eotvos-lorand-tudomanyegyetem-budapest-csiko-csaba-temavezeto-dr-mezei-istvan-matematika-szakos-hallgato-elte-ttk.html]Az udvarias sofőr esete[/url][/size][/*][*][size=85][url=https://docplayer.hu/39691193-Rekurziv-sorozatok-eotvos-lorand-tudomanyegyetem-budapest-csiko-csaba-temavezeto-dr-mezei-istvan-matematika-szakos-hallgato-elte-ttk.html]Hányféleképpen zárójelezhető egy [i]n[/i] tényezős szorzat?[/url][/size][/*][*][size=85][url=https://www.komal.hu/feladat?a=feladat&f=B4928&l=hu]KöMaL B. 4928. feladat[/url][/size][/*][/list]