Kombinatorikk

Kombinatorikk er eit område innan matematikken som går ut på å telje kombinasjonar av objekt i mengder som vert delte etter gjevne reglar. Kombinatorikken inngår i den diskrete matematikken og er nært slekta til sannsynsteorien i og med at ein trenger ein metode å finne mengda mogelege utfall, og mengda måtar eit visst utfall kan opptre, for å rekne ut sannsynet for det nemnde utfallet.

Typiske kombinatoriske spørsmål kan vere om kor mange moglege måtar det er å stokke ein kortstokk, som 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 noko over 80 undesillionar. Eit noko meir handgripeleg problem kan vere mengda mogelege lottorekkjer, som kan reknast ut ved ved binomialkoeffisienten ${34 \choose 7}$ = 5 379 616.

Permutasjonar og kombinasjonar

Ved oppteljing av permutasjonar og kombinasjonar, er det generelt to sett av reglar. Ein snakkar ofte om trekningar med eller utan tilbakelegging og der rekkjefølgja av trekninga er vesentleg eller uvesentleg, eller utvalet er ordna eller uordna, høvesvis permutasjon og kombinasjon. Det heile kan illustrerast ved norske pengespel. Lotto er eit spel der trekninga skjer utan tilbakelegging (eit tal kan berre trekkjast éin gong) og rekkjefølgja er uvesentleg. Vi snakkar om 5 379 616 ulike kombinasjonar utan repetisjon. Tipping er derimot eit spel der dei tre utfalla for kvar kamp kan repeterast eit vilkårleg mengd gonger, men der rekkjefølgja av utfalla er høgst vesentleg. Ein tippekupong har 531 441 ulike permutasjonar med repetisjon.

Permutasjonar med repetisjon

Eit ordna utval med repetisjonar kan skildrast ved ei trekning med tilbakelegging der rekkjefølgja er vesentleg. Mengder permutasjonar der ein gjer k trekningar og det er n element å velje mellom kvar gong er

$n^{k}$.

Viss ein tek for seg tippekupongen, er det for kvar kamp tre moglege utfall – H, U og B. Det er tolv kampar. For første kampen har du tre høve, for andre tre høve og så vidare tolv gonger. Multipliserer ein høva ein har for kvar «trekning», får ein mengder permutasjonar.

Permutasjonar utan repetisjon

Ser ein for seg ein urne med ballar, der ein trekkjer éin og éin og ikkje legg dei tilbake etterkvart, og rekkjefølgda er vesentleg, vil mengder høve reduserast med éin for kvar trekning. Har ein n ballar og utfører k trekningar, er mengda permutasjonar

${\frac {n!}{(n-k)!}}=nPk$.

Skal du til dømes velje tre personar blant fem, vil du første gong ha 5 å velje mellom, så 4 og deretter 3, det vil si 5!/(5-3)! = 5!/2! = 5×4×3=60.

Dersom n = k vil mengda permutasjonar vere lik n!, fordi n!/(n-n)! = n!/0! = n!/1 = n!. Skal du til dømes stille opp tre menneske i kø, kan du gjere det på 3!=3×2×1=6 måtar. For den første plassen har du 3 val, for den andre 2 og for den siste berre 1. Multipliserer ein dette saman, får ein mengda permutasjoner.

Kombinasjonar utan repetisjon

Dersom rekkefølgja ikkje betyr noko og ein skal trekke ut k element blant n utan tilbakelegging, er mengda kombinasjonar lik binomialkoeffisienten

${n \choose k}={{n!} \over {k!(n-k)!}}=nCk$.

Dette kjem av at om ein trekkjer k element frå n, får ein nPk (sjå ovanfor) høve. Men dette talet inkluderer alle moglege rekkjefølgjer å arrangere dei k elementa på, som er k!. Ved å dele nPk på k!, får ein då nCk, eller mengder kombinasjonar av k element blant n.

Mengder moglege kombinasjonar i Lotto er 34C7 = 5 379 616, og i Viking-Lotto 48C6 = 12 271 512.

Kombinasjonar med repetisjon

Dersom rekkjefølgja ikkje tyder noko og ein skal trekkje ut k element blant n med tilbakelegging, er mengder kombinasjonar

${{(n+k-1)!} \over {k!(n-1)!}}={{n+k-1} \choose {k}}={{k+r-1} \choose {k-1}}$.

Skal du til dømes kjøpe tre smultringar og det er ti typar å velje mellom, er mengder moglege kjøp (10 + 3 − 1)! / 3!(10 − 1)! = 220.

For å kome fram til dette kan ein ta utgangspunkt i ei trekning der vi ikkje tek omsyn til rekkjefølgja ballane blir trekt i, men vi skal leggje ballane tilbake i urna etterkvart. Det sentrale er difor kor mange gonger kvar av dei n ballane har vorte trekt ut. Viss, til dømes, n = 3 og k = 5, er éit mogleg resultat at vi trekkjer ball nummer 1 to gonger, ball nummer 2 tre gonger, og ball nummer 3 ingen gonger.

Vi kan sjå for oss dette på ein annan måte. Vi har k identiske ballar, og n nummererte behaldarar, og vi skal plassere dei k ballane i behaldarane. Det viktige er ikkje kva for ball som hamner i kva for behaldarar, men kor mange ballar som hamner i behaldar 1, kor mange som hamner i behaldar 2, og så vidare.

I dømet ovanfor vil behaldar 1 få to ballar, og behaldar 2 få tre ballar, medan behaldar 3 blir verande tom. Ein måte å representere det på er følgjande måte:

OO|OOO|

Her representerer sirkelen ein ball, medan dei vertikale strekane representerer skiljeveggane mellom behaldarane. På same vis vil til dømes

O|OO|OO

innebere at behaldar 1 inneheld éin ball, medan behaldar 2 og 3 inneheld to ballar kvar.

Ein ser då at mengder uordna utval når ein trekkjer k ballar ut av ei urne med n ballar med tilbakelegging, er det same som mengder måtar ein kan arrangere k sirklar og n-1 vertikale strekar på ei linje. Svaret på dette er

${n+k-1 \choose k}.$

Enumerativ kombinatorikk

Det mest elementære innan kombinatorikk er å berekne mengder måtar avgjorde mønster kan formast. La S vere ei mengd med n element. Kombinasjonar og permutasjonar av k element frå S vil utgjere delmengder av k element frå denne mengda er delmengder av S vil utgjere delmengder med k element frå S. Permutasjonar av k element frå denne mengda vil utgjere sekvensar av k ulike element frå S. Formlar for å berekne mengder moglege permutasjonar og kombinasjonar er tilgjengelege og viktige innan kombinatorikken.

Enumerativ kombinatorikk søker etter ulike måtar å skildre ein teljefunksjon, f(n), som gjeven ei samling endelege mengder {S_i}, typisk indeksert med naturlege tal, tel mengder element i S_n for kvar n.

Dei enklaste slike funksjonar er lukka formlar, som kan uttrykkjast ved samansetning av enkle funksjonar som fakultet, eksponentar og så vidare. Til dømes er mengder moglege ulike rekkjefølgder i ein kortstokk med n kort f(n) = n!.

Det er ikkje alltid det er praktisk eller tilfredsstillande å uttrykkje slike funksjonar på den måten. Til dømes kan f(n) vere mengda ulike delmengder av heiltal i intervallet [1, n] som ikkje inneheld to etterfølgjande heiltal. Viss n = 4, tilfredsstiller mengdene

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

der $\phi =(1+{\sqrt {5}})/2$, eller det gylne snittet. Men no har det seg sånn at vi ser på ein teljefunksjon, og at vi har ${\sqrt {5}}$ i ein slik vert gjerne som uestetisk. Eit alternativ som viser tydeleg at f(n) er eit positivt heltall, kan f(n) i staden uttrykkast som rekursjonsrelasjonen

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

men vilkåret f(1) = 1 og f(2) = 1.

Ein annan angrepsvinkel er å finne ein asymptotisk formel:

$f(n)\sim g(n)$

der g(n) er ein kjend funksjon og f(n) nærmar seg g(n) når n går mot uendeleg. I nokre tilfelle vil ein asymptotisk formel vere å føretrekke framfor ein horribelt komplisert lukka formel som ikkje seier noko om oppførselen til dei talte objekta. For dømet ovanfor vil ein asymptotisk formel vere

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

når n blir stor.

f(n) kan òg uttrykkast som ein genererande funksjon, som vanlegvis anten er ein vanleg genererande funksjon

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

eller ein eksponensiell genererande funksjon:

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

Har ein kome fram til ein genererande funksjon, kan ein ved hjelp av den vere i stand til å hente ut all informasjon gjeven av dei tidlegare nemnde tilnærmingane. I tillegg gjev dei naturlege operasjonane på ein genererande funksjon, addisjon, multiplikasjon, derivasjon etc. høvet til å bruke resultata frå eit kombinatorisk problem til å utleie løysingar for andre.

Sjå òg

• Binomialkoeffisient
• Fakultet
• Grafteori
• Nim
• Partisjon
• Permutasjon
• Sannsynsteori

Kjelder

• Denne artikkelen bygger på «Kombinatorikk» frå Wikipedia på bokmål, den 31. desember 2011.