Ismétléses kombináció fogalma

Ha adott n különböző elemből úgy választunk ki k darabot, hogy egyet többször is (ismétlődve is) kiválasztunk, akkor ismétléses kombinációról beszélünk.

Az ismétléses kombinációk számának felírásában, a felső index után zárójelbe tett i betűvel jelöljük azt, hogy ez az ismétlődést is megengedő kombinációk száma:

.

Feladat: 1 tanuló- 1 jutalom

Az osztály 32 tanulója között 8 azonos jutalmat sorsolnak ki.

a) Hányféleképpen kaphatják a tanulók a jutalmakat, ha egy tanuló legfeljebb csak egy jutalmat kaphat?

A feladat szövegében a „kiválasztás” szó nem szerepel, azonban úgy is megfogalmazhatjuk az a) kérdést, hogy 32-ből hányféleképpen választhatjuk ki azt a 8 tanulót, akik egy-egy jutalmat kapnak.

Ez 32 elem 8-ad osztályú kombinációinak száma:

.

Feladat: 1 tanuló- több jutalom

b) Hányféleképpen kaphatják a tanulók a jutalmakat, ha egy tanuló több jutalmat is kaphat?

Megoldás: 1 tanuló- több jutalom

Ez a kérdés jóval összetettebb. Mivel egy tanuló több jutalmat is kaphat, az is elképzelhető, hogy egyetlen tanuló kapja mind a 8-at. Nagyon nehéznek tűnik a kiválasztás, mert 1, 2, 3, ... vagy 8 tanulót lehet kiválasztani.

Tehetetlennek érezzük magunkat, és csak óhajként fogalmazhatjuk meg: „Milyen jó lenne, ha tudnánk a kiválasztandó tanulók pontos számát!”

Nekünk most csak lehetőségeket kell összeszámlálnunk, nem jutalmakat kell kiosztanunk. Most szabadon tervezhetjük a kiosztásnak olyan menetét is, amelyet a valóságban nem tehetünk meg.

Ha szerzünk még annyi ajándékot, hogy mindenkinek tudunk legalább egyet adni, akkor ez megkönnyíti az összeszámlálást. Ha ténylegesen ezt tennénk, akkor utólag vissza kellene kérnünk a jutalmak egy részét. Ez a kiosztási mód azonban csak elképzelt. Hangsúlyozzuk, hogy bennünket csak a kiosztás lehetőségének a száma érdekel.

A 8 ajándékhoz szerzünk még annyit, hogy mindenkinek egy-egy külön jutalmat adhassunk. Ehhez az elgondoláshoz a 32-es osztálylétszám miatt összesen 8+32, azaz 40 jutalmat kell szétosztanunk úgy, hogy mindenki kapjon egy „kötelező” jutalmat is.

Képzeljük el, hogy 40 ajándék egymásra téve úgy áll, ahogy azt az ábra mutatja.

A tanulók sorban mennek a jutalmakért, és az első leveszi a legfelső jutalmat (elképzelésünk szerint ez „jogosan” jár neki). Többet is vihet, mert „igazi jutalmat” is kaphat, és az csak az első után következik.

Túl sokat nem vihet el, mert mindenkinek kell kapnia legalább egy jutalmat. Az első tanuló egymás után veszi kézbe a jutalmakat. Valakinek egyszer azt kell mondania, hogy „elég”. Ez azt jelenti, hogy többet nem vihet el.

Az a valaki, aki időnként azt mondja, hogy „elég”, első alkalommal akkor mondhatja, amikor a legelső tanuló már kézbe vett egy jutalmat. Minden további tanulónál is kell ezt mondania egyszer-egyszer, csak az utolsó tanulónál nem mondhatja, az elviszi az összes maradék jutalmat (legalább egyet). Tehát 31-szer kell mondania azt, hogy „elég”.

Az előbb azt vizsgáltunk, hogy hányszor kell annak elhangoznia, hogy „elég”. Most vizsgáljuk meg azt, hogy hány lehetőség van az „elég” kimondására. Az első tanuló kézbe veszi az első jutalmat. Ekkor már elhangozhat az „elég”. Bármely jutalom kézbevevése után elhangozhat az „elég”, csak a legutolsó után nem, hiszen akkor már semmi értelme sem lenne. Tehát az „elég” kimondására 39 lehetőség van, de az - már megállapítottuk az előbb - csak 31-szer hangozhat el.

Annak, aki időnként azt mondja, hogy „elég”, 39 alkalom közül kell kiválasztania 31-et. A lehetőségek száma 39 elem 31-ed osztályú kombinációja:

.

Képzeletbeli szétosztásunk lehetőségeinek a száma azonos az igazi feltételnek megfelelő szétosztás számával. Igaz, hogy azok mellett mindenkinél van egy elképzelt „kötelező” jutalom is, de az nem változtatja meg az igazi feltételeknek megfelelő szétosztás lehetőségeinek a számát.

A b) kérdésre azt válaszoljuk: 32 tanuló között 8 azonos jutalmat -féleképpen oszthatunk szét, ha egy tanuló több jutalmat is kaphat. A a (3) összefüggés alapján -cal egyenlő.

Ez az előbb látott gondolatmenet alkalmazható n tanuló és k jutalom esetében is, valamint nagyon sok másként hangzó problémánál is. Mindig alkalmazható, ha n különböző elemből úgy kell kiválasztanunk k-t, hogy egyet többször is (akár k-szor is) kiválaszthatunk. Az ilyen esetekben, ugyanilyen módon okoskodva, az összes lehetőségre -et kapunk. Ez a (3) összefüggés alapján: .