Feladat: F.3287 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Barát Anna ,  Máthé András ,  Naszódi Gergely ,  Pálvölgyi Dömötör ,  Papp Dávid ,  Szabadka Zoltán ,  Vitéz Ildikó 
Füzet: 2000/január, 35 - 36. oldal  PDF file
Témakör(ök): Részhalmazok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1999/május: F.3287

Egy halmaz páronként diszjunkt halmazokra való felbontását a halmaz egy partíciójának nevezzük. Igazoljuk, hogy egy n elemű halmaznak legfeljebb n! darab partíciója van.

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. Jelöljük egy n elemű halmaz partícióinak a számát r(n)-nel. Nyilván r(1)=1=1!, r(2)=2=2!, r(3)=4<3!. Tegyük fel, hogy r(k)<k!, és vizsgáljuk egy k+1 elemű T=H{a} halmaz partícióit (aH). A T minden partíciójából az a elem elhagyásával a H partícióját kapjuk. Megfordítva ez azt jelenti, hogy T minden partíciója megkapható a H alkalmas H=K1...Kt partíciójából úgy, hogy az a elemet valamelyik Ki részhalmazhoz csatoljuk, vagy képezzük a (mindegyik Ki-hez diszjunkt) {a} halmazt.
Adott H-beli partíció esetén ez éppen t+1 lehetőség. Mivel a Ki halmazok egyike sem üres*, azért tk, t+1k+1. Tehát r(k+1)(k+1)r(k), így (a megvizsgált kezdeti érték(ek)re támaszkodva) az r(n)n! egyenlőtlenség teljes indukciós bizonyítását kaptuk.
 Vitéz Ildikó (Miskolc, Földes F. Gimn., 11. o.t.)

 
II. megoldás. Az {1,2,...,n} halmaz mindegyik partíciójához rendeljük hozzá az 1, 2, ..., n számok egy sorbaállítását a következőképpen: először állítsuk a partíciót meghatározó részhalmazokat legkisebb elemük szerint növekvő̲ sorrendbe, az egyes részhalmazokban szereplő számokat pedig rendezzük csökkenő̲ sorrendbe. Egy ilyen módon kapott számsorból a partíció egyértelműen visszakapható, hiszen éppen ott vannak az egyes részhalmazokat kijelölő vágások, ahol a sorban egy szám után nála nagyobb szám következik. Tehát különböző partícióknak különböző számsorozatok felelnek meg, ezért a partíciók száma nem nagyobb az összes sorrend számánál, n!-nál.
 Papp Dávid (Budapest, Szent István Gimn., 11. o.t.)

*Ez a nyilvánvalóan szükséges megszorítás a feladat szövegéből sajnos kimaradt.