Alkalmazott matematika 3

Kombinatorika

Tartalom

• Permutációk
  • Ismétlés nélküli permutációk
  • Ismétléses permutációk
• Variációk
  • Ismétlés nélküli variációk
  • Ismétléses variációk
• Kombinációk
  • Ismétlés nélküli kombinációk
  • Ismétléses kombinációk
• Gyakorló feladatok

Permutációk

Ismétlés nélküli permutációk

Legyen H egy tetszőleges halmaz. Válasszuk ki és rögzítsük a H halmaz n∈ℕ⁺ darab különböző elemét (feltéve, hogy H elemszáma legalább 'n'). Speciálisan megengedjük az n=1 esetet is. Ekkor az
    (a₁, a₂, ..., a_n)
véges elemsorozatot ("rendezett elem n-est") az a_i elemek egy ismétlés nélküli permutációjának nevezzük.

Legyen
    H_n={a_i∈H | 1≤i≤n}
a kiválasztott elemekből álló ('n' elemű) halmaz. Ekkor a H_n halmaz elemeinek egy ismétlés nélküli permutációján a H_n halmaznak egy "önmagára vett bijektív leképezését értjük" (Wikipédia). Ebben az értelemben a H_n halmaz elemeinek összes permutációját a H_n halmaz önmagára vett összes lehetséges bijektív leképezése adja meg.

Például, ha n=5 és H_n={1,2,3,4,5}, akkor egy lehetséges 'p' bijektív leképezést

módon adhatunk meg, ahol a leképezés értelmezési tartományának (Dom(p)) elemeit a táblázat felső sorában, értékkészletét (Rng(p)) pedig a táblázat alsó sorában soroljuk fel (az elemek egymáshoz rendelését pedig a táblázat megfelelő oszlopai mutatják).

Megjegyzés: a H_n (n elemű) halmaz elemeinek egy permutációját úgy is megkaphatjuk, hogy a H_n halmaz összes elemét egy adott sorrendben, egymás után kiválasztjuk (és minden elemet csak egyszer, azaz az elemet kiválasztása után "nem tesszük vissza"). Az összes lehetséges (különböző) kiválasztások száma ebben az esetben megegyezik az n elem n-ed osztályú (vagy rendű) ismétlés nélküli variációinak a számával (ld. később).

Az (a₁, a₂, ..., a_n) és (b₁, b₂, ..., b_n) permutációk megegyeznek, ha minden elemre a_i=b_i (1≤i≤n) teljesül. Egy ismétlés nélküli permutációban minden elem különböző, tehát két tetszőleges elemet felcserélve egy másik, az előzőtől különböző permutációt kapunk.

Rögzített n∈ℕ⁺ elemszám esetén az összes különböző ismétlés nélküli permutáció száma

A fentieknek megfelelően egy véges, n elemű H_n halmaz elemeinek összes ismétlés nélküli permutációját
   { (i₁,i₂,...,i_n) | i_j∈H_n, 1≤j≤n; i_j≠i_k, 1≤j<k≤n }
módon kaphatjuk meg.

Például az (1,2,3) számok ismétlés nélküli permutációi a következőképpen állíthatók elő:

/* ismétlés nélküli permutációk, P3 (1,2,3) */

var i,j,k;
var sorszam=0;

for(var i=1;i<=3;i++) {
 for(var j=1;j<=3;j++) {
  if(j==i) continue;
  for(var k=1;k<=3;k++) {
   if(k==i || k==j) continue;
   writeln("("+i+","+j+","+k+")");
   sorszam++;
   }
  }
 }
writeln();
writeln("a permutációk száma: "+sorszam);

writeln("-----");

Jegyezzük meg, hogy
– a permutációkat a H_n={1,2,3} halmaz elemeinek egymás utáni kiválasztásával kapjuk meg (n=3);
    ○ egy permutáció kiválasztása (P₃=V₃³, ld. később) a H_n={1,2,3} halmaz elemeinek egy lehetséges elrendezését valósítja meg;
    ○ a H_n halmaz elemei sorszámok, amelyek bármilyen különböző dolgot azonosíthatnak (pl. különböző golyókat, kártyákat stb.);
– a programban szereplő 'for' ciklusok ciklusváltozói (i,j,k) a H_n halmaz elemeit veszik fel, vagyis a ciklusváltozók értéktartománya meghatározza, hogy hány elemmel dolgozunk (hány elemből választunk, hány elemet rendezünk el stb.);
    ○ az "if ... continue;" utasítások biztosítják, hogy a ciklusváltozók értéke minden kiválasztáskor különböző legyen (mivel ismétlés nélküli permutációkat képzünk);
– minden egyes 'for' ciklus egy elem kiválasztását valósítja meg a H_n halmazból, vagyis 'n' elem kiválasztásához pontosan 'n' (egymásba ágyazott) ciklusra van szükségünk;
    ○ egy permutáció kiválasztását a writeln("("+i+","+j+","+k+")"); utasítás valósítja meg.

A program futásának eredménye:

Az ismétlés nélküli permutációk alapfeladata

Legyen egy urnában 3 különböző színű golyó.

(1) Válasszunk ki (vagy húzzunk ki) az urnából 3 különböző színű golyót visszatevés nélkül. Hányféleképpen tehetjük ezt meg?

(2) Helyezzük el a kihúzott golyókat egymás mellé a húzás sorrendjében. Hányféle elrendezés lehetséges?

Ismétléses permutációk

Legyen H egy tetszőleges halmaz. Válasszuk ki és rögzítsük a H halmaz n∈ℕ⁺ darab (nem feltétlenül különböző) elemét (a_i∈H, 1≤i≤n). Ekkor az
    (a₁, a₂, ..., a_n)
véges elemsorozatot ("rendezett elem n-est") az a_i elemek ismétléses permutációjának nevezzük.

Egy ismétléses permutációban két elemet felcserélve csak akkor kapunk az előzőtől különböző permutációt, ha a felcserélt elemek különbözőek.

Tegyük fel, hogy az (a₁, a₂, ..., a_n) ismétléses permutációban s≤n darab különböző elem van. Jelöljük ezeket az elemeket b_j (1≤j≤s) módon. Ezekre teljesül, hogy az (a₁, a₂, ..., a_n) permutációban
   a b₁ elem k₁-szer ismétlődik (1≤k₁≤n),
   a b₂ elem k₂-szer ismétlődik (1≤k₂≤n),
   ...,
   a b_s elem k_s-szer ismétlődik (1≤k_s≤n).
Mivel a permutációban összesen 'n' darab elem van, az egyes elemek ismétlődéseinek összegére
    k₁+k₂+...+k_s=n
teljesül. Ebben az esetben az 'n' elem összes k₁, k₂, ..., k_s-ad rendű (különböző) ismétléses permutációjának száma

Emeljük ki, hogy 's' értéke a különböző elemek számát adja meg, 'n' értéke pedig az ismétléses permutációban levő különböző "helyek" (vagy pozíciók) számát adja meg, amely csak ismétlés nélküli permutációk esetén egyezik meg a permutációban levő különböző elemek számával. Ebben az esetben ugyanis k₁=k₂=...=k_s=1 miatt egyrészt s=n, másrészt pedig
    P_n^1,1,...,1= n!= P_n
teljesül.

Egy ismétléses permutáció elemeit a
    { (b₁,k₁), (b₂,k₂), ... , (b_n,k_n) }
véges multihalmaz (vagy "zsák") segítségével adhatjuk meg, ahol a fenti jelölésnek megfelelően a (b_j,k_j) számpárok ("tupletek") azt jelölik, hogy a multihalmazban a b_j elem pontosan k_j≥0 gyakorisággal fordul elő (1≤j≤n), és a gyakoriságokra
    k₁+k₂+...+k_n=n
teljesül. Vegyük észre, hogy most megengedtük a gyakoriságokra a nulla értéket is (ez azonban 0!=1 miatt ugyanazt az eredményt adja az ismétléses permutációk számára, mint a fenti képlet).

Egy ismétléses permutációt a multihalmaz összes elemének a multihalmazban szereplő gyakorisággal történő kiválasztásával kaphatunk meg (az elemeket tetszőleges sorrendben választva).

A fentiekből következik, hogy
    (1) az összes lehetséges multihalmaz számát 'n' elem 'n'-ed rendű ismétléses kombinációja adja meg;
    (2) ha a multihalmaz összesen két elemet (s=2) tartalmaz k₁>0 és k₂>0 gyakorisággal, és az összes többi elem gyakorisága zérus (vagyis k₁+k₂=n teljesül), akkor 'n' elem k₁ és k₂ rendű ismétleses permutációja megegyezik 'n' elem k=k₁ rendű (vagy 'n' elem k=k₂=(n−k₁) rendű) ismétlés nélküli kombinációjával, azaz
    P_n^k₁,k₂,i= n!/(k₁!*k₂!)= C_n^k= (ⁿ _k)= (ⁿ _n−k)= C_n^n−k
teljesül.
    A feladat egy lehetséges modellje: hányféleképpen állíthatunk össze 'k' darab fehér és (n−k) darab fekete golyóból egy sorozatot (permutáció), illetve hányféleképpen oszthatjuk fel az 'n' természetes számból álló (alap)halmazt egy 'k' elemű, és egy (n−k) elemű részhalmazra (kombináció)?

Például a { (1,2), (2,1), (3,2) } multihalmaznak megfelelő számok, azaz az (1,2,3) számok 5 elemből álló (2,1,2) osztályú ismétléses permutációi a következőképpen állíthatók elő:

/* ismétléses permutációk, P5 (1,1,3) */

var i,j,k,l,m;
var sorszam=0;
var t=[-1,1,1,3]; // a 0-dik elemet nem használjuk
var s=[-1,0,0,0]; // az 1,2,3 számok gyakorisága

for(var i=1;i<=3;i++) {
 s[i]++;
 for(var j=1;j<=3;j++) {
  s[j]++;
  for(var k=1;k<=3;k++) {
   s[k]++;
   for(var l=1;l<=3;l++) {
    s[l]++;
    for(var m=1;m<=3;m++) {
     s[m]++;
     if(s[1]==t[1] && s[2]==t[2] && s[3]==t[3]) {
      writeln("("+i+","+j+","+k+","+l+","+m+")");
      sorszam++;
      }
     s[m]--;
     }
    s[l]--;
    }
   s[k]--;
   }
  s[j]--;
  }
 s[i]--;
 }

writeln();
writeln("a permutációk száma: "+sorszam);

writeln("______________________");

Megjegyzés: a fenti program az (1,2,3) számokból képzett 5 elemű, (1,1,3) osztályú ismétléses permutációkat úgy állítja elő, hogy előállítja az (1,2,3) számok összes 5-öd osztályú (vagy rendű) ismétléses variációit (ld. később), és ezekből kiszűri ("kiszitálja") azokat az "érvényes" permutációkat, amelyekben pontosan 1 db 1-es, 1 db. 2-es és 3 db. 3-as szám szerepel.

A program futásának eredménye:

Vegyük észre, hogy a fenti program alapján előállíthatjuk n=3 különböző elem ismétlés nélküli permutációit is, mint az ismétléses permutációk speciális esetét:

/* ismétlés nélküli permutációk, P3 = P3 (1,1,1) */

var i,j,k;
var sorszam=0;
var t=[-1,1,1,1]; // a 0-dik elemet nem használjuk
var s=[-1,0,0,0]; // az 1,2,3 számok gyakorisága

for(var i=1;i<=3;i++) {
 s[i]++;
 for(var j=1;j<=3;j++) {
  s[j]++;
  for(var k=1;k<=3;k++) {
   s[k]++;
   if(s[1]==t[1] && s[2]==t[2] && s[3]==t[3]) {
    writeln("("+i+","+j+","+k+")");
    sorszam++;
    }
   s[k]--;
   }
  s[j]--;
  }
 s[i]--;
 }

writeln();
writeln("a permutációk száma: "+sorszam);

writeln("______________________");

Az ismétléses permutációk alapfeladata

Legyen egy urnában 5 golyó. Ezekből 2 golyó piros, 1 golyó zöld és 2 golyó kék színű. Az azonos színű golyók között nem tudunk különbséget tenni.

(1) Válasszunk ki (vagy húzzunk ki) az urnából 5 golyót visszatevés nélkül. Hányféleképpen tehetjük ezt meg?

(2) Helyezzük el a kihúzott golyókat egymás mellé a húzás sorrendjében. Hányféle elrendezés lehetséges?

A fenti programokat általánosítva megoldhatunk további feladatokat is. Például vizsgáljuk meg azt a feladatot, hogy van 4 különböző színű golyónk (piros=1, sárga=2, zöld=3, kék=4), egy urnából 5 golyót húzunk, és a kihúzott golyókat visszatesszük. Hányféleképpen húzhatjuk ki a golyókat úgy, hogy a pirosból (1-es golyó) legalább 2-t de legfeljebb 4-t, a sárgából (2-es golyó) legfeljebb 1-et, a zöldből (3-es golyó) legfeljebb 2-t, a kékből (4-es golyó) legalább 1-t de legfeljebb 3-t húzhatunk ki, ha a golyók kihúzásának a sorrendje is számít? (Megoldás: 215 ilyen húzás lehetséges.)

/* ismétléses permutációk, P5 (2-4,0-1,0-2,1-3) */

var i,j,k,l,m;
var sorszam=0;
var tmin=[-1,2,0,0,1]; 
var tmax=[-1,4,1,2,3]; 
var s=[-1,0,0,0,0]; // az 1,2,3,4 számok gyakorisága

for(var i=1;i<=4;i++) {
 s[i]++;
 for(var j=1;j<=4;j++) {
  s[j]++;
  for(var k=1;k<=4;k++) {
   s[k]++;
   for(var l=1;l<=4;l++) {
    s[l]++;
    for(var m=1;m<=4;m++) {
     s[m]++;
     if(s[1]>=tmin[1] && s[1]<=tmax[1] &&
        s[2]>=tmin[2] && s[2]<=tmax[2] && 
        s[3]>=tmin[3] && s[3]<=tmax[3] &&
        s[4]>=tmin[4] && s[4]<=tmax[4]) {
      writeln("("+i+","+j+","+k+","+l+","+m+")");
      sorszam++;
      }
     s[m]--;
     }
    s[l]--;
    }
   s[k]--;
   }
  s[j]--;
  }
 s[i]--;
 }

writeln();
writeln("a kihúzások száma: "+sorszam);

writeln("______________________");

Variációk

Ismétlés nélküli variációk

Legyen H egy tetszőleges, 'n' elemű halmaz, és válasszuk ki ennek k∈ℕ⁺ darab különböző elemét (a_i, a_j∈H, a_i≠a_j, 1≤i<j≤k≤n); speciálisan megengedjük a k=1 (és k=n) esetet is. Ekkor az
    (a₁, a₂, ..., a_k)
véges elemsorozatot az a_i elemek egy ismétlés nélküli variációjának nevezzük.

Rögzített k∈ℕ⁺ elemszám esetén az n elem összes különböző k-ad osztályú ismétlés nélküli variációjának száma

Például az (1,2,3,4) számok 3-ad osztályú ismétlés nélküli variációi a következőképpen állíthatók elő:

/* ismétlés nélküli variációk, V4,3 (1,2,3,4) */

var i,j,k;
var sorszam=0;

for(var i=1;i<=4;i++) {
 for(var j=1;j<=4;j++) {
  if(j==i) continue;
  for(var k=1;k<=4;k++) {
   if(k==i || k==j) continue;
   writeln("("+i+","+j+","+k+")");
   sorszam++;
   }
  }
 }
writeln();
writeln("a variációk száma: "+sorszam);

writeln("-----");

A program futásának eredménye:

Az ismétlés nélküli variációk alapfeladata

Legyen egy urnában 4 különböző színű golyó.

(1) Válasszunk ki (vagy húzzunk ki) az urnából 3 golyót visszatevés nélkül. Hányféleképpen tehetjük ezt meg?

(2) Helyezzük el a kihúzott golyókat egymás mellé a húzás sorrendjében. Hányféle elrendezés lehetséges?

Ismétléses variációk

Legyen H egy tetszőleges, 'n' elemű halmaz, és válasszuk ki ennek k∈ℕ⁺ darab elemét úgy, hogy egy elemet többször is kiválaszthatunk (a_i∈H, 1≤i≤k). Ekkor az
    (a₁, a₂, ..., a_k)
véges elemsorozatot az a_i elemek egy ismétléses variációjának nevezzük (mivel egy elemet többször is kiválaszthatunk, k>n is lehetséges).

Rögzített k∈ℕ⁺ elemszám esetén az 'n' elem összes különböző k-ad osztályú ismétléses variációjának száma

Például az (1,2,3) számok 3-ad osztályú ismétléses variációi a következőképpen állíthatók elő:

/* ismétléses variációk, V3,3,i (1,2,3) */

var i,j,k;
var sorszam=0;

for(var i=1;i<=3;i++) {
 for(var j=1;j<=3;j++) {
  for(var k=1;k<=3;k++) {
   writeln("("+i+","+j+","+k+")");
   sorszam++;
   }
  }
 }
writeln();
writeln("a variációk száma: "+sorszam);

writeln("-----");

A program futásának eredménye:

Az ismétléses variációk alapfeladata

Legyen egy urnában 3 különböző színű golyó.

(1) Válasszunk ki (vagy húzzunk ki) az urnából 3 golyót úgy, hogy a golyókat a kihúzás után visszatesszük. Hányféleképpen tehetjük ezt meg?

(2) Helyezzük el a kihúzott golyókat egymás mellé a húzás sorrendjében. Hányféle elrendezés lehetséges?

Kombinációk

Ismétlés nélküli kombinációk

Legyen H egy tetszőleges, 'n' elemű halmaz, és válasszuk ki ennek k∈ℕ darab különböző elemét (a_i, a_j∈H, a_i≠a_j, 1≤i<j≤k≤n) úgy, hogy nem számít a kiválasztott elemek sorrendje; speciálisan megengedjük a k=1 (és k=n) esetet is. Ekkor az
    { a₁, a₂, ..., a_k }
véges elemhalmazt az a_i elemek egy ismétlés nélküli kombinációjának nevezzük.
(Az ismétlés nélküli kombinációkat úgy is felfoghatjuk, hogy az ismétlés nélküli variációknál megismerteknek megfelelően kiválasztunk egy 'k' elemből álló elemsorozatot, és ezek lehetséges permutációi között nem teszünk különbséget. Ez számok esetében a legegyszerűbben úgy oldható meg, hogy a kiválasztott számokat növekvő sorrendben elrendezzük, ez ugyanis az azonos számokból álló variációk közül minden esetben csak azt az egy permutációt "hagyja meg", amelyben a számok rendezettek, és a többi permutációt kiszűri.)

Az ismétlés nélküli kombinációkat úgy képezzük, hogy tetszőlegesen kiválasztott 'k' különböző elem összes lehetséges (k! darab) permutációjához egy kijelölt permutációt rendelünk hozzá (ti. azt, amelyekben a számokat elrendezzük). Ezért ha 'k' különböző elemet egymás után, adott sorrendben választunk ki 'n' különböző elemből, akkor ismétlés nélküli kombinációk esetén a 'k' különböző elem összes lehetséges kiválasztásának számát osztanunk kell a k! értékkel.

Rögzített k∈ℕ elemszám esetén az n elem összes különböző k-ad osztályú ismétlés nélküli kombinációjának száma

módon számítható ki, ahol az

Például az (1,2,3,4) számok 3-ad osztályú ismétlés nélküli kombinációi a következőképpen állíthatók elő:

/* ismétlés nélküli kombinációk, C4,3 (1,2,3,4) */

var i,j,k;
var sorszam=0;

for(var i=1;i<=4;i++) {
 for(var j=i+1;j<=4;j++) {
  for(var k=j+1;k<=4;k++) {
   writeln("{"+i+","+j+","+k+"}");
   sorszam++;
   }
  }
 }
writeln();
writeln("a kombinációk száma: "+sorszam);

writeln("-----");

Vegyük észre, hogy a kombinációk egyes elemeinek kiválasztását végző 'for' ciklusok ciklusváltozóinak (i, j és k) kezdőértéke biztosítja, hogy az {i,j,k} alakú kombinációk mindegyikében i<j<k teljesüljön, vagyis az elemek a kombinációban növekvő sorrendben szerepeljenek.

A program futásának eredménye:

Az ismétlés nélküli kombinációk alapfeladata

Legyen egy urnában 4 különböző színű golyó.

(1) Válasszunk ki (vagy húzzunk ki) az urnából 3 golyót visszatevés nélkül és helyezzük el őket egy másik urnában (vagyis a kihúzás sorrendje nem számít). Hányféleképpen tehetjük ezt meg?

(2) Helyezzük el a kihúzott golyókat egymás mellé a színek sorrendjében (legyen például az egyes színárnyalatok kódja vörös=0, sárga=1/6, zöld=1/3, cián=1/2, kék=2/3, magenta=5/6 stb., és helyezzük el a kihúzott golyókat a színkódok szerint). Hányféle elrendezés lehetséges?

Ismétléses kombinációk

Legyen H egy tetszőleges, 'n' elemű halmaz, és válasszuk ki ennek k∈ℕ⁺ darab a_i∈H elemét (1≤i≤k) úgy, hogy nem számít a kiválasztott elemek sorrendje, és egy elemet többször is kiválaszthatunk. Ekkor az
    { (a₁,k₁), (a₂,k₂), ... , (a_n,k_n) }
véges multihalmazt (vagy "zsákot") a k_i≥0 gyakorisággal előforduló a_i elemek (1≤i≤n) egy ismétléses kombinációjának nevezzük. Mivel az ismétléses kombináció során pontosan 'k' darab elemet választunk, a zsákban levő elemek gyakoriságára minden választás esetén
    k₁+k₂+k₃+ ... +k_n=k
teljesül (mivel egy elemet többször is kiválaszthatunk, k>n is lehetséges).
(Az ismétléses kombinációkat úgy is felfoghatjuk, hogy az ismétléses variációknál megismerteknek megfelelően kiválasztunk egy k elemből álló elemsorozatot, és ezek lehetséges ismétléses permutációi között nem teszünk különbséget. Ez számok esetében a legegyszerűbben úgy oldható meg, hogy a kiválasztott számokat nem csökkenő sorrendben elrendezzük, ez ugyanis az azonos számokból álló variációk közül minden esetben csak azt az egy permutációt "hagyja meg", amelyben a számok nem csökkenő sorrendben állnak, és a többi permutációt kiszűri. Tehát például az első 'n' természetes szám k-ad osztályú ismétléses kombinációit a számokból képezhető 'k' elemű rendezett számsorozatok (szám n-esek) adják meg, amelyekben egy szám többször is előfordulhat.)

Rögzített k∈ℕ⁺ elemszám esetén az 'n' elem összes különböző k-ad osztályú ismétléses kombinációjának száma

módon számítható ki.

Egy { (a₁,k₁), (a₂,k₂), ... , (a_n,k_n) } ismétléses kombinációt kizárólag a k_i≥0 gyakoriságok határoznak meg, ahol k₁+k₂+...+k_n=k miatt nyilvánvalóan k_i≤n is teljesül (1≤i≤n). Az ismétléses kombináció az (a_i,k_i) elempárokból álló multihalmaz (1≤i≤n), amelyek sorrendje tetszőlegesen megválasztható. Rögzítsünk ezért egy meghatározott sorrendet (például úgy, hogy az (a_i,k_i) elempárokat az a_i elemek szerint növekvő sorrendben elrendezzük).

Ezután kódoljuk az elempárokat a következőképpen:
   (0) legyen i←1,
   (1) az a_i elemet helyettesítsük egy rögzített B értékkel és írjuk le,
   (2) B után írjunk annyi X-t, amennyi k_i értéke,
   (3) legyen i←i+1 (azaz növeljük i értékét 1-gyel), és
   (4) folytassuk az algoritmust az (1) lépésben, amíg i≤n fennáll.

Az algoritmus eredményeként minden ismétléses kombinációhoz kölcsönösen egyértelműen hozzárendeltünk egy B-vel kezdődő, a B és X karakterek csoportjaiból álló sorozatot, amelyben pontosan 'n' darab B és 'k' darab X érték található (ahol az i-dik B után szereplő X karakterek száma meghatározza az i-dik elem k_i gyakoriságát).

Az első B elemet változatlanul hagyva (n+k−1) darab elem marad, amelyekben (n−1) darab B és 'k' darab X elem ismétlődik. Ezeknek az elemeknek minden különböző ismétléses permutációja külcsönösen egyértelműen megfeleltethető 'n' elem egy 'k'-ad rendű ismétléses kombinációjának (és megfordítva).

Tehát az (n−1) darab B és 'k' darab X elemből álló sorozatok, vagyis összesen (n+k−1) elem összes (n−1) és k-ad rendű ismétléses permutációja megadja az 'n' elem k-ad osztályú ismétléses kombinációinak számát. Ez a korábbiaknak megfelelően
    (n+k−1)!/((n−1)!*k!)
ami éppen a bizonyítandó formulát adja (vö. Cser et al. 1962: 458-459; Vilenkin 1987: 50-51).

Például az (1,2,3,4) számok 3-ad osztályú ismétléses kombinációi a következőképpen állíthatók elő:

/* ismétléses kombinációk, C4,3,i (1,2,3,4) */

var i,j,k;
var sorszam=0;

for(var i=1;i<=4;i++) {
 for(var j=i;j<=4;j++) {
  for(var k=j;k<=4;k++) {
   writeln("{"+i+","+j+","+k+"}");
   sorszam++;
   }
  }
 }
writeln();
writeln("a kombinációk száma: "+sorszam);

writeln("-----");

Vegyük észre, hogy a kombinációk egyes elemeinek kiválasztását végző 'for' ciklusok ciklusváltozóinak (i, j és k) kezdőértéke biztosítja, hogy az {i,j,k} alakú kombinációk mindegyikében i≤j≤k teljesüljön, vagyis az elemek a kombinációban nem csökkenő sorrendben szerepeljenek.

A program futásának eredménye:

A fenti program eredményei formálisan "halmazok", de az ismétlődő elemek jelzik, hogy valójában multihalmazokat kaptunk. Ezeket például az alábbi programmal tudjuk megjeleníteni:

/* ismétléses kombinációk, C4,3,i (1,2,3,4) multihalmazként megjelenítve*/

function mh(x) {
 var y=0;
 if(x==i) y++;
 if(x==j) y++;
 if(x==k) y++;
 return "("+x+","+y+")";
 }

var i,j,k;
var sorszam=0;

for(var i=1;i<=4;i++) {
 for(var j=i;j<=4;j++) {
  for(var k=j;k<=4;k++) {
   write("["+i+","+j+","+k+"] = {");
   writeln(mh(1)+","+mh(2)+","+mh(3)+","+mh(4)+"}");
   sorszam++;
   }
  }
 }
writeln();
writeln("Az ismétléses kombinációk száma: "+sorszam);

writeln("-----");

A program futásának eredménye:

Az ismétléses kombinációk alapfeladata

Legyen egy urnában 4 különböző színű golyó, és legyen mindegyik színű golyóból "végtelen sok" (de legalábbis "elegendően" sok abban az értelemben, hogy egy adott színű golyó kihúzása után mindig maradjon még az adott színből). Ebben az esetben nincs különbség a visszatevés nélküli és a visszatevéses mintavétel között, mivel egy adott színű golyó kihúzása után is lényegében "ugyanannyi" színű golyó marad, akár visszatesszük a golyót, akár nem.

(1) Vegyünk ki az urnából 3 golyót. Helyezzük el a kivett golyókat egy másik urnában (vagyis a mintavétel során a kihúzás sorrendje nem számít). Hányféleképpen tehetjük ezt meg?

(2) Helyezzük el a kihúzott golyókat egymás mellé a színek sorrendjében (legyen például az egyes színárnyalatok kódja vörös=0, sárga=1/6, zöld=1/3, cián=1/2, kék=2/3, magenta=5/6 stb., és helyezzük el a kihúzott golyókat a színkódok szerint). Hányféle elrendezés lehetséges?

---

Az ismétléses kombinációk alapfeladatát megfogalmazhatjuk kockadobásokkal is. Dobjunk háromszor egy dobókockával, és írjuk fel a kapott dobásokat egy papírlapra nagyság szerint. Hány különböző dobássorozatot tudunk felírni?

Az ismétléses variációk megkaphatók úgy, hogy képezzük az ismétléses kombinációkat, és az egyes kombinációk ismétléses permutációit összegezzük. Például legyen három különböző színű golyónk egy urnában, legyen az urnában "elegendő számú" golyó minden színből, és húzzunk ki öt golyót az urnából. Ekkor egyrészt
C₃^5,i= (3+5−1)!/(5!*(7−5)!)= 7!/(5!*2!)= 7*6/2= 21
másrészt pedig
V₃^5,i= 3⁵= 243
teljesül. Ellenőrizzük az ismétléses variációk és kombinációk kapcsolatát egy programmal:

/* az ismétléses variációk és ismétléses kombinációk kapcsolata */

function fakt(n) {
 var f=1;
 for(var p=2;p<=n;p++) {
  f*=p;
  }
 return f;
 }

function ism_perm(k1,k2,k3) {
 var n=k1+k2+k3;
 var ip=fakt(n);
 ip/=fakt(k1);
 ip/=fakt(k2);
 ip/=fakt(k3);
 return ip;
 }

var i,j,k,l,m;
var sorszam=0;
var t=[-1,1,1,3]; // a 0-dik elemet nem használjuk
var s=[-1,0,0,0]; // az 1,2,3 számok gyakorisága
var sum=0;

for(var i=1;i<=3;i++) {
 s[i]++;
 for(var j=i;j<=3;j++) {
  s[j]++;
  for(var k=j;k<=3;k++) {
   s[k]++;
   for(var l=k;l<=3;l++) {
    s[l]++;
    for(var m=l;m<=3;m++) {
     s[m]++;
     write("("+i+","+j+","+k+","+l+","+m+")");
     var ip=ism_perm(s[1],s[2],s[3]);
     writeln(" -> "+ip);
     sum+=ip;
     sorszam++;
     s[m]--;
     }
    s[l]--;
    }
   s[k]--;
   }
  s[j]--;
  }
 s[i]--;
 }

writeln();
writeln("az ismétléses kombinációk száma: "+sorszam);
writeln("az ismétléses variációk száma: "+sum);

writeln("______________________");

A program futásának eredménye:

Gyakorló feladatok (vö. Szabó 1996: 82-87)

(1) Hat kosárlabdacsapat körmérkőzést játszik egymással.

(1.1) Hányféle sorrendben végezhetnek a csapatok?

Megoldás: P₆=6!

(1.2) Egyfordulós körmérkőzés esetén hány mérkőzést jelent ez?

Megoldás: C₆²= (⁶ ₂)= 6!/(2!*4!)=15

(1.3) Kétfordulós körmérkőzés esetén hány mérkőzést jelent ez?

Megoldás: V₆²=2*C₆²=6*5=2*15=30

(2) Hány 19-cel kezdődő, ötjegyű szám készíthető az {1,3,5,7,9} számjegyekből, ha

(2.1) a számok képzésénél egy számjegy csak egyszer szerepelhet?

Megoldás: P₍₅₋₂₎=3!

(2.2) a számok képzésénél egy számjegy akárhányszor szerepelhet?

Megoldás: V₅^3,i=5³=125

(3) Hány páros, négyjegyű szám képezhető az {1,2,3,4} számjegyekből, ha

(3.1) minden számjegy csak egyszer szerepelhet?

(3.2) egy számjegy akárhányszor szerepelhet?

(4) Hány 3-mal osztható, négyjegyű szám képezhető az {1,2,3,4} számjegyekből, ha

(4.1) minden számjegy csak egyszer szerepelhet?

Megoldás: 0 (mivel 1+2+3+4=10 nem osztható 3-mal)

(4.2) egy számjegy akárhányszor szerepelhet?

(5) Hány 6-tal osztható, négyjegyű szám képezhető az {1,2,3,4} számjegyekből, ha

(5.1) minden számjegy csak egyszer szerepelhet?

(5.2) egy számjegy akárhányszor szerepelhet?

(6) Hány 10-zel osztható, négyjegyű szám képezhető a {0,1,2,3,4} számjegyekből, ha

(6.1) minden számjegy csak egyszer szerepelhet?

Megoldás: V₄³=4*3*2=24

(6.2) egy számjegy akárhányszor szerepelhet?

Megoldás: 4*V₅^2,i=4*5*5=100

(7) Egy 6 főből álló baráti társaság az étteremben egy kör alakú asztal körül elhelyezett 6 széken akar helyet foglalni. Hányféleképpen történhet ez meg, ha két elhelyezkedést akkor és csak akkor tekintünk különbözőnek, ha a társaságnak van legalább egy olyan tagja, akinek vagy a bal oldali, vagy a jobb oldali szomszédja a két esetben különböző?

Megoldás: P₍₆₋₁₎=5! (ötlet: üljön le egy székre valaki, és a többi ember cseréljen székeket)

(8) 10 ember ül le egy kerek asztal mellé. Hányféleképpen helyezkedhetnek el, ha azt akarjuk, hogy

(8.1) Kovács és Lakatos feltétlen egymás mellett üljön?

(8.2) Kovács és Lakatos soha ne üljön egymás mellett?

(9) 10 ember ül le egymás mellé egy egyenes asztal egyik oldalán. Hányféleképpen helyezkedhetnek el, ha azt akarjuk, hogy

(9.1) Kovács és Lakatos feltétlen egymás mellett üljön?

(9.2) Kovács és Lakatos soha ne üljön egymás mellett?

(10) 10 ember ül le egymás mellé egy egyenes asztal mindkét oldalán (az asztalfőn egyik oldalon sem ül senki). Hányféleképpen helyezkedhetnek el, ha azt akarjuk, hogy

(10.1) Kovács és Lakatos feltétlen egymás mellett üljön?

(10.2) Kovács és Lakatos soha ne üljön egymás mellett?

(11) 6 piros, 3 fehér, 2 kék golyót hányféleképpen lehet egymás mellé helyezni, hogy a hat piros golyó ne kerüljön egymás mellé?

Megoldás: P₁₁^2,3,6,i−P₆^1,2,3,i= 11!/(2!*3!*6!)−6!/(2!*3!)= 4620−60= 4560

(12) Hány nyolcjegyű szám képezhető a (0,0,0,0,1,1,1,1) számjegyekből?

Megoldás: P₇^3,4,i=7!/(3!*4!)=35

(13) Hány különböző gyöngysort lehet készíteni 20 gyöngyszemből, ha

(13.1) a gyöngysor két végét nem kötjük össze, és 10 fehér és 10 kék gyöngyünk van?

(13.2) a gyöngysor két végét nem kötjük össze, és 10 fehér, 5 kék és 5 piros gyöngyünk van?

(13.3) a gyöngysor két végét összekötjük, és 5 fehér és 15 kék gyöngyünk van?

(13.4) a gyöngysor két végét összekötjük, és 10 fehér, 5 kék és 5 piros gyöngyünk van?

(14) Az {1,2,3,...,14,15} számokat sorozatba rendezzük. Hány olyan eset van, amelyben az {1,2} számok csökkenő sorrendben kerülnek egymás mellé?

(15) 10 tanuló között hányféleképpen lehet kiosztani 3 különböző tárgyat, ha egy tanuló több tárgyat is kaphat?

(16) Hány olyan hatjegyű szám van, amelynek minden számjegye 6-nál nagyobb és 9-nél kisebb?

(17) Hány olyan ötjegyű szám van, amelynek a második és a harmadik jegye 3-as, és a szám 5-tel osztható?

(18) 15 betűből és 10 számból autórendszámot készítünk úgy, hogy a rendszámban először 3 betű, majd 3 számjegy szerepeljen (pl. ABC 123). Hány autót tudunk így megkülönböztetni?

(19) Egy dobókockával ötször dobunk egymás után. Hányféle dobássorozat lehetséges?

Megoldás: V₆^5,i=6⁵=7776

(20) Két kockával dobva hány esetben kapunk összesen legalább 8-at?

(21) Egy udvarban 10 kacsa és 24 tyúk van.

(21.1) Egy jó ebédet akarunk főzni. Hányféleképpen választhatunk ki egy kacsát és egy tyúkot?

Megoldás: C₁₀¹*C₂₄¹= 240

(21.2) Egy jó és bőséges ebédet akarunk főzni. Hányféleképpen választhatunk hozzá ki két kacsát és két tyúkot,

(a) ha a kiválasztás sorrendje nem számít?

Megoldás: C₁₀²*C₂₄²= (¹⁰ ₂)*(²⁴ ₂)= (5*9)*(12*23)= 12420

A fenti feladat példa hipergeometrikus eloszlásra N=34, s=10, n=4 és k=2 paraméterekkel, ahol az összes eset számát C_Nⁿ= (^N _n)= (³⁴ ₄)= (34*11*4*31)= 46376 adja meg.

(b) ha a kiválasztás sorrendje is számít?

Megoldás: P₄^2,2,i*V₁₀²*V₂₄²= [4!/(2!*2!)]*[10!/(10−2)!]*[24!/(24−2)!]= (4*3/2)*(10*9)*(24*23)= 298080

Ebben az esetben az összes eset számát V₃₄⁴= 34!/(34−4)!= 34*33*32*31= 1113024 adja meg.

(21.2) Főzés előtt meg szeretnénk vizsgálni a háziállatok minőségét. Hányféleképpen választhatunk ki két kacsát és két tyúkot úgy, hogy egy kacsát vagy egy tyúkot többször is kiválaszthatunk (azaz minden véletlen kiválasztás után "visszatesszük" a kiválasztott madarakat),

(a) ha a kiválasztás sorrendje nem számít?

Megoldás: C₁₀^2,i*C₂₄^2,i= (¹¹ ₂)*(²⁵ ₂)= (5*11)*(12*25)= 16500

Ebben az esetben az összes eset számát C₃₄^4,i= 37!/(4!*33!)= 37*3*35*17= 66045 adja meg.

(b) ha a kiválasztás sorrendje is számít?

Megoldás: P₂^2,2,i*V₁₀^2,i*V₂₄^2,i= (⁴ ₂)*10²*24²= 6*100*576= 345600

A fenti feladat példa binomiális eloszlásra N=34, s=10, n=4 és k=2 paraméterekkel, ahol az összes eset számát Nⁿ= 34⁴= 1336336 adja meg.

(22) Egy biológiadolgozatban 10 kérdés szerepel. Az egyes válaszokat kérdésenként {A,B,C,D,E} betűk jelölik (minden kérdésre öt lehetséges választ sorolunk fel).

(22.1) Ha minden kérdésre pontosan egy jó választ adhatunk, hányféle különböző választássorozat lehetséges?

(22.2) Ha minden kérdésre legalább egy és legfeljebb négy jó választ adhatunk (amerikai stílusú teszt), hányféle különböző választássorozat lehetséges?

(23) Hányféleképpen lehet 90 számból 5 számot kihúznunk (visszatevés nélkül), ha a számok sorrendje nem számít? (lottóhúzás)

Megoldás: C₉₀⁵= (⁹⁰ ₅)= 90!/(5!*(90−5)!= 90*89*88*87*86/(5*4*3*2*1)= 19*89*11*29*86= 46,390,894

(24) 100 darab tévékészülék között 10 hibás (selejtes) darab van. Hányféleképpen tudunk 15 készüléket úgy kiválasztani, hogy a kiválasztott készülékek között

(24.1) ne legyen hibás?

(24.2) 1 hibás legyen?

(24.3) 3 hibás legyen?

(24.4) legfeljebb 3 hibás legyen?

(25) 5 lány és 3 fiú röplabdázni szeretne. Hányféleképpen alkothatunk két, négyfős csapatot, ha azt szeretnénk, hogy mindkét csapatban legyen legalább egy fiú?

(26) Egy csomag 52 lapos franciakártya csomagból 10 lapot húzunk ki. Hány esetben lesz ezek között

(26.1) legalább egy király?

(26.2) pontosan egy király?

(26.3) legalább két király?

(26.4) pontosan két király?

(27) Egy rekeszben 20 üveg sor van. 15 üvegben világos sör, 5 üvegben barna sör van. Hányféleképpen választhatunk ki 6 üveg sört úgy, hogy pontosan két barna sörünk legyen?

(28) Egy osztályban 14 fiú és 16 lány van. Hányféleképpen lehet 4 fiút és 4 lányt kiválasztani, akik együtt mennek moziba?

(29) Egy urnában húsz cédula van 1-től 20-ig megszámozva. Húzzunk ki 5 cédulát úgy, hogy minden húzás után a kihúzott cédulát visszatesszük. Hány esetben lesz a kihúzott legkisebb szám nagyobb 6-nál?

(30) Egy 10 elemű halmaznak hány 3 elemű részhalmaza van?

(31) Hány háromjegyű páros szám készíthető az 1, 2, 3, 4, 5 számjegyekből, ha egy számot többször is felhasználhatunk?

Megoldás: 2*V₅^2,i= 2*5²= 2*25= 50

(32) Hány háromjegyű szám készíthető a 0, 1, 3, 5 számjegyekből, ha egy számot többször is felhasználhatunk?

Megoldás: 3*V₄^2,i= 3*4²= 3*16= 48

(33) Egy 10 csapatos bajnokságban hányféle sorrend alakulhat ki a dobogón?

Megoldás: V₁₀³= 10!/(10−3)!= 10*9*8= 720

(34) Hányféleképpen lehet sorba rakni 2 kék, 2 zöld és 3 piros golyót?

Megoldás: P₆^2,2,3= 7!/(2!*2!*3!)= 7*6*5*4/(2*2)= 7*6*5= 210

(34) Egy urnában van 4 kék, és 5 piros golyó. A golyókat kihúzás után zsebre tesszük. Hányféleképpen tudunk kihúzni három golyót?

Megoldás: C₂^3,i= (2+3−1)!/(3!*(4−3)!)= 4!/3!= 4
A megoldások: KKK, KKP, KPP, PPP

A fenti feladat mutatja, hogy ismétléses kombinációk esetén három golyó kihúzása esetén csak az számít, hogy az urnában háromnál több golyó legyen minden színből. (Például ugyanezt az eredményt kapjuk, ha az urnában 8 kék, és 4 piros golyó van.)

(34) Egy urnában van 4 kék, és 5 piros golyó. A golyókat kihúzás után zsebre tesszük. Hányféleképpen tudunk kihúzni hat golyót?

Megoldás: C₂^3,i= (2+3−1)!/(3!*(4−3)!)= 4!/3!= 4
A megoldások (k+p=6 alakban): 1+5=6, 2+4=6, 3+3=6 és 4+2=6

Ha 'k' kék és 'p' piros golyót húzunk, akkor k+p=6 teljesül. Ez k≤4 és p≤5 miatt csak úgy teljesülhet, ha legalább 1 kék és legalább 2 piros golyót húzunk. Ezután a fennmaradó 3 kék és 3 piros golyóból kell kihúznunk három golyót.