Feladat: F.2753 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Podoski Károly 
Füzet: 1990/május, 204 - 205. oldal  PDF  |  MathML 
Témakör(ök): Függvények, Kombinatorikai leszámolási problémák, Természetes számok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1989/szeptember: F.2753

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. A feladatot ún. kettős teljes indukcióval igazoljuk. Ez azt jelenti, hogy n-re vonatkozó teljes indukciót alkalmazunk, de ezen belül az indukciós lépést k-ra vonatkozó indukcióval bizonyítjuk.
1. Kezdő lépés. n=0 esetén az állítás igaz, hiszen 0!=1 és f(0,k) minden k-ra egész (k=0-ra 1, k>0-ra 0), tehát 0! |f(0,k) igaz.
2. Indukciós lépés. Tegyük fel, hogy f(n,k) minden k természetes számra osztható n!-sal, és belátjuk, hogy ebből következik, hogy f(n+1,k) minden k természetes számra osztható (n+1)!-sal.
Ezt k-ra vonatkozó indukcióval bizonyítjuk. Ha k=0, akkor f(n+1,0)=0 osztható (n+1)!-sal. Most tegyük fel, hogy már beláttuk valamelyik k-ra f(n+1,k) osztható (n+1)!-sal. Ekkor f(n+1,k+1)=(n+1)[f(n+1,k)+f(n,k)] a definíció szerint, és itt a zárójel mindkét tagja osztható n!-sal (az első tag még (n+1)!-sal is), tehát f(n+1,k+1) osztható (n+1)⋅n!=(n+1)!-sal. Így beláttuk, hogy f(n+1,k) minden k-ra osztható k!-sal, s ezzel az indukciós lépést, tehát a bizonyítást is befejeztük.

 

Megjegyzések. 1. A bizonyítás azt is megmutatta, hogy f(n,k) minden (n,k) természetes számpárra (véges sok lépésben) kiszámolható.
2. A bizonyításban alkalmazott kettős indukció esetünkben könnyen "egyszeressé'' változtatható, ha az indukciót nem n, majd k, hanem (n+k) szerint végezzük.
 

II.megoldás. Megmutatjuk, hogy az f(n,k) függvénynek kombinatorikus jelentése van. Jelölje g(n,k) azt a számot, ahányféleképpen az 1, 2, ..., k számokat pontosan n (megkülönböztetett) osztályba lehet sorolni, vagyis ahányféleképpen n csoportba lehet őket osztani úgy, hogy minden csoportba kerüljön szám. Ha két felosztás csak abban különbözik egymástól, hogy csoportokat egészben felcserélünk, azt is különbözőnek számítjuk. (Pl. k=4, n=3-ra az {1}, {2}, {3,4} felosztás és a {3, 4}, {2}, {1} felosztás különböző.) Bebizonyítjuk, hogy g(n,k)-re teljesülnek a feladat egyenletei. Ekkor a fenti megjegyzés szerint g(n,k) értéke minden (n,k) természetes számpárra kiszámítható és ugyanaz lesz az értéke, mint f(n,k)-é. Tehát f(n,k)=g(n,k).
Másrészt a definícióból nyilvánvaló, hogy n! osztója g(n,k)-nak, hiszen bontsuk fel az {1, 2, ..., k} halmazt tetszőlegesen n db nem üres, páronként diszjunkt A1, A2, ..., An halmazokra minden lehetséges módon. Minden ilyen felbontásból n! féle módon készíthetünk csoportba osztást: ti. ennyiféleképpen lehet "megszámozni'', hogy az A1, ..., An halmazok közül melyik legyen az első csoport, melyik a második stb. Nyilván minden csoportbaosztást megkapunk így, s mivel egyik Ai sem üres és nincs köztük átfedés, ezért minden felosztás különböző lesz.
Be kell még bizonyítanunk, hogy g(0,0)=1, g(n,0)=g(0,n)=0, ha n≧1, és g(n,k)=n[g(n-1,k-1)+g(n,k-1)]. Nyilvánvaló, hogy ha k<n, akkor nincs elég szám, így g(n,k)=0, és az is világos, hogy g(n,n)=n!, az n-edrendű permutációk száma. Ebből g(0,0)=1, és g(n,n)=n(n-1)!=n[g(n-1,n-1)+g(n,n-1)], hiszen g(n,n-1)=0. Legyen most k>n, és osszuk fel az {1, 2, ..., k} halmazt n csoportra. Két eset van: 1. A k szám egy külön csoportot képez. 2. A k egy többelemű csoportban van.
Az első esetnél n-féle lehetőség van arra, hogy hányadik csoportban legyen a k, s a többi n-1 csoportba kell az 1, 2, ..., k-1 számokat besorolni úgy, hogy minden csoportba jusson szám; erre g(n-1,k-1) lehetőség van. Az 1. eset tehát n⋅g(n-1,k-1)-féleképpen jöhet létre.
A második eset annyiféleképpen valósulhat meg, ahányféleképpen az 1, ..., k-1 számokat n (nem üres) csoportba lehet osztani (ez g(n,k-1) lehetőség), majd a k számot valamelyik csoportba betenni (ez minden esetben n lehetőség). A 2. eset tehát n⋅g(n,k-1)-féleképpen valósítható meg. Több eset nem lévén azt kaptuk, hogy
g(n,k)=n[g(n,k-1)+g(n-1,k-1).]
Ezzel a bizonyítást befejeztük.
 

Podoski Károly (Bp., Árpád Gimn., IV. o. t.) dolgozata alapján