Binomialkoeffisient

Binomialkoeffisienten er en grunnleggende matematisk funksjon i det matematiske delområdet kombinatorikk. Den angir hvor mange forskjellige kombinasjoner en kan velge  objekter fra en mengde av  ulike objekter (uten tilbakelegging, uavhengig av rekkefølgen). Sagt på en annen måte angir binomialkoeffisienten antall delmengder med  elementer i en mengde med  elementer.

Binomialkoeffisienten av et naturlig tall n og et heltall k er definert som det naturlige tallet

og som er null når k < 0 eller k > n. Her betegner n! fakultetet av n. Ifølge Nicholas J. Higham, ble denne notasjonen introdusert av Albert von Ettinghausen i 1826, selv om disse tallene var kjent i århundrer før dette; se Pascals trekant. 

Binomialkoeffisienten av n og k blir også skrevet som C(n, k), nCk eller  (C står for det engelske ordet combination) og leses «n over k». For å spare plass bruker vi den første av disse tre notasjonene.

For eksempel kan binomialkoeffisienten brukes til å beregne hvor mange mulige tallkombinasjoner som finnes i Lotto:

Hvilket igjen betyr at sannsynligheten for å få sju rette i Lotto på en gitt rekke er:

Binomialkoeffisientene er koeffisienter i utvidelsen av binomet  (derav navnet):

Dette generaliseres ved binomialformelen, som tillater eksponenten n å være et komplekst tall, (spesielt tillater dette n å være ethvert reelt tall, ikke nødvendigvis bare positive heltall).

 Utledning fra binomutvidelse 

Når eksponenten er 1, blir  til . Når eksponenten er 2, blir  til , som former ledd som følger. Det første leddet får vi ved å gange x fra begge faktorene, slik at vi får ; likeså for y, slik at vi får leddet . Men xy leddet kan formes av x fra den første og y fra den andre faktoren, eller y fra den første og x fra den andre faktoren; derfor får leddet koeffisienten 2.
Når eksponenten er 3, reduseres  til , hvor vi allerede vet at . Igjen oppstår ekstremene  og  på et unikt vis. Men leddet  er enten 2xy ganget med x eller  ganget med y, som gir koeffisienten 3; likeså oppstår  på to måter, ved å summere koeffisientene 1 og 2 får vi 3.

Dette foreslår en induksjon. Slik at for eksponenten 4, har hvert ledd sammenlagt grad (sum av eksponentene) på 4, med 4-k faktorer av x og k faktorer av y. Hvis k ikke er 0 eller 1 (leddene  eller ), da oppstår leddet på to måter, fra tilstøtende koeffisienter med sammenlagt grad 3. For eksempel  er begge  ganget med x og  ganget med y, slik at leddets koeffisienten blir 3+3. Dette er opprinnelsen til Pascals trekant, som er diskutert nedenfor.

Sett fra et annet perspektiv, for å forme  fra n faktorer av , må vi velge y fra k av faktorene og x fra resten. Vi teller mulighetene ved å betrakte de n! permutasjonene av faktorene. Hver permutasjon fremstilles som en uordnet liste med tall fra 1 til n. Vi velger en x fra de n−k første faktorene, og en y fra de resterende k faktorene; på denne måten vil hver permutasjon bidra til leddet . For eksempel, listen 〈4,1,2,3〉 velger x fra faktorene 4 og 1, og y velger faktorer fra 2 og 3, som en måte å forme leddet .

 (x  +1 y)(x  +2 y)(x  +3 y)(x  +4 y)

Men den distinkte listen 〈1,4,3,2〉 gjør akkurat det samme utvalget; formelen for binomialkoeffisienten må fjerne denne overflødigheten. De n-k faktorene av x har (n−k)! permutasjoner, og de k faktorene av y har k! permutasjoner. Derfor er n!/(n−k)!k! antall virkelig distinkte måter å forme leddet .

Diskusjonen kan videreføres til tilfellet hvor hver faktor er en sum av flere variabler, som naturligvis leder til definisjonen av en multinomialkoeffisient. En gunstig notasjon bruker en liste av variabler , med eksponentene gitt i en annen liste, , kjent som et multi-indeks. Leddene i utvidelsen av  har formen

hvor , og koeffisienten til et slikt ledd er multinomialkoeffisienten

Den enkle binomialkoeffisienten er tilfellet der m=2.

 Pascals trekant 

Pascals regel er det viktige gjentakelsesforholdet 

som følger direkte fra definisjonen. Dette gjentakelsesforholdet  kan brukes til å bevise, ved matematisk induksjon, at C(n, k) er et naturlig tall for alle n og k, et faktum som ikke er umiddelbart tydelig ut ifra definisjonen.

Den gir også opphav til pascals trekant:
 row 0                     1
 row 1                   1   1
 row 2                 1   2   1
 row 3               1   3   3   1
 row 4             1   4   6   4   1
 row 5           1   5   10  10   5   1
 row 6         1   6   15  20  15   6   1
 row 7       1   7   21  35  35   21  7   1
 row 8     1   8   28  56  70  56   28  8   1

rad nummer n inneholder tallene C(n, k) for k = 0,...,n. Den konstrueres ved å begynne med enere på utsiden og så legge sammen nabotall og skrive summen rett under. Denne metoden gjør det mulig å raskt regne ut binomial koeffisienter uten å måtte bruke brøk eller multiplikasjon. For eksempel, ved å se på den femte raden i trekanten, kan en straks lese av at
.
Differansene mellom elementer på andre diagonaler er elementene på forrige diagonal – slik som følger av gjentakelsesforholdet  (3) ovenfor.

I Precious Mirror of the Four Elements (1303), nevner Zhu Shijie trekanten som en eldgammel metode for å løse binomialkoeffisienter, noe som indikerer at metoden var kjent for kinesiske matematikere fem århundrer før Pascal.

 Kombinatorikk og statistikk 

Binomialkoeffisienter er av stor betydning i kombinatorikk, fordi de gir ferdige formler for visse hyppige telleproblemer:
 Alle mengder med n elementer har  forskjellige delmengder som har k elementer hver (disse kalles k-kombinasjoner).
 Antallet strenger av lengde n som inneholder k ett-tall og n−k null-tall er 
 Det finnes  strenger som består av k ett-tall og n null-tall slik at ingen ett-tall er tilstøtende.
 Antallet sekvenser som består av n naturlige tall som har summer lik k er ; dette er også antallet måter å velge k elementer ut av en mengde med n hvis tilbakelegging er tillat.
 Catalantallene har en enkel formulering som involverer binomialkoeffisisnter; de kan brukes til å telle diverse strukturer, slik som trær og parentesuttrykk.

Binomialkoeffisienter forekommer også i formelen for binomisk distribusjon i statistikk og i formelen for en Bézier kurve.

 Formler som inneholder binomialkoeffisienter 

Følgende formler kan være nyttige:

Dette utledes fra (2) ved at , og dette viser seg i den numeriske "symmetrien" i Pascals trekant.

Fra (2) ved å bruke at x = y = 1. Dette er det samme som å si at summen av elementene av en rad i Pascals trekant alltid tilsvarer to opphøyd i et heltall.

Fra (2), etter å ha derivert og satt inn x = y = 1.

Siden C(n, k) er definert som null hvis k > n, er summen endelig. Ved å utvide (1+x)m (1+x)n-m = (1+x)n med (2). Likning (7a) generaliserer likning (3). Likning (7a) er Vandermonde's konvolusjonsformel (etter Alexandre-Théophile Vandermonde) og er essensielt en form for Chu-Vandermonde identiteten. Den kan vises å gjelde for tilfeldige, komplekse  og .

Likning (7a) gjelder for alle verdier av m, mens likning (7b) gjelder for alle verdier av j.

Fra (7) ved å bruke m = k = n og (4).

Her betegner F(n + 1) Fibonacci-tallene. Denne formelen om diagonalene i Pascals trekant kan bevises med induksjon ved å bruke (3).



Dette kan bevises ved induksjon av n ved å bruke (3).

 Divisorer til binomialkoeffisienter 

Primtallsdivisorer til C(n, k) kan tolkes som følger: Hvis p er et primtall og r er den høyeste eksponenten slik at slik at  er delelig med C(n, k), da er r likt antallet naturlige tall j slik at brøkdelen av  er større enn brøkdelen av . Særskilt er C(n, k) alltid delelig med n/gcd(n, k).

 Ulikheter for binomialkoeffisienter 

Følgende grenser for C(n, k) gjelder:




 Generalisering til komplekse verdier 

Binomialkoeffisienten  kan defineres for alle komplekse tall z og alle naturlige tall k som følger:

Denne generaliseringen er kjent som den generelle binomialkoeffisienten og er brukt i utredningen av binomialformelen og oppfyller egenskapene (3) og (7).

For en konstant k, er uttrykket  et polynom av k'te grad med rasjonale koeffisienter.

f(z) er det unike polynomet av grad k som oppfyller
f(0)=f(1)=...=f(k-1)=0
og
f(k)=1.

Ethvert polynom p(z) av grad d kan skrives på formen

Dette er viktig i teorien om differenslikninger og kan bli sett på som en diskret analog til Taylors teorem.

Newtons binomserie får den enkle formen
.

Det er ikke vanskelig å vise at rekkens konvergensradius er 1.

 Generalisering til q-serie 

Binomialkoeffisienten har en q-analog generalisering kjent som Gauss-binomet.

 Se også 
 Fakultet (matematikk)
 Liste over fakultet- og binomemner

 Referanser 
Denne artikkelen bruker materiale fra følgende PlanetMath artikler, som er lisensiert under GFDL:
Binomial Coefficient
Bounds for binomial coefficients 
Proof that C(n,k) is an integer
Generalized binomial coefficients

Kategori:Kombinatorikk
Kategori:Fakultet og binomialkoeffisientsemner
Kategori:Heltallsfølger
Kategori:Nummertriangler