Kombinationer med upprepning
Kombinationer med upprepning liknar vanliga kombinationer, men vi tillåter att elementen ur den underliggande mängden M upprepas.
Definition och formel
Vi börjar med ett trevligt exempel: du kommer in i en affär och vill köpa tolv läskflaskor inför en utflykt. I hyllan finns totalt fyra olika sorter. Nu har du flera möjligheter att köpa flaskorna – du kan till exempel köpa 5 Fanta, 2 Sprite, 1 Pepsi och 4 Zingo eller så kan du köpa precis tre flaskor av varje sort. På hur många olika sätt kan du köpa flaskorna så att du får precis tolv?
Vi har alltså grundmängden M = {Fanta, Sprite, Pepsi, Zingo} och frågar hur många k-tipler, där k = 12, det finns som innehåller element ur mängden M och där ordningen inte spelar roll?
Härledningen av formeln är lite svårare än för andra kombinatoriska uppgifter. Först föreställer vi oss vårt inköp som en följd av nollor och ettor så att antalet ettor motsvarar antalet köpta flaskor av en viss sort och nollan avgränsar de olika sorterna. Följden 111011101111101 säger oss alltså att vi har köpt tre Fanta (de första tre ettorna), sedan tre Sprite (0 är en avgränsare, nästa tre ettor), sedan fem Pepsi (0 avgränsare och sedan fem ettor) och till sist en Zingo. Hela principen visas i följande figur:
Om vi skulle vilja köpa 6 Fanta, 4 Sprite, 2 Zingo och ingen Pepsi, skulle följden se ut så här:
Vi lägger märke till att längden på den här följden alltid är lika med 15 – det måste finnas 12 ettor för att vi ska köpa totalt 12 flaskor. Och det måste finnas tre avgränsare för att vi ska kunna skilja fyra olika sorter åt. Då återstår frågan: hur många sådana följder med längden 15 innehåller precis tre nollor?
Det räcker att räkna ut placeringen av nollorna – när vi har placerat 3 nollor bland 12 ettor har vi en giltig kombination av flaskor. Med andra ord: vi har totalt 15 platser och 3 av dem måste vi fylla med nollor. De återstående platserna fyller vi automatiskt med ettor.
Det här är nu en enkel uppgift om kombinationer utan upprepning. De 15 platserna numrerar vi med talen {1, …, 15} och nu väljer vi ur den här mängden alltid tre tal, varvid vi får tre index där vi placerar en nolla. T.ex. för kombinationen {2, 4, 7} skulle vi få följden: 101011011111111. På plats 2, 4 och 7 står en nolla, resten är ettor. Det finns alltså totalt
olika sätt att placera nollorna på de 15 platserna och därmed också 455 olika möjligheter att köpa 12 flaskor, om vi har fyra olika sorter.
Det föregående resonemanget kan vi generalisera. Om vi har en mängd M med n element och väljer k-tipler ur den, där de enskilda elementen kan upprepas, så bildar vi en följd av nollor och ettor med längden n + k − 1 (k ettor och n − 1 nollor) och undersöker på hur många sätt vi kan placera n − 1 nollor, så antalet kombinationer med upprepning är lika med
Den sista omskrivningen kunde vi tillåta oss tack vare de grundläggande sambanden mellan binomialkoefficienter.
Lösta exempel
- På hur många sätt kan man fördela 20 fribiljetter till en premiär på stadsteatern mellan 10 pensionärer? Det är ett exempel på kombinationer med upprepning, eftersom en pensionär kan få flera, potentiellt alla, fribiljetter. Vi måste bara inse vad som är n och vad som är k. I själva verket väljer vi kombinationer av 20 element ur 10 pensionärer, med andra ord bildar vi en följd av nollor och ettor så att följden har längden 29 och innehåller 20 ettor och 9 nollor. Alltså n = 10, k = 20. Vi får resultatet:
Kapitel: Kombinatorik, Ordnat urval, Permutationer, Kombinationer, Ordnat urval med återläggning, Kombinationer med upprepning, Hur många olika PIN-koder finns det?
