Kombinatorikk

	Områder i anvendt matematikk
	Approksimasjonsteori
	Differensialligninger
	Kombinatorikk
	Sannsynlighetsteori

	Områder i algebra
	Abstrakt algebra
	Grupper ; Ringer ; Kropper
	Algebraisk geometri
	Elementær algebra
	Ligninger; Funksjoner
	Kombinatorikk
	Lineær algebra
	Vektorrom ; Matriser
	Tallære

Kombinatorikk er et område innen matematikken som går ut på å telle kombinasjoner av objekter i mengder som deles etter gitte regler. Kombinatorikken inngår i den diskrete matematikken og er nært beslektet med sannsynlighetsteorien i og med at man trenger en metode å finne antall mulige utfall, og antall måter et bestemt utfall kan opptre, for å beregne sannsynligheten for det nevnte utfallet.

Typiske kombinatoriske spørsmål kan være om hvor mange mulige måter det er å stokke en kortstokk, hvilket er 52! (52 fakultet), som er 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000, eller noe over 80 undesillioner. Et noe mer håndgripelig problem kan være antall mulige lottorekker, som kan beregnes ved binomialkoeffisienten ${34 \choose 7}$ = 5 379 616.

Hovedprinsipper

Multiplikasjonsprinsippet

Dersom $A$ og $B$ er to mengder, så er antall ordnede par $(a,b)$ som kan lages, med $a\in A$ og $b\in B$ , lik $|A|\cdot |B|$ . Mer generelt er kardinaliteten til det kartesiske produktet $|M_{1}\times M_{2}\times \dots \times M_{n}|=|M_{1}|\cdot |M_{2}|\cdots |M_{n}|$ .

For eksempel, hvis en middag skal bestå av en forrett, hovedrett og dessert, med $5$ forretter, $3$ hovedretter og $2$ desserter, kan man totalt lage $5\cdot 3\cdot 2=30$ middager.

Addisjonsprinsippet

Dersom $A$ og $B$ er to disjunkte mengder, vil kardinaliteten til unionet mellom $A$ og $B$ , $|A\cup B|=|A| |B|$ . Mer generelt, dersom $A_{1},A_{2},\dots A_{n}$ er disjunkte mengder vil $\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|.$ Med utgangspunkt i det forrige eksempelet, dersom middagen skal ha en hovedrett og enten en forrett eller en dessert, kan telleproblemet deles inn i to tilfeller. Mengden av alle middager med forrett vil være disjunkt fra mengden av alle middager med dessert. Fra multiplikasjonsprinsippet kan vi regne ut størrelsen på disse mengdene. Da følger et fra addisjonsprinsippet at antall middager vi kan lage er $5\cdot 3 5\cdot 2=25$ .

Inklusjon-ekslusjon-prinsippet

Det er ikke alltid man kan sikre at mengdene $A$ og $B$ er disjunkte. Dersom man bruker addisjonsprinsippet for å finne $|A\cup B|$ teller man elementene som er i både $A$ og $B$ dobbelt. Derfor sier inklusjon-eksklusjon-prinsippet at $|A\cup B|=|A| |B|-|A\cap B|$ .

Mer generelt, dersom vi objektene $A_{1},A_{2},\dots ,A_{n}$ kan ha egenskapene $P_{1},P_{2},\dots P_{r}$ , og $N(i)$ betegner antallet objekter som har egenskap $P_{i}$ , $N(i,j)$ betegner antallet objekter som har egenskap $P_{i},P_{j}$ der $i\neq j$ og så videre, vil antallet objekter som har minst én av egenskapene være gitt ved $\sum _{i=1}^{r}N(i) \sum _{i<j}N(i,j) \cdots (-1)^{r-1}N(1,2,\dots ,r)$

Permutasjoner og kombinasjoner

Ved opptelling av permutasjoner og kombinasjoner, er det generelt to sett av regler. Man snakker ofte om trekninger med eller uten tilbakelegging og der rekkefølgen av trekningen er vesentlig eller uvesentlig, eller utvalget er ordnet eller uordnet, henholdsvis permutasjon og kombinasjon. Det hele kan illustreres ved norske pengespill. Lotto er et spill der trekningen foregår uten tilbakelegging (et tall kan bare trekkes én gang) og rekkefølgen er uvesentlig. Vi snakker om 5 379 616 forskjellige kombinasjoner uten repetisjon. Tipping er derimot et spill der de tre utfallene for hver kamp kan repeteres et vilkårlig antall ganger, men der rekkefølgen av utfallene er høyst vesentlig. En tippekupong har 531 441 forskjellige permutasjoner med repetisjon.

Permutasjoner med repetisjon

Et ordnet utvalg med repetisjoner kan beskrives ved en trekning med tilbakelegging der rekkefølgen er vesentlig. Antall permutasjoner der man foretar k trekninger og det er n elementer å velge mellom hver gang er

n^{k}

.

Hvis man tar for seg tippekupongen, er det for hver kamp tre mulige utfall – H, U og B. Det er tolv kamper. For første kamp har du tre muligheter, for andre tre muligheter og så videre tolv ganger. Multipliserer man mulighetene man har for hver «trekning», får man antall permutasjoner.

Permutasjoner uten repetisjon

Ser man for seg en urne med baller, der man trekker én og én og ikke legger dem tilbake etterhvert, og rekkefølgen er vesentlig, vil antall muligheter reduseres med én for hver trekning. Har man n baller og trekker utfører k trekninger, er antall permutasjoner

{\frac {n!}{(n-k)!}}=n{\text{P}}k

.

Skal du for eksempel velge tre personer blant fem, vil du første gang ha 5 å velge mellom, så 4 og deretter 3, det vil si 5!/(5-3)! = 5!/2! = 5×4×3=60.

Dersom n = k vil antall permutasjoner være lik n!, fordi n!/(n-n)! = n!/0! = n!/1 = n!. Skal du for eksempel stille opp tre mennesker i kø, kan du gjøre det på 3!=3×2×1=6 måter. For den første plassen har du 3 valg, for den andre 2 og for den siste bare 1. Multipliserer man dette sammen, får man antall permutasjoner.

Kombinasjoner uten repetisjon

Dersom rekkefølgen ikke betyr noe og man skal trekke ut k elementer blant n uten tilbakelegging, er antall kombinasjoner lik binomialkoeffisienten

{n \choose k}={{n!} \over {k!(n-k)!}}=n{\text{C}}k

.

Dette kommer av at om man trekker k elementer fra n, får man nPk (se ovenfor) muligheter. Men dette tallet inkluderer alle mulige rekkefølger å arrangere de k elementene på, som er k!. Ved å dele nPk på k!, får man da nCk, eller antall kombinasjoner av k elementer blant n.

Antall mulige kombinasjoner i Lotto er 34C7 = 5 379 616, og i Viking-Lotto 48C6 = 12 271 512.

Kombinasjoner med repetisjon

Dersom rekkefølgen ikke betyr noe og man skal trekke ut k elementer blant n med tilbakelegging, er antall kombinasjoner

{{(n k-1)!} \over {k!(n-1)!}}={{n k-1} \choose {k}}={{n k-1} \choose {n-1}}

.

Skal du for eksempel kjøpe tre smultringer og det er ti typer å velge mellom, er antall mulige kjøp (10 3 − 1)! / 3!(10 − 1)! = 220.

For å komme frem til dette kan en ta utgangspunkt i en trekning der vi ikke tar 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}.

Enumerativ kombinatorikk

Det mest elementære innen kombinatorikk er å beregne antall måter bestemte mønster kan formes. La S være en mengde med n elementer. Kombinasjoner og permutasjoner av k elementer fra S vil utgjøre delmengder av k elementer fra denne mengden er delmengder av S vil utgjøre delmengder med k elementer fra S. Permutasjoner av k elementer fra denne mengden vil utgjøre sekvenser av k forskjellige elementer fra S. Formler for å beregne antall mulige permutasjoner og kombinasjoner er tilgjengelige og viktige innen kombinatorikken.

Enumerativ kombinatorikk søker etter forskjellige måter å beskrive en tellefunksjon, f(n), som gitt en samling endelige mengder {S_i}, typisk indeksert med naturlige tall, teller antall elementer i S_n for enhver n.

De enkleste slike funksjoner er lukkede formler, som kan uttrykkes ved sammensetning av enkle funksjoner som fakulteter, eksponenter og så videre. For eksempel er antall mulige forskjellige rekkefølger i en kortstokk med n kort f(n) = n!.

Det er ikke alltid det er praktisk eller tilfredsstillende å uttrykke slike funksjoner på den måten. For eksempel kan f(n) være antallet forskjellige delmengder av heltall i intervallet [1, n] som ikke inneholder to etterfølgende heltall. Hvis n = 4, tilfredsstiller mengdene {}, {1}, {2}, {3}, {4}, {1,3}, {1,4} og {2,4} dette kravet, så f(4) = 8. Det viser seg at f(n) er fibonaccitall nummer n 2, slik at funksjonen kan uttrykkes som en lukket formel:

f(n)={\frac {\phi ^{n 2}-(1-\phi )^{n 2}}{\sqrt {5}}}

der $\phi =(1 {\sqrt {5}})/2$ , eller det gyldne snitt. Men nå har det seg sånn at vi ser på en tellefunksjon, og tilstedeværelsen til ${\sqrt {5}}$ i en slik anses gjerne som uestetisk. Et alternativ som viser tydelig at f(n) er et positivt heltall, kan f(n) i stedet uttrykkes som rekursjonsrelasjonen

f(n)=f(n-1) f(n-2)\,\!

men betingelsen f(1) = 1 og f(2) = 1.

En annen angrepsvinkel er å finne en asymptotisk formel:

f(n)\sim g(n)

der g(n) er en kjent funksjon og f(n) nærmer seg g(n) når n går mot uendelig. I noen tilfeller vil en asymptotisk formel være å foretrekke fremfor en horribelt komplisert lukket formel som ikke sier noe om oppførselen til de talte objekter. For eksempelet ovenfor vil en asymptotisk formel være

f(n)\sim {\frac {\phi ^{n 2}}{\sqrt {5}}}

når n blir stor.

f(n) kan også uttrykkes som en genererende funksjon, som vanligvis enten er en vanlig genererende funksjon

\sum _{n\geq 0}f(n)x^{n}

eller en eksponensiell genererende funksjon:

\sum _{n\geq 0}f(n){\frac {x^{n}}{n!}}

Har man kommet frem til en genererende funksjon, kan man ved hjelp av den være i stand til å hente ut all informasjon gitt av de tidligere nevnte tilnærmelsene. I tillegg gir de naturlige operasjonene på en genererende funksjon, addisjon, multiplikasjon, derivasjon etc. muligheter til å bruke resultatene fra et kombinatorisk problem til å utlede løsninger for andre.

Se også

Litteratur

A. Søgaard og R. Tambs Lyche, Matematikk III for realgymnaset, Gyldendal Norsk Forlag, Oslo (1955).