Kombinationer med gentagelser
Kombinationer med gentagelser ligner almindelige kombinationer, vi tillader bare, at elementerne fra den underliggende mængde M kan gentages.
Definition og formel
Vi begynder med et pænt eksempel: du kommer ind i en butik og vil købe tolv flaskeøl til en tur. På hylden har de i alt fire forskellige slags flaskeøl. Nu har du flere muligheder for, hvordan du kan købe flaskeøllene — du kan fx købe 5 pilsner, 2 hvedeøl, 1 IPA og 4 porter, eller du kan købe præcis tre flasker af hver slags. Hvor mange forskellige muligheder er der i alt for at købe flaskeøllene, så du har præcis tolv af dem?
Vi har således grundmængden M = {pilsner, hvedeøl, IPA, porter}, og vi spørger, hvor mange r-tupler, hvor r = 12, der findes, som indeholder elementer fra mængden M, og hvor rækkefølgen ikke har betydning?
Udledningen af formlen er her noget sværere end ved de andre kombinatoriske opgaver. Først forestiller vi os vores indkøb som en følge af nuller og et-taller, således at antallet af et-taller svarer til antallet af købte flaskeøl af den pågældende slags, og nullet adskiller de enkelte slags. Så 111011101111101 fortæller os, at vi har købt tre pilsner (de første tre 1-taller), så tre hvedeøl (0 er en skillevæg, de næste tre 1-taller), så fem IPA (0 som skillevæg og så fem 1-taller) og til sidst én porter. Hele princippet viser følgende figur:
Hvis vi ville købe 6 pilsner, 4 hvedeøl, 2 porter og ingen IPA, ville følgen se sådan ud:
Lad os bemærke, at længden af denne følge altid er lig med 15 — der skal være 12 et-taller, for at vi kan købe i alt 12 øl. Og der skal være tre skillevægge, for at vi kan adskille fire forskellige slags. Tilbage er at beregne, hvor mange sådanne følger af længden 15 der i alt findes, som indeholder præcis tre nuller?
Det er nok at beregne placeringen af nullerne — i det øjeblik vi fordeler 3 nuller mellem 12 et-taller, har vi en gyldig kombination af øl. Med andre ord: vi har i alt 15 pladser, og 3 af dem skal vi besætte med et nul. De resterende pladser besætter vi automatisk med et-taller.
Det er nu en enkel opgave om kombinationer uden gentagelser. De 15 pladser nummererer vi med tallene {1, …, 15}, og nu vælger vi fra denne mængde altid tripler af tal, hvorved vi får tre indekser, hvor vi placerer nullet. Fx for kombinationen {2, 4, 7} ville vi få følgen: 101011011111111. På 2., 4. og 7. plads er der et nul, resten er et-taller. Der findes således i alt
forskellige måder at fordele nullerne på de 15 pladser, og dermed også 455 forskellige muligheder for at købe 12 øl, når vi har fire forskellige slags øl.
Den foregående overvejelse kan vi generalisere. Hvis vi har en mængde af elementer M af størrelse n og vælger r-tupler fra den, hvor de enkelte elementer kan gentages, så sammensætter vi en følge af nuller og et-taller af længden n + r − 1 (r et-taller og n − 1 nuller) og undersøger, på hvor mange måder vi kan fordele n − 1 nuller, så antallet af kombinationer med gentagelser, som vi betegner K'(n, r), er lig med
Den sidste omskrivning kunne vi tillade os takket være de grundlæggende sammenhænge mellem binomialkoefficienter.
Løste eksempler
- På hvor mange måder kan man fordele 20 gratis billetter til en filmpremiere mellem 10 pensionister? Det er et eksempel på kombinationer med gentagelser, for én pensionist kan få flere, potentielt alle, gratis billetter. Vi skal bare gøre os klart, hvad n og r er. Faktisk vælger vi kombinationer af 20 elementer fra 10 pensionister, med andre ord danner vi en følge af nuller og et-taller, så følgen har længden 29, indeholder 20 et-taller og 9 nuller. Så n = 10, r = 20. Vi får resultatet:
Kapitler: Kombinatorik, Ordnet udvælgelse, Permutationer, Kombinationer, Ordnet udvælgelse med tilbagelægning, Kombinationer med gentagelser, Hvor mange forskellige pinkoder findes der?
