 Akkor PAL érdeklődésére tekintettel nézzük meg ezeket a feladatokat.
Kezdjük az 512. feladattal. Stray dog már elárulta a megoldást: a determináns 1. Ezt nem is nehéz belátni: detH=det(CCT)=(detC)2. Csakhogy C háromszögmátrix, mivel ha 0 n<k, akkor n-k<0 és n-k-2<0, így

tehát a C mátrix főátló fölötti elemei valóban nullák. Hasonlóan, ha 0 n=k, akkor

viszont

így hát cn,k=1, tehát a mátrix főátlójában egyesek állnak. Ebből aztán detC=1 tehát valóban detC=1.
Mindezt persze akkor lehet könnyen megsejteni, ha előbb valamilyen kis N méretre konkrétan kiszámoljuk a mátrixot. Például ha N=12, akkor


Most nézzük az 511. feladatot. Erre van egy nagyon érdekes kombinatorikus bizonyítás.
Először lássunk be egy rekurziót a C mátrix elemeire. Vegyük észre, hogy ha 0 n és 0<k, akkor cn+1,k=cn,k-1+cn,k+1; ha pedig 0 n, akkor cn+1,0=cn,1. Szóban ez azt jelenti, hogy a mátrixban minden elem a fölötte balra lévő és a fölötte jobbra lévő elem összege, de ha nincs fölötte balra lévő elem, akkor egyszerűen a fölötte jobbra lévő elemmel egyenlő.
Azt, hogy ez a rekurzió igaz, nem nehéz belátni, egyszerűen be kell írni a definíciót. Nézzük először az első esetet: legyen 0 n és 0<k. Ha n-k páratlan, akkor



ha viszont n-k páros, akkor cn+1,k=0=cn,k-1+cn,k+1. A második esetben, ha 0 n, akkor



(Egy kis csalás van itt: szó szerint ennek a szabálynak a mátrix jobb szélén nincs értelme, de szerencsére tekinthetjük a mátrixot a végtelen nagy mátrix sarkának, úgyhogy igazából nincs probléma.)
Most a meglepő észrevétel az, hogy a C mátrix elemeinek kombinatorikai jelentést lehet tulajdonítani. A cn,k elem ugyanis pontosan azt számolja le, hányféleképpen lehet n lépést tenni a számegyenesen az origóból úgy, hogy minden lépésben egyet balra vagy egyet jobbra lépünk, nem lépünk rá a negatív félegyenesre, és a végén a k-ba érkezünk. Azt, hogy valóban ezt számoljuk le, nem nehéz látni a fenti rekurzió alapján.
Vegyük most szemügyre ezt a képletet, ami szerepelt a kitűzésben: ha 0 m,n akkor

Azt állítom, hogy hm,n éppen azt számolja le, hányféleképpen lehet a számegyenesen m+n lépés hosszú sétát tenni úgy, hogy az origóból indulunk és oda is érünk vissza, minden lépésben eggyel jobbra vagy eggyel balra lépünk, és sose lépünk a negatív félegyenesre. Valóban, legyen ugyanis k az a szám, ahol az m-edik lépésben lépünk. Ekkor az első m lépés cm,k féle lehet a c fent megadott értelmezése szerint. Másrészt az utolsó n lépés éppen cn,k féle lehet, mert ha ezt az utolsó n lépést visszafele játsszuk le, akkor az origóból indulunk, és a végén érünk a k-ba. Az is látható, hogy az első m és az utolsó n lépést egymástól függetlenül választhatjuk meg akárhogyan, ha már k értékét rögzítettük, minden lehetőséghez tartozik pontosan egy m+n lépéses séta. Így megkaptuk, hogy hm,n egyenlő az m+n hosszú, origóba érkező séták számával, ami tényel m+n függvénye.
Az 513. feladatot egyelőre nem lövöm le.
|