5.1 Kombinatorikk | Matematikk S1

Systematisk telling med permutasjoner og kombinasjoner.

55 min

16 oppgaver

MultiplikasjonsprinsippetPermutasjonKombinasjonFakultet

Din fremgang i kapitlet

0 / 16 oppgaver

Hva er kombinatorikk?

Kombinatorikk handler om systematisk telling. Vi skal lære metoder for å telle antall mulige utfall uten å liste opp alle sammen.

Eksempel: Hvor mange forskjellige PIN-koder med 4 siffer finnes det? Å liste opp alle er upraktisk, men med kombinatorikk kan vi beregne dette raskt.

I dette kapittelet skal vi se på:
- Multiplikasjonsprinsippet
- Permutasjoner (ordnede utvalg)
- Kombinasjoner (uordnede utvalg)

Multiplikasjonsprinsippet

Multiplikasjonsprinsippet er grunnlaget for all kombinatorikk:

> Hvis en prosess kan gjennomfores i $k$ trinn, der trinn 1 kan gjores pa $n_1$ mater, trinn 2 kan gjores pa $n_2$ mater (uavhengig av trinn 1), osv., sa er totalt antall mater a gjennomfore hele prosessen:
> $n_1 \cdot n_2 \cdot n_3 \cdot \ldots \cdot n_k$

Multiplikasjonsprinsippet

k

✏️Eksempel 1: Antrekk

En person har 4 forskjellige skjorter og 3 forskjellige bukser. Hvor mange forskjellige antrekk kan personen velge?

Losning:

Vi bruker multiplikasjonsprinsippet:

- Valg av skjorte: 4 muligheter
- Valg av bukse: 3 muligheter

Totalt antall antrekk = $4 \cdot 3 = 12$

Trediagram:
``Skjorte 1 ─┬─ Bukse 1 → Antrekk 1 ├─ Bukse 2 → Antrekk 2 └─ Bukse 3 → Antrekk 3

Skjorte 2 ─┬─ Bukse 1 → Antrekk 4 ├─ Bukse 2 → Antrekk 5 └─ Bukse 3 → Antrekk 6

Skjorte 3 ─┬─ Bukse 1 → Antrekk 7 ├─ Bukse 2 → Antrekk 8 └─ Bukse 3 → Antrekk 9

Skjorte 4 ─┬─ Bukse 1 → Antrekk 10 ├─ Bukse 2 → Antrekk 11 └─ Bukse 3 → Antrekk 12``

Svaret er 12 antrekk.

✏️Eksempel 2: PIN-koder

Hvor mange forskjellige 4-sifrede PIN-koder finnes det?

Losning:

En PIN-kode bestar av 4 siffer, der hvert siffer kan vaere fra 0 til 9.

For hvert siffer har vi 10 muligheter (0, 1, 2, ..., 9).

Multiplikasjonsprinsippet gir:

$10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10\,000$

Det finnes 10 000 forskjellige PIN-koder.

📝Oppgave 5.1.1

Et spisested tilbyr 3 forretter, 5 hovedretter og 4 desserter. Hvor mange forskjellige treretters menyer kan man sette sammen?

📝Oppgave 5.1.2

Et passord skal besta av 3 bokstaver (fra A til Z) etterfulgt av 2 siffer (fra 0 til 9). Hvor mange forskjellige passord kan lages?

Fakultet

Nar vi skal ordne $n$ objekter i rekkefolge, bruker vi fakultet.

Fakultet

n

✏️Eksempel 3: Rekkefolge av personer

Pa hvor mange mater kan 5 personer stille seg i ko?

Losning:

Vi skal ordne 5 personer i rekkefolge.

- Forste plass: 5 muligheter
- Andre plass: 4 muligheter (en person er brukt)
- Tredje plass: 3 muligheter
- Fjerde plass: 2 muligheter
- Femte plass: 1 mulighet

Totalt: $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

Det er 120 mater a stille 5 personer i ko.

📝Oppgave 5.1.3

Regn ut folgende:

6!

\displaystyle \frac{8!}{6!}

\displaystyle \frac{10!}{8! \cdot 2!}

Permutasjoner

En permutasjon er et ordnet utvalg der rekkefolgen har betydning.

Permutasjoner

r

✏️Eksempel 4: Pallplasser

I et lokalt lop deltar 8 personer. Pa hvor mange mater kan gull, solv og bronse fordeles?

Losning:

Vi skal velge 3 personer fra 8, der rekkefolgen har betydning (gull ≠ solv ≠ bronse).

$P(8,3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336$

Alternativt:
- Gull: 8 muligheter
- Solv: 7 muligheter
- Bronse: 6 muligheter

Totalt: $8 \cdot 7 \cdot 6 = 336$

Det er 336 mater a fordele pallplassene.

📝Oppgave 5.1.4

En klubb med 12 medlemmer skal velge president, visepresident og sekretaer. Pa hvor mange mater kan dette gjores?

📝Oppgave 5.1.5

Et bibliotek har 7 forskjellige boker som skal plasseres pa en hylle. Pa hvor mange mater kan bokene ordnes?

Kombinasjoner

En kombinasjon er et uordnet utvalg der rekkefolgen ikke har betydning.

Kombinasjoner

r

✏️Eksempel 5: Lottotrekning

I en forenklet lottotrekning skal 6 tall trekkes fra tallene 1 til 34. Hvor mange forskjellige kombinasjoner finnes?

Losning:

Her er rekkefolgen uviktig - det spiller ingen rolle om 7 trekkes for eller etter 23.

$C(34,6) = \binom{34}{6} = \frac{34!}{6!(34-6)!} = \frac{34!}{6! \cdot 28!}$

Vi regner:
$= \frac{34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}$

$= \frac{34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{720}$

$= \frac{968\,330\,880}{720} = 1\,344\,904$

Det finnes 1 344 904 forskjellige kombinasjoner.

✏️Eksempel 6: Komitevalg

Fra en gruppe pa 10 studenter skal det velges en komite pa 4 personer. Pa hvor mange mater kan komiteen velges?

Losning:

Her har rekkefolgen ingen betydning - alle komitemedlemmer er likeverdige.

$C(10,4) = \binom{10}{4} = \frac{10!}{4! \cdot 6!} = \frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1} = \frac{5040}{24} = 210$

Det er 210 mater a velge komiteen.

📝Oppgave 5.1.6

Regn ut folgende:

\binom{7}{3}

\binom{8}{2}

\binom{6}{6}

\binom{5}{0}

📝Oppgave 5.1.7

En handballklubb har 15 spillere. Treneren skal velge ut 7 spillere til en kamp. Pa hvor mange mater kan laget velges?

Nar bruker vi hva?

Situasjon	Formel	Eksempel
Rekkefolgen teller	$\displaystyle P(n,r) = \frac{n!}{(n-r)!}$	Pallplasser, PIN-koder
Rekkefolgen teller ikke	$\displaystyle C(n,r) = \frac{n!}{r!(n-r)!}$	Lotteri, velge lag

Huskeregel:
- Permutasjon: "Posisjon matters" (P)
- Kombinasjon: "Collection only" (C)

📝Oppgave 5.1.8

Avgjor om det er permutasjon eller kombinasjon, og beregn antallet:

Velge 3 representanter fra en gruppe pa 10 personer

Dele ut forste-, andre- og tredjepremie til 3 av 10 deltakere

Velge 2 kort fra en kortstokk med 52 kort

Kombinatorikk og sannsynlighet

Kombinatorikk er grunnlaget for a beregne sannsynligheter i situasjoner med like sannsynlige utfall:

$P(A) = \frac{\text{Antall gunstige utfall}}{\text{Antall mulige utfall}}$

Ved a bruke kombinatorikk kan vi telle bade teller og nevner systematisk.

En standard kortstokk har 52 kort fordelt på 4 farger:

Farge	Symbol	Farge på kortet
Hjerter	♥	Rød
Ruter	♦	Rød
Spar	♠	Sort
Kløver	♣	Sort

Hver farge har 13 kort: Ess (1), 2, 3, 4, 5, 6, 7, 8, 9, 10, Knekt, Dame, Konge.
Nyttige tall:
- Totalt: 52 kort
- Hver farge: 13 kort
- Røde kort: 26 (hjerter + ruter)

- Sorte kort: 26 (spar + kløver)

- Ess: 4 (ett i hver farge)
- Bildekort (knekt, dame, konge): 12 (3 per farge)

✏️Eksempel 7: Pokerhender

Fra en kortstokk med 52 kort trekkes 5 kort tilfeldig. Hva er sannsynligheten for a fa noyaktig 3 ess?

Losning:

Antall mulige utfall:
Vi velger 5 kort fra 52:
$\binom{52}{5} = \frac{52!}{5! \cdot 47!} = 2\,598\,960$

Antall gunstige utfall:
- Velge 3 ess fra 4: $\binom{4}{3} = 4$
- Velge 2 andre kort fra de 48 gjenvaerende: $\displaystyle \binom{48}{2} = \frac{48 \cdot 47}{2} = 1\,128$

Antall gunstige = $4 \cdot 1\,128 = 4\,512$

Sannsynlighet:
$P(3 \text{ ess}) = \frac{4\,512}{2\,598\,960} \approx 0{,}00174 \approx 0{,}17\%$

Sannsynligheten for noyaktig 3 ess er ca. 0,17%.

📝Oppgave 5.1.9

En klasse har 12 jenter og 8 gutter. Det skal trekkes en gruppe pa 5 elever tilfeldig. Hva er sannsynligheten for at gruppen bestar av noyaktig 3 jenter og 2 gutter?

📝Oppgave 5.1.10

En veske inneholder 6 rode og 4 bla kuler. Det trekkes 3 kuler tilfeldig uten tilbakelegging. Finn sannsynligheten for at:

Alle tre kulene er rode

Noyaktig 2 kuler er rode

Minst 1 kule er bla

📝Oppgave 5.1.11

Et sykehus har 5 leger og 8 sykepleiere. Det skal dannes et team pa 4 personer som ma inneholde minst 1 lege. Pa hvor mange mater kan teamet settes sammen?

📝Oppgave 5.1.12

I Lotto velges 7 tall fra tallene 1-34. Det trekkes ogsa 3 tilleggstall. Hva er sannsynligheten for a fa 4 rette pluss 1 tilleggstall?

Oppsummering

Multiplikasjonsprinsippet:
$n_1 \cdot n_2 \cdot \ldots \cdot n_k$ for uavhengige valg

Fakultet:
$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1$

Permutasjoner (ordnet utvalg):
$\displaystyle P(n,r) = \frac{n!}{(n-r)!}$

Kombinasjoner (uordnet utvalg):
$\displaystyle C(n,r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Sannsynlighet:
$\displaystyle P(A) = \frac{\text{gunstige}}{\text{mulige}}$

Situasjon

Formel

Eksempel

Rekkefolgen teller

\displaystyle P(n,r) = \frac{n!}{(n-r)!}

Pallplasser, PIN-koder

Rekkefolgen teller ikke

\displaystyle C(n,r) = \frac{n!}{r!(n-r)!}

Lotteri, velge lag

Farge

Symbol

Farge på kortet

Hjerter

♥

Rød

Ruter

♦

Rød

Spar

♠

Sort

Kløver

♣

Sort