18 Kombinatorikk

Question 1

18.1 Inklusjon-og-eksklusjonsprinsippet for to mengder

Answer 1

Når A og B er to endelige mengder, sier inklusjon-og-eksklusjonsprinsippet at:
|A ∪ B| = |A| + |B| - |A ∩ B|

Question 2

18.2 Inklusjon-og-eksklusjonsprinsippet for tre mengder

Answer 2

Hvis A, B og C er tre endelige mengder, sier inklusjon-og-eksklusjonsprinsippet at:

|A ∪ B ∪ C| = |A| + |B| + |C| - (|A ∩ B| + |A ∩ C| + |B ∩ C| + |A ∩ B ∩ C|)

Question 3

18.3 Multiplikasjonsprinsippet

Answer 3

Hvis vi skal treffe en rekke uavhengige valg, er det totale antallet muligheter produktet av antall muligheter ved hvert valg. Dette kalles multiplikasjonsprinsippet.

Question 4

18.4 Permutasjon

Answer 4

En permutasjon av en mengde er en ordning av elementene i den. Hvis vi allerede har en ordning, er en permutasjon en endring av rekkefølgen.

Question 5

18.5 Fakultetsfunksjonen

Answer 5

Hvis n er et naturlig tall, er

n! = n · (n - 1) · (n - 2) ··· 1.

Vi lar 0! = 1, og vi leser n! som “n fakultet”.

Question 6

18.6 Ordnet utvalg, k-permutasjon

Answer 6

Hvis en mengde med n elementer er gitt, og vi ønsker å velge k av disse i rekkefølge, er det n(n - 1)(n - 2) ··· (n - (k - 1)) måter å gjøre dette på. Dette kalles et ordnet utvalg, eller en k-permutasjon av n elementer.

Question 7

18.7 Kombinasjon

Answer 7

En kombinasjon er et utvalg av elementer fra en mengde hvor rekkefølgen ikke spiller noen rolle. En k-kombinasjon av en mengde A er en delmengde av A med k elementer.

Question 8

18.8 Binomialkoeffisient

Answer 8

Hvis n og k er naturlige tall slik at k ⩽ n, defineres (n ¦ k) ved

[se vedlagt bilde].

Vi leser (n ¦ k) som “n velg k”, og et slik tall kalles en binomialkoeffisient.