Tre ulike typer utvalg

På sida Introduksjon til kombinatorikk jobbet du med å lage par av tellebrikker av fem ulike farger etter ulike kriterier. Vi hadde to sett av kriterier. Det ene var om vi kunne bruke den samme fargen om igjen, og det andre var om rekkefølgen vi la brikkene i, hadde noe å si. På denne sida skal vi gå mer nøye inn på disse ulike utvalgene med andre eksempler.

Tenk deg at du skal fylle ut en tippekupong med tolv fotballkamper helt tilfeldig. Du legger tre lapper i en hatt. På den ene lappen står det H for hjemmeseier, på den andre står det U for uavgjort, og på den tredje lappen står det B for borteseier.

Den første lappen du trekker, skal angi resultatet i kamp nummer 1. Lappen må så legges tilbake i hatten før resultatet i kamp nummer 2 trekkes. Vi har derfor et utvalg med tilbakelegging. Det betyr også noe hvilken rekkefølge lappene trekkes i. Det er ikke likegyldig om du først trekker H og så U, eller om du først trekker U og så H. Det vil si at utvalget er ordnet.

Vi har da et ordnet utvalg med tilbakelegging. Vi har like mange muligheter på hver plass, og vi finner antall muligheter totalt slik:

$3·3·3·3·3·3·3·3·3·3·3·3=3^{12}$

I en klasse med 30 elever skal vi velge et styre med leder, nestleder og sekretær. Vi velger først leder. Da har vi 30 mulige utfall. Så velger vi nestleder. Da er det 29 elever igjen å velge mellom siden lederen ikke kan være nestleder også. For hver av de 30 mulige lederne kan vi få 29 mulige nestledere, altså $30·29$ muligheter. Til slutt velger vi sekretær. Da er det 28 elever igjen å velge mellom (eller 28 lapper igjen i hatten, om vi skal sammenligne med forrige eksempel).

Siden rekkefølgen betyr noe og en person ikke kan ha flere verv, har vi altså et ordnet utvalg uten tilbakelegging.

Produktregelen sier at antall mulige styresammensetninger blir $$ 30·29·28=24 360$$. Dette kan også skrives som

$30·29·28=30·\left(30-1\right)·\left(30-2\right)=30·\left(30-1\right)·\left(30-3+1\right)$

Formel for antall permutasjoner

I dagligtalen vil vi kanskje kalle det vi har regnet ut i ordnede utvalg for kombinasjoner. I matematikken bruker vi i stedet begrepet permutasjoner, og dette beskriver måter en mengde elementer kan ordnes eller sorteres på.

Vi ser nå på en generell formell. Vi skal velge et styre på $$ r$$ elever ut fra en gruppe på $$ n$$ elever. Kriteriene er de samme som ovenfor. Antall mulige styresammensetninger blir da

$n·\left(n-1\right)·\left(n-2\right)· ...·\left(n-r+1\right)$

Ser du at dette er "begynnelsen" på $$ n$$-fakultet? Hvis vi multipliserer med$\left(n-r\right)!$ i telleren og nevneren, får vi $$ n!$$ i telleren:

$\begin{array}{rcl}n·\left(n-1\right)·\left(n-2\right)· ...& ·& \left(n-r+1\right)\\ & & \\ & =& \frac{n·\left(n-1\right)·\left(n-2\right)· ... ·\left(n-r+1)\right)·\left(n-r\right)!}{1·\left(n-r\right)!}\\ & & \\ & =& \frac{n!}{\left(n-r\right)!}\end{array}$

Med tallene fra eksempelet vårt kan vi skrive utregningen slik:

$$ \begin{array}{rcl}\frac{30!}{27!} & =& \frac{30·29·28·\cancel{27·26·25·24·23·22·21·20·19·18·17·16·15·14·13·12·11·10·9·8·7·6·5·4·3·2·1}}{\cancel{27·26·25·24·23·22·21·20·19·18·17·16·15·14·13·12·11·10·9·8·7·6·5·4·3·2·1}}\\ & =& 30·29·28\end{array}$$

Hva gjør vi rent praktisk når vi deler $$ n!$$ på $$ (n-r)!$$?

Vi kan se for oss at vi først regner ut antall måter å stille opp de 30 elevene på. De skal stå ved siden av hverandre. Det er de 30! over brøkstreken. For hver permutasjon av de tre i styret kan vi ha 27! ulike permutasjoner av resten av klassen. Derfor må vi dele på 27! for å finne ut hvor mange permutasjoner vi har av tre elever.

Antall muligheter i disse situasjonene betegnes med $$ nPr$$ der $$ P$$ står for permutasjoner.

Permutasjoner i GeoGebra

I GeoGebra er kommandoen nPr(<n>, <r>) der det første tallet er $$ n$$ og det andre tallet $$ r$$.

Vi kan finne antall ulike styrer slik:

Permutasjoner i Python

Vi kan importere generatoren permutations() fra biblioteket itertools:

1from itertools import permutations
2
3elever = [] #liste over elever
4
5for i in range(30):
6    elever.append(i) #legger inn 30 tall i lista
7
8Styre = list(permutations(elever,3)) #lager liste av permutasjonene
9
10print(f"Antall lag er {len(list(Styre))}.") #skriver ut lengden på lista

På samme måte som da vi fant kombinasjonsmulighetene, må vi lage en liste av permutasjonene før vi kan telle dem.

For å finne svaret må vi kjøre programmet.

Formelen må også gjelde for det tilfelle at $$ r=n$$. Da er$(n-r)!=0!$. Her ser vi nytten av å definere $0!=1$, siden dette gjør at når  r = n, er

$nPr=\frac{n!}{\left(n-r\right)!}=\frac{n!}{\left(n-n\right)!}=\frac{n!}{0!}=\frac{n!}{1}=n!$

Dette vil for eksempel gjelde dersom vi skal finne ut hvor mange rekkefølger elever i en klasse kan stille seg opp i, slik vi så over.

I en klasse med 30 elever skal vi nå bare velge et styre bestående av tre elever. Rekkefølgen på de som blir trukket ut, betyr ikke noe. En person kan ikke ha flere verv. Vi har da en situasjon der vi leter etter antall måter å kombinere de ulike elevene med hverandre på, altså teller vi her antall kombinasjoner. Vi har et uordnet utvalg uten tilbakelegging.

Dersom dette hadde vært et ordnet utvalg uten tilbakelegging, slik som i det forrige eksempelet, ville antall kombinasjoner ha vært gitt ved

$$ 30P3=\frac{30!}{(30-3)!}=\frac{30!}{27!}=30·29·28$$

I dette tilfellet, når rekkefølgen ikke har noen betydning, faller det bort noen muligheter. Når vi trekker ut tre elever, kan disse tre elevene sorteres (permuteres) på $3·2·1=3!=6$ ulike måter. Disse seks permutasjonene inneholder de samme tre elevene, og vi kan bare ha med en av disse permutasjonene i opptellingen av antall kombinasjoner. Vi får altså et antall utvalg som er seks ganger for stort når vi bruker formelen for nPr, så vi må dele formelen på 6, det vil si 3!.

Vi får derfor

$$ \frac{30·29·28}{6}=\frac{30·29·28}{3·2·1}=\frac{30·29·28}{3!}=\frac{30!}{27!·3!}=4060$$

kombinasjonsmuligheter i dette tilfellet.

Generelt får vi at antall mulige kombinasjoner for et uordnet utvalg uten tilbakelegging av r elementer fra n elementer er gitt med formelen

$\frac{n·\left(n-1\right)·\left(n-2\right)· ... ·\left(n-r+1\right)}{r!}=\frac{n!}{r!\left(n-r\right)!}$

På sida Fakultet, Pascals trekant og binomialkoeffisienten så vi eksempler på utvalg der binomialkoeffisienter fra Pascals talltrekant ga antall kombinasjonsmuligheter. Dette var nettopp slike uordnede utvalg uten tilbakelegging.

Vi husker skrivemåtene for binomialkoeffisientene som $nCr$ og $\left(\begin{array}{c}n\\ r\end{array}\right)$. Dette leser vi som "n over r".

Vi har nå funnet en formel for binomialkoeffisienten som vi kan bruke til å regne "for hånd" som et alternativ til å sette opp Pascals talltrekant.

Vi så i introduksjonen til kombinatorikk at vi kunne finne alle disse tre utvalgstypene i ett og samme eksempel. Nå skal vi oppsummere med et annet eksempel.

Vi trekker to lapper fra en hatt med lapper nummerert fra 1 til 6. Alle mulighetene for å lage par er illustrert i tabellen nedenfor.

• Et ordnet utvalg med tilbakelegging vil si alle parene i tabellen. Vi kan finne antall par ved regning:

  $n^r=6^2=36$

• Et ordnet utvalg uten tilbakelegging gir parene i de gule og blå rutene i tabellen, til sammen 30 ruter. Parene i de hvite rutene faller bort. Vi kan igjen finne antall permutasjoner ved regning:

  $nPr=\frac{n!}{\left(n-r\right)!}=\frac{6!}{\left(6-2\right)!}=\frac{6!}{4!}=\frac{6·5·\cancel{4!}}{\cancel{4!}}=6·5=30$

• Et uordnet utvalg uten tilbakelegging gir kun 15 kombinasjoner. Parene i de hvite rutene faller bort, og parene i de gule og de blå rutene blir identiske fordi for for eksempel $$ \mathrm{(1,2)\; =\; (2,1).}$$ Vi finner antall kombinasjoner ved regning:

  $nCr=6C2=\left(\begin{array}{c}6\\ 2\end{array}\right)=\frac{6!}{2!\left(6-2\right)!}=\frac{6·5·\cancel{4!}}{2!·\cancel{4!}}=\frac{30}{2}=15$

De tre ulike utvalgene er oppsummert i tabellen nedenfor.

Den observante leser husker kanskje at vi helt til å begynne med også snakket om uordnede utvalg med tilbakelegging. Disse har vi ikke gått nærmere inn på fordi formelen for disse utvalgene er utenfor kompetansemålene i S1. Som du så, kan du likevel finne ut av det ved å telle litt – så lenge mulighetene ikke er for mange.

Det er også viktig å huske på at du kan møte på kombinatorikkproblemer som ikke faller inn under en av disse utvalgstypene, og du må kanskje tenke litt selv. Da er det viktig å merke seg multiplikasjonsprinsippet, eller produktregelen for kombinasjoner.

Produktregelen for kombinasjoner

Tenk deg at du skal kjøpe ny mobiltelefon, og at det finnes to produsenter å velge mellom. Hver av disse produsentene har tre modeller, og hver modell kan fås i fire farger. Hvor mange forskjellige mobiltelefoner kan du ende opp med?

For hver produsent kan du velge tre modeller. Det gir $2·3$ kombinasjonsmuligheter.

For hver av disse mulighetene kan du velge fire farger. Antall kombinasjonsmuligheter totalt blir da $2·3·4=24$. Du kan ende opp med 24 forskjellige mobiltelefoner.

Produktregelen for kombinasjoner i Python

Fra itertools kan vi importere generatoren product(). Denne lager de ulike kombinasjonene for oss. Vi kan lage et program som skriver ut og teller opp de ulike kombinasjonene:

1from itertools import product
2
3produsent = ["produsent1","produsent2"]
4modell = ["modellA", "modellB", "modellC"]
5farge = ["blå","rød","hvit","svart"]
6
7kombinasjoner = list(product(produsent,modell,farge))
8
9print(kombinasjoner)
10print(f"Antall kombinasjoner er {len(kombinasjoner)}.")

I programmet over har vi lagd tre lister, over produsentene, modellene og fargene. Så har vi lagd ei liste med alle de mulige kombinasjonene av ett element fra hver liste. Kopier og kjør programmet for å se hva resultatet blir!

Du ser at lengden på lista kombinasjoner er 24, akkurat som vi regnet ut over. Hvis du ser på utskriften, vil du se at hvert av de 24 elementene i denne lista er ei liste for seg selv, med tre elementer: én produsent, én modell og én farge.

Vi kan skrive ut en bestemt av disse kombinasjonene. Prøv å utvide programmet over med kodelinjene under og se hva som skjer:

print(kombinasjoner[0])

print(kombinasjoner[0][1])

Du vil se at den første print-kommandoen vil gi deg det første elementet i lista kombinasjoner som er ('produsent1','modellA','blå').

Den andre kommandoen vil gå til det første elementet i lista kombinasjoner og finne det andre elementet i den lista. Utskriften blir ('modellA').