Kombinasjoner med gjentakelse
Kombinasjoner med gjentakelse ligner på vanlige kombinasjoner, bare at vi tillater at elementene fra den underliggende mengden M kan gjentas.
Definisjon og formel
Vi begynner med et fint eksempel: Du kommer inn i en butikk og vil kjøpe tolv flasker øl til hytteturen. I hylla har de fire ulike typer flaskeøl. Nå har du flere muligheter for hvordan du kan kjøpe ølet — du kan for eksempel kjøpe 5 Ringnes, 2 Hansa, 1 Aass og 4 Frydenlund, eller du kan kjøpe nøyaktig tre flasker av hvert merke. Hvor mange ulike muligheter finnes det til sammen for å kjøpe flaskeølet slik at du har nøyaktig tolv flasker?
Vi har altså grunnmengden M = {Ringnes, Hansa, Aass, Frydenlund}, og vi spør: Hvor mange k-tupler, der k = 12, finnes det som inneholder elementer fra mengden M og der rekkefølgen ikke har noe å si?
Utledningen av formelen er ganske mye mer sammensatt enn for de andre kombinatoriske oppgavene. Først forestiller vi oss innkjøpet vårt som en følge av nuller og enere, slik at antall enere svarer til antall kjøpte flasker av det aktuelle merket, og en null skiller de ulike merkene. Så 111011101111101 forteller oss at vi har kjøpt tre Ringnes (de tre første enerne), deretter tre Hansa (0 er skilletegnet, så tre enere til), deretter fem Aass (0 som skilletegn og så fem enere) og til slutt én Frydenlund. Hele prinsippet vises i følgende figur:
Hvis vi ville kjøpe 6 Ringnes, 4 Hansa, 2 Frydenlund og ingen Aass, ville følgen sett slik ut:
La oss legge merke til at lengden på denne følgen alltid er lik 15 — det må være 12 enere for at vi skal kjøpe til sammen 12 øl. Og det må være tre skilletegn for at vi skal kunne skille de fire ulike merkene. Det gjenstår å regne ut hvor mange slike følger med lengde 15 som inneholder nøyaktig tre nuller.
Det holder at vi regner ut plasseringen av nullene — når vi har plassert 3 nuller blant 12 enere, har vi en gyldig kombinasjon av øl. Med andre ord: Vi har til sammen 15 plasser, og 3 av dem må vi fylle med null. De resterende plassene fyller vi automatisk med enere.
Dette er allerede en enkel oppgave om kombinasjoner uten gjentakelse. Vi nummererer de 15 plassene med tallene {1, …, 15} og velger nå alltid tripler av tall fra denne mengden, og da får vi tre indekser der vi setter null. For eksempel for kombinasjonen {2, 4, 7} får vi følgen: 101011011111111. På 2., 4. og 7. plass står det null, resten er enere. Det finnes altså til sammen
ulike måter å plassere nullene på de 15 plassene, og dermed også 455 ulike muligheter for å kjøpe 12 øl når vi har fire ulike typer øl.
Denne tankegangen kan vi generalisere. Hvis vi har en mengde M med n elementer og velger k-tupler fra den, slik at de enkelte elementene kan gjentas, setter vi sammen en følge av nuller og enere med lengde n + k − 1 (k enere og n − 1 nuller) og finner ut på hvor mange måter vi kan plassere n − 1 nuller. Antallet kombinasjoner med gjentakelse er dermed lik
Den siste omskrivingen kunne vi tillate oss takket være de grunnleggende sammenhengene mellom binomialkoeffisientene.
Løste eksempler
- På hvor mange måter kan 20 gratisbilletter til premieren på en ny film fordeles blant 10 pensjonister? Dette er et eksempel på kombinasjoner med gjentakelse, for én pensjonist kan få flere gratisbilletter, potensielt alle. Vi må bare være klare over hva som er n og hva som er k. Egentlig velger vi kombinasjoner av 20 blant 10 pensjonister, eller med andre ord lager vi en følge av nuller og enere med lengde 29 som inneholder 20 enere og 9 nuller. Så n = 10, k = 20. Vi får resultatet:
Kapitler: Kombinatorikk, Ordnet utvalg, Permutasjoner, Kombinasjoner, Ordnet utvalg med tilbakelegging, Kombinasjoner med gjentakelse, Hvor mange ulike PIN-koder finnes det?
