Ismétléses kombináció

Az ismétléses kombináció hasonló a hagyományos kombinációhoz, csak megengedjük, hogy az alaphalmaz M elemei ismétlődjenek.

Definíció és képlet

Kezdjük egy szép példával: bemész a boltba, és egy kirándulásra tizenkét üveg üdítőt szeretnél venni. A polcon összesen négy különböző ízű üdítő van. Többféleképpen is megvehetsz tizenkét üveget – például 5 narancsosat, 2 citromosat, 1 almásat és 4 meggyest, vagy vehetsz minden ízből pontosan három üveget. Hányféleképpen vehetsz üdítőt úgy, hogy összesen pontosan tizenkét üveged legyen?

Az alaphalmazunk tehát M = {narancs, citrom, alma, meggy}, és azt kérdezzük, hány olyan k elemű csoport van, ahol k = 12, amelynek elemei az M halmazból valók, és a sorrend nem számít.

A képlet levezetése már valamivel bonyolultabb, mint a többi kombinatorikai feladatnál. Először képzeljük el a vásárlásunkat nullákból és egyesekből álló sorozatként úgy, hogy az egyesek száma megegyezik az adott ízből vett üvegek számával, a nulla pedig elválasztja az egyes ízeket. A 111011101111101 sorozat tehát azt jelenti, hogy három narancsosat vettünk (az első három 1-es), aztán három citromosat (a 0 az elválasztó, utána újabb három 1-es), aztán öt almásat (0 az elválasztó, majd öt 1-es), végül egy meggyest. Az egész elvet a következő ábra mutatja:

$$\underset{nar}{\underbrace{111}}0\underset{cit}{\underbrace{111}}0\underset{alm}{\underbrace{11111}}0\underset{meg}{\underbrace{1}}$$

Ha 6 narancsosat, 4 citromosat, 2 meggyest és egyetlen almásat sem szeretnénk venni, a sorozat így nézne ki:

$$\underset{nar}{\underbrace{111111}}0\underset{cit}{\underbrace{1111}}00\underset{meg}{\underbrace{11}}$$

Vegyük észre, hogy ennek a sorozatnak a hossza mindig 15 – 12 darab egyesnek kell benne lennie, hogy összesen 12 üveg üdítőt vegyünk, és három elválasztónak, hogy el tudjuk választani a négy különböző ízt. Már csak azt kell kiszámolnunk, hány olyan 15 hosszúságú sorozat van, amelyben pontosan három nulla szerepel.

Elég a nullák elhelyezését kiszámolni – ha a 12 egyes közé elhelyezünk 3 nullát, már van egy érvényes üdítőválasztásunk. Más szóval: van 15 helyünk, és ezek közül 3-at nullával kell kitöltenünk. A többi helyet automatikusan egyesekkel töltjük ki.

Ez már egy egyszerű feladat az ismétlés nélküli kombinációra. A 15 helyet megszámozzuk a {1, …, 15} számokkal, és ebből a halmazból mindig hármasokat választunk ki, így megkapjuk azt a három indexet, ahová a nullát tesszük. Például a {2, 4, 7} kombinációhoz a következő sorozatot kapnánk: 101011011111111. A 2., 4. és 7. helyen nulla áll, a többi egyes. Összesen tehát

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

különböző módon helyezhetjük el a nullákat a 15 helyen, és így 455 különböző módon vehetünk 12 üveg üdítőt, ha négy különböző ízünk van.

Az előző gondolatmenetet általánosíthatjuk. Ha van egy n elemű M halmazunk, és ebből választunk k elemű csoportokat úgy, hogy az egyes elemek ismétlődhetnek, akkor egy n + k − 1 hosszúságú, nullákból és egyesekből álló sorozatot állítunk össze (k darab egyes és n − 1 darab nulla), és azt keressük, hányféleképpen helyezhetünk el n − 1 nullát. Az ismétléses kombinációk száma, amelyet C'(k, n)-nel jelölünk, tehát

$$C^{\prime }(k,n)=(\genfrac{}{}{0ex}{}{n+k-1}{n-1})=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$$

Az utolsó átalakítást a binomiális együtthatók alapvető összefüggései tették lehetővé.

Megoldott feladatok

1. Hányféleképpen lehet szétosztani 20 ingyenes színházjegyet 10 nyugdíjas között? Ez ismétléses kombinációs feladat, mert egy nyugdíjas több, akár az összes ingyenes jegyet is megkaphatja. Csak arra kell jól ügyelnünk, mi az n és mi a k. Valójában 20 elemű kombinációkat választunk a 10 nyugdíjasból, vagyis egy olyan nullákból és egyesekből álló sorozatot készítünk, amelynek hossza 29, és 20 egyest meg 9 nullát tartalmaz. Tehát n = 10, k = 20. Az eredmény:

$$C^{\prime }(20,10)=(\genfrac{}{}{0ex}{}{10+20-1}{20})=10015005.$$