Tre ulike typar utval

På sida Introduksjon til kombinatorikk jobba du med å lage par av teljebrikker av fem ulike fargar etter ulike kriterium. Vi hadde to sett av kriterium. Det eine var om vi kunne bruke den same fargen om igjen, og det andre var om rekkjefølgja vi la brikkene i, hadde noko å seie. På denne sida skal vi gå meir nøye inn på desse ulike utvala med andre døme.

Tenk deg at du skal fylle ut ein tippekupong med tolv fotballkampar heilt tilfeldig. Du legg tre lappar i ein hatt. På den eine lappen står det H for heimesiger, på den andre står det U for uavgjort, og på den tredje lappen står det B for bortesiger.

Den første lappen du trekkjer, skal gi resultatet i kamp nummer 1. Lappen må så bli lagt tilbake i hatten før resultatet i kamp nummer 2 blir trekt. Vi har derfor eit utval med tilbakelegging. Det betyr òg noko kva rekkjefølgje lappane blir trekte i. Det er ikkje likegyldig om du først trekkjer H og så U, eller om du først trekkjer U og så H. Det vil seie at utvalet er ordna.

Vi har då eit ordna utval med tilbakelegging. Vi har like mange moglegheiter på kvar plass, og vi finn talet på moglegheiter totalt slik:

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

I ein klasse med 30 elevar skal vi velje eit styre med leiar, nestleiar og sekretær. Vi vel først leiar. Då har vi 30 moglege utfall. Så vel vi nestleiar. Då er det 29 elevar igjen å velje mellom sidan leiaren ikkje kan vere nestleiar òg. For kvar av dei 30 moglege leiarane kan vi få 29 moglege nestleiarar, altså $30·29$ moglegheiter. Til slutt vel vi sekretær. Då er det 28 elevar igjen å velje mellom (eller 28 lappar igjen i hatten, om vi skal samanlikne med det førre døme).

Sidan rekkjefølgja betyr noko og ein person ikkje kan ha fleire verv, har vi altså eit ordna utval utan tilbakelegging.

Produktregelen seier at talet på moglege styresamansetningar blir $$ 30·29·28=24 360$$. Dette kan vi òg skrive 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 talet på permutasjonar

I daglegtalen vil vi kanskje kalle det vi har rekna ut i ordna utval for kombinasjonar. I matematikken bruker vi i staden omgrepet permutasjonar, og dette beskriv måtar ei mengde element kan ordnast eller sorterast på.

Vi ser no på ein generell formell. Vi skal velje eit styre på $$ r$$ elevar ut frå ei gruppe på $$ n$$ elevar. Kriteria er dei same som ovanfor. Talet på moglege styresamansetningar blir då

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

Ser du at dette er "byrjinga" på $$ n$$-fakultet? Dersom vi multipliserer med$\left(n-r\right)!$ i teljaren og nemnaren, får vi $$ n!$$ i teljaren:

$\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 tala frå dømet vårt kan vi skrive utrekninga 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}$$$

Kva gjer vi reint praktisk når vi deler $$ n!$$ på $$ (n-r)!$$?

Vi kan sjå for oss at vi først reknar ut talet på måtar å stille opp dei 30 elevane på. Dei skal stå ved sida av kvarandre. Det er dei 30! over brøkstreken. For kvar permutasjon av dei tre i styret kan vi ha 27! ulike permutasjonar av resten av klassen. Derfor må vi dele på 27! for å finne ut kor mange permutasjonar vi har av tre elevar.

Talet på moglegheiter i desse situasjonane skriv vi som $$ nPr$$ der $$ P$$ står for permutasjonar.

Permutasjonar i GeoGebra

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

Vi kan finne talet på ulike styre slik:

Permutasjonar i Python

Vi kan importere generatoren permutations() frå biblioteket itertools:

1from itertools import permutations
2
3elevar = [] #liste over elevar
4
5for i in range(30):
6    elevar.append(i) #legg inn 30 tal i lista
7
8Styre = list(permutations(elevar,3)) #lagar liste av permutasjonane
9
10print(f"Talet på lag er {len(list(Styre))}.") #skriv ut lengda på lista

På same måte som då vi fann kombinasjonsmoglegheitene, må vi lage ei liste av permutasjonane før vi kan telje dei.

For å finne svaret må vi køyre programmet.

Formelen må òg gjelde for det tilfellet at $$ r=n$$. Då er$(n-r)!=0!$. Her ser vi nytta av å definere $0!=1$, sidan dette gjer 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 til dømes gjelde dersom vi skal finne ut kor mange rekkjefølgjer elevar i ein klasse kan stille seg opp i, slik vi såg over.

I ein klasse med 30 elevar skal vi no berre velje eit styre beståande av tre elevar. Rekkjefølgja på dei som blir trekt ut, betyr ikkje noko. Ein person kan ikkje ha fleire verv. Vi har då ein situasjon der vi leiter etter talet på måtar å kombinere dei ulike elevane med kvarandre på, altså tel vi her talet på kombinasjonar. Vi har eit uordna utval utan tilbakelegging.

Dersom dette hadde vore eit ordna utval utan tilbakelegging, slik som i det førre dømet, ville talet på kombinasjonar ha vore gitt ved

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

I dette tilfellet, når rekkjefølgja ikkje har noka betydning, fell det bort nokre moglegheiter. Når vi trekkjer ut tre elevar, kan desse tre elevane bli sorterte (permuterte) på $3·2·1=3!=6$ ulike måtar. Desse seks permutasjonane inneheld dei same tre elevane, og vi kan berre ha med ein av desse permutasjonane i oppteljinga av talet på kombinasjonar. Vi får altså eit tal utval som er seks gonger for stort når vi bruker formelen for nPr, så vi må dele formelen på 6, det vil seie 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$$

kombinasjonsmoglegheiter i dette tilfellet.

Generelt får vi at talet på moglege kombinasjonar for eit uordna utval utan tilbakelegging av r element frå n element 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åg vi døme på utval der binomialkoeffisientar frå Pascals taltrekant gav talet på kombinasjonsmoglegheiter. Dette var nettopp slike uordna utval utan tilbakelegging.

Vi hugsar skrivemåtane for binomialkoeffisientane som $nCr$ og $\left(\begin{array}{c}n\\ r\end{array}\right)$. Dette les vi som "n over r".

Vi har no funne ein formel for binomialkoeffisienten som vi kan bruke til å rekne "for hand" som eit alternativ til å setje opp Pascals taltrekant.

Vi såg i introduksjonen til kombinatorikk at vi kunne finne alle desse tre utvalstypane i eitt og same døme. No skal vi samanfatte med eit anna døme.

Vi trekkjer to lappar frå ein hatt med lappar nummererte frå 1 til 6. Alle moglegheitene for å lage par er illustrerte i tabellen nedanfor.

• Eit ordna utval med tilbakelegging vil seie alle para i tabellen. Vi kan finne talet på par ved rekning:

  $n^r=6^2=36$

• Eit ordna utval utan tilbakelegging gir para i dei gule og blå rutene i tabellen, til saman 30 rutar. Para i dei kvite rutene fell bort. Vi kan igjen finne talet på permutasjonar ved rekning:

  $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$

• Eit uordna utval utan tilbakelegging gir berre 15 kombinasjonar. Para i dei kvite rutene fell bort, og para i dei gule og dei blå rutene blir identiske fordi for til dømes $$ \mathrm{(1,2)\; =\; (2,1)}$$. Vi finn talet på kombinasjonar ved rekning:

  $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$

Dei tre ulike utvala er samanfatta i tabellen nedanfor.

Den observante lesaren hugsar kanskje at vi heilt til å byrje med òg snakka om uordna utval med tilbakelegging. Desse har vi ikkje gått nærare inn på fordi formelen for desse utvala er utanfor kompetansemåla i S1. Som du såg, kan du likevel finne ut av det ved å telje litt – så lenge moglegheitene ikkje er for mange.

Det er òg viktig å hugse på at du kan møte på kombinatorikkproblem som ikkje fell inn under ein av desse utvalstypane, og du må kanskje tenkje litt sjølv. Då er det viktig å merke seg multiplikasjonsprinsippet, eller produktregelen for kombinasjonar.

Produktregelen for kombinasjonar

Tenk deg at du skal kjøpe ny mobiltelefon, og at det finst to produsentar å velje mellom. Kvar av desse produsentane har tre modellar, og kvar modell finst i fire fargar. Kor mange ulike mobiltelefonar kan du ende opp med?

For kvar produsent kan du velje tre modellar. Det gir $2·3$ kombinasjonsmoglegheiter.

For kvar av desse moglegheitene kan du velje fire fargar. Talet på kombinasjonsmoglegheiter totalt blir då $2·3·4=24$. Du kan ende opp med 24 ulike mobiltelefonar.

Produktregelen for kombinasjonar i Python

Frå itertools kan vi importere generatoren product(). Denne lagar dei ulike kombinasjonane for oss. Vi kan lage eit program som skriv ut og tel opp dei ulike kombinasjonane:

1from itertools import product
2
3produsent = ["produsent1","produsent2"]
4modell = ["modellA", "modellB", "modellC"]
5farge = ["blå","raud","kvit","svart"]
6
7kombinasjonar = list(product(produsent,modell,farge))
8
9print(kombinasjonar)
10print(f"Talet på kombinasjonar er {len(kombinasjonar)}.")

I programmet over har vi laga tre lister, over produsentane, modellane og fargane. Så har vi laga ei liste med alle dei moglege kombinasjonane av eitt element frå kvar liste. Kopier og køyr programmet for å sjå kva resultatet blir!

Du ser at lengda på lista kombinasjonar er 24, akkurat som vi rekna ut over. Dersom du ser på utskrifta, vil du sjå at kvart av dei 24 elementa i denne lista er ei liste for seg sjølv, med tre element: éin produsent, éin modell og éin farge.

Vi kan skrive ut ein bestemd av desse kombinasjonane. Prøv å utvide programmet over med kodelinjene under og sjå kva som skjer:

print(kombinasjonar[0])

print(kombinasjonar[0][1])

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

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