Urnemodeller i kombinatorikk

Urnemodeller brukes i kombinatorikk for å visualisere enkelte telleproblemer. Man har gitt en urne med n forskjellige baller, og man skal trekke ut k baller etter hverandre. Det er viktig at de n ballene kan skilles fra hverandre – de kan for eksempel være nummerte fra 1 til n. Man skiller mellom ordnet og uordnet utvalg, og om ballene trekkes med eller uten tilbakelegging. Man får da fire forskjellige urnemodeller, og man ønsker å regne ut på hvor mange forskjellige måter man kan trekke de k ballene.

Ordnet utvalg betyr at rekkefølgen ballene trekkes i har betydning. At ballene trekkes med tilbakelegging betyr at man først trekker en ball, skriver ned resultatet, og legger ballen tilbake i urnen før man trekker en ny.

Vi antar at ballene er nummerert fra 1 til n.

Ordnet utvalg med tilbakelegging

Her trekker man først en ball, skriver ned nummeret på ballen, og legger den tilbake i urnen. Så repeterer man det til man har trukket k baller. Hver gang man trekker en ball, er det n forskjellige muligheter. Ifølge produktregelen, kan de k ballene derfor trekkes på n^k måter.

På en norsk tippekuppong er det tolv kamper, hvor hver kamp kan ha tre forskjellige utfall, nemlig hjemmeseier, borteseier og uavgjort. Man kan da forestille seg at man har en urne med tre baller, merket H, U og B. Deretter trekker tolv baller, med tilbakelegging. Antall måter en tippekuppong kan fylles ut på blir derfor 3¹² = 531441.

Ordnet utvalg uten tilbakelegging

Her trekker man k baller, men uten å legge tilbake ballene i urnen etterhvert. Hver ball kan derfor trekkes høyst én gang. Vi kan igjen bruke produktregelen for å bestemme på hvor mange måter dette kan gjøres. Når vi trekker den første ballen, inneholder urnen n baller, så det er n muligheter for den første ballen. Når vi trekker den andre ballen, er det bare n-1 baller igjen i urnen, så de to første ballene kan derfor trekkes på n × (n-1) forskjellige måter. Antall måter vi kan trekke ut k baller, blir dermed

$n\times (n-1)\times (n-2)\times \ldots \times (n-k+1)={\frac {n!}{(n-k)!}}.$

Dette tallet skrives iblant nPk, eller P(n,k). (Uttrykket n! er en skrivemåte for produktet 1 · 2 · ... · n. Se fakultet.)

Et eksempel hvor denne urnemodellen kan benyttes er følgende: Man har ni skiløpere til disposisjon, og må sette opp et staffettlag med fire deltagere. Det er både viktig å vite hvilke skiløpere som tas med, og rekkefølgen deres. Antall måter dette kan gjøres på blir dermed 9!/5! = 3024.

Uordnet utvalg uten tilbakelegging

Her er rekkefølgen på ballene som trekkes uten betydning. Det vil si at om vi trekker ball nummber 5, 2 og 8, regnes det som det samme som om vi trekker ballene 2, 8 og 5. Hvis vi har trukket ut k baller, kan disse ballene ordnes på k! forskjellige måter. Vi kan derfor tenke oss at vi først trekker ut et ordnet utvalg på k baller, og deretter ignorerer rekkefølgen de ble trukket i. Vi regnet ut ovenfor at de k ballene kan trekkes ut på P(n,k) forskjellige måter. Vi deler deretter med k!, siden rekkefølgen er likegyldig. Antallet måter vi kan trekke ut k baller er dermed

${\frac {P(n,k)}{k!}}={\frac {n!}{k!(n-k)!}}={n \choose k}.$

Dette skrives iblant nCk eller C(n,k). (Se binomialkoeffisient.)

For et eksempel på denne urnemodellen, kan man tenke seg en lottokuppong. Her skal man trekke ut sju tall fra trettifire, men rekkefølgen på tallene er likegyldig. Antall måter man kan fylle ut en lottokuppong blir dermed C(34,7) = 5379616.

Uordnet utvalg med tilbakelegging

I den siste urnemodellen tar vi ikke hensyn til rekkefølgen ballene trekkes i, men vi skal legge ballene tilbake i urnen etterhvert. Det sentrale er derfor hvor mange ganger hver av de n ballene har blitt trukket ut. Hvis, for eksempel, n = 3 og k = 5, er ett mulig resultat at vi trekker ball nummer 1 to ganger, ball nummer 2 tre ganger, og ball nummer 3 ingen ganger.

Vi kan se for oss dette på en annen måte. Vi har k identiske baller, og n nummerte beholdere, og vi skal plassere de k ballene i beholderne. Det viktige er ikke hvilke baller som havner i hvilke beholdere, men hvor mange baller som havner i beholder 1, hvor mange som havner i beholder 2, og så videre.

I eksempelet ovenfor, vil beholder 1 få to baller, og beholder 2 få tre baller, mens beholder 3 forblir tom. En måte å representere det på er følgende måte:

OO|OOO|

Her representerer sirkelen en ball, mens de vertikale strekene representerer skilleveggen mellom beholderne. På samme måte vil for eksempel

O|OO|OO

innebære at beholder 1 inneholder én ball, mens beholder 2 og 3 inneholder to baller hver.

Man ser da at antall uordnede utvalg når man trekker k baller ut av en urne med n baller med tilbakelegging, er det samme som antall måter man kan arrangere k sirkler og n-1 vertikale streker på en linje. Svaret på dette er

${n+k-1 \choose k}.$