Jakob Bernoulli var den første som i Ars conjectandi tok opp begrepet permutasjoner, sortering av objekter på forskjellige måter, publisert posthumt i 1713. Abraham De Moivre (1667-1754) hadde arbeidet med normalfordeling i Approximatio ad summam terminorum binomii (a+b)n in seriem expansi (1733) (Approksimasjon til summen av termer i binomiske (a+b)n i utvidet serie).
Pierre Remond de Montmort (1678-1719) hadde i 1708 diskutert teorien bak kortspillet Treize, hvor 13 kort i en farge fra ess til konge stokkes og deles ut ett ad gangen samtidig som man teller høyt. De gangene kortet akkurat viser det tallet man teller har den som deler ut vunnet. Euler ble opptatt av kuriøse spørsmål tilknyttet doktrinen om kombinatorikk. Hvor mange måter er det muligheter er det å ordne n bokstaver:
n=0{}, n=1 {a}, n=2 {a,b}, n=3 {a,b,c}, n=4 {a,b,c,d}
Det er n! (n fakultet) måter å ordne n objekter.
\(\displaystyle n!= n\cdot (n-1)\cdot (n-2)\cdot \dots \cdot 3 \cdot 2\cdot 1\)
Uttrykt som produktnotasjon:
\(n!= \displaystyle\prod_{k=1}^n k\)
\(0!= 1\)
Ved utregning av binomialkoeffisienter benyttes faktultetsfunksjonen:
\(\displaystyle\frac {n!}{k!(n-k)!} = \binom{n}{k}\)
Fakultetsfunksjonen inngår i utregning av binomialkoeffisienter for k-te element i en mengde med k objekter fra en mengde med n objekter for eksempel i Pascals trekant.
Hvis vi har 3 mennesker (a,b,c) står i kø foran en disk kan disse ordnes 6 forskjellige måter:abc acb bac bca cab cba.
Det er 10 faktutlet (10!) = 3628800 mulige måter i å ordne 10 bokstaver.
Det er 52 fakultet (52!) mulige måter å stokke en kortstokk: ca. 8·1067 , et tall med 67 siffer.
Fakultetsfunksjonen n fakultet (n!) har den egenskapen at den stiger meget raskt med økende n.
I en skala på piano er det 12 tangenter. Det betyr at tonene i en skala kan sorteres på 12!= 479001600 forskjellige måter, de fleste kombinasjoner spilt etter hverandre låter ikke vakkert.
For hver av de 12 tonene er det to muligheter, bli spilt eller ikke spilt. Dette gir 212=4096 muligheter.
Kode med 4 siffer alle fra 0-9 gir 104 kombinasjoner.
Vi har tre klinkekuler med fargene rød, blå og grønn i en urne. Hvor mange måter kan de tre fargene ordnes på ? 3!= 6. Hvis vi har S={a,b,c} så kan disse ordnes på 3! forskjellige måter
Franskmannen Louis Braille konstruerte i 1825 en blindeskrift basert på kombinasjoner av 3∙2=6 opphøyde punkter, tre rekker med to i hver. Dette gir en punktskrift med 26-1=63 tegn som kan avleses med fingerputene.
Man kan foreta et utvalg med eller uten tilbakelegging.Når vi skal vudere hvor mange muligheter det er å ta ut et bestemt antall individer eller hendelser fra en prøve som er representativ for populasjonen, er det avgjørende om samme individ eller hendelse kan tas ut flere ganger (med tilbakelegging) eller ikke (uten tilbakelegging). Vi kan tenke oss en urne med kuler som er nummerert i rekkefølge. Hvis vi trekker ut en kule, noterer nummer og egenskaper ved kulen, og legger den tilbake blir dette trekning med tilbakelegging. Legger vi den ikke tilbake blir det trekning uten tilbakelegging. Er rekkefølgen av tallene på kulene avgjørende er det en ordnet trekning. Er rekkefølgen ikke avgjørende i trekningen er det en uordnet trekning.
Hvis man tar ut k prøver fra totalantallet merkete elementer n, uten tilbakelegging, gir dette følgende antall uordnete kombinasjoner (permutasjoner):
\(\displaystyle\frac {n!}{k!(n-k)!} = \binom{n}{k}\)
Antall kombinasjoner hvis man tar ut k prøver fra n merkete elementer, uten tilbakelegging, gir dette følgende antall ordnete kombinasjoner:
\(\displaystyle\frac {n!}{(n-k)!} = n(n-1)(n-2) \cdot \cdot(n-k+1)\)
Vi putter tre klinkekuler med fargene rød (R) og grønn (G) og blå (B) i en urne. Antall muligheter for å trekke ut to av dem hvor rekkefølgen har betydning gir 3!=3∙2∙1=6 muligheter: GR,RG,BR,RB,BG,GB. Hvis ikke rekkefølgen er avgjørende er det 3 kombinasjoner: RG, RB, GB.
Spillet Lotto går ut på å trekke ut 7 riktige tall (ordnet i stigende rekkefølge) blant tallene 1-34. Antall mulige Lottorekker er:
\(\displaystyle\binom{34}{7}= 5379616\)
I Lotto legges ikke tallene som er trukket ut tilbake, og rekkefølgen på tallene spiller ingen rolle, altså et uordnet utvalg uten tilbakelegging.
Sannsynligheten for 7 rette i Lotto er:\(\displaystyle\frac{1}{\binom{34}{7}}=1.858869 \cdot 10^{-7}\)
I Viking-lotto skal man trekke ut 6 riktige tall fra tallene 1-48. Dette gir følgende muligheter:
\(\displaystyle\binom{48}{6}= 12271512\)
Sannsynligheten for å vinne i Viking-Lotto
\(\displaystyle\frac{1}{\binom{48}{6}}=8.148955 \cdot 10^{-8}\)
I Bridge får hver spiller utdelt 13 kort. Antall bridgehender vil være antall undermengder med 13 objekter som kan bli delt ut av 52. Problemet kan løses med kombinatorikk.
\(\displaystyle \binom {52}{13}= \frac{52!}{13!\cdot (52-13)!}= 635013559600\)
Hva er sannsynligheten for å skrive hele alfabetet fra A til Å ved å trykke tilfeldig på et tastatur med bokstaver ? Det er 29 bokstaver i alfabetet. Sannsynligheten for å skrive en A er 1/29. Sannsynligheten for AB er 1/29∙1/29. Sannsynligheten for ABC blir 1/29∙1/29∙1/29 osv. Sannsynligheten for å skrive hele alfabetet a-Å blir ca. 3.9∙10-43, altså ekstremt lite sannsynlig.
Å kaste to spillterninger, hver har 6 sider med prikker eller øyne fra 1-6 gir 36= 62 mulige utfall. Dette er eksempel på ordnet repetert utvalg med tilbakelegging.
Kasting av tre terninger gir 216=63 mulige utfall. De tre terningene gir 3 valg, hver med 6 muligheter. De tre valgene er uavhengige av hverandre. Legg merke til at summen av øynene på motsatt side av terningen alltid er 7.
Hvor mange måter det er mulig å dele ut 5 kort fra en kortstokk med 52 kort er et annet eksempel: Det er 52 muligheter når første kort trekkes, 51 muligheter når andre kort trekkes, 50 muligheter når tredje kort trekkes osv. dvs. følgende muligheter:
\(52\cdot 51 \cdot50\cdot 49\cdot 48= 311875200\)
Hvis vi sier det er n1 muligheter for første valg, n2 muligheter for andre, n3 muligheter for tredje osv. blir det totale antall muligheter n1∙n2∙n3∙…
\(n_1 \cdot n_ 2\cdot n_3 \cdot n_4 \cdots\)
Generelt hvis man trekker x ganger og det er n muligheter å velge mellom blir antall permutasjoner lik:
\(\displaystyle n^x\)
Vi har det mer generelle problem å telle antall distinkte delmengder k som kan dannes fra en mengde med n elementer. Vi kan kalle dette tallet f(n,k) lik binomialkoeffisienten:
\(\displaystyle f(n, k) = \binom{n}{k}\)
\(\displaystyle\frac{n!}{k!(n-k)!} = \binom{n}{k}\)
Når vi skal vudere hvor mange muligheter det er å ta ut et bestemt antall individer eller hendelser fra en prøve som er representativ for populasjonen, er det avgjørende om samme individ eller hendelse kan tas ut flere ganger (med tilbakelegging) eller ikke (uten tilbakelegging). Vi kan tenke oss en urne med kuler som er nummerert i rekkefølge. Hvis vi trekker ut en kule, noterer nummer og egenskaper ved kulen, og legger den tilbake blir dette trekning med tilbakelegging. Legger vi den ikke tilbake blir det trekning uten tilbakelegging.
Er rekkefølgen av tallene på kulene avgjørende er det en ordnet trekning. Er rekkefølgen ikke avgjørende i trekningen er det en uordnet trekning.
Hvis man tar ut k prøver fra totalantallet merkete elementer n, uten tilbakelegging, gir dette følgende antall uordnete kombinasjoner (permutasjoner):
\(\displaystyle\frac{n!}{k!(n-k)!} = \binom{n}{k}\)
Antall kombinasjoner hvis man tar ut k prøver fra n merkete elementer, uten tilbakelegging, gir dette følgende antall ordnete kombinasjoner:
\(\displaystyle\frac{n!}{(n-k)!} = n(n-1)(n-2)\cdot \dots \cdot (n-k+ 1)\)
Vi putter tre klinkekuler med fargene rød (R) og grønn (G) og blå (B) i en urne. Antall muligheter for å trekke ut to av dem hvor rekkefølgen har betydning gir 3!=3∙2∙1=6 muligheter:
GR,RG,BR,RB,BG,GB. Hvis ikke rekkefølgen er avgjørende er det 3 kombinasjoner: RG, RB, GB.
Pólyas teorem
Pólyas teorem , kaltRedfield–Pólyas teorem innen kombinatorikk. generalisering av Burnside's lemma utviklet av den
Ungarsk-amerikanske matematikeren George Pólyas (1887 - 1985) i 11927 av den amerikanske matematikeren John Howard Redfield i(1879-1944). Mange problemstillinger innen matematikk omhandler telling For eksempel m objekter {1, 2, 3,..., m}1med k forskjellige farge f r{f1, f2 , f3,..., fk}. Pólyas opptellingsteorem teller hvor mange fargemønstre er det mulig å lage.
George Pólyas utga flere bøker om problemløsing bl.a. How to Solve It (1945).
Litteratur
Wikipedia