Binomialkoeffisient

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

Binomialkoeffisienten av et naturlig tall *n* og et heltall *k* er definert som det naturlige tallet
: {n \choose k} = \frac{n!}{k!(n-k)!} \quad \mbox{hvis } n\geq k\geq 0 \qquad \mbox{(1)} 

og som er null når *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*), *n*C*k* eller C^{k}_{n} (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:
: \mathrm{C}(34, 7) = \frac{34!}{7!(34-7)!} = \frac{34!}{7!27!} = {34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29 \cdot 28 \over 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 5379616

Hvilket igjen betyr at sannsynligheten for å få sju rette i Lotto på en gitt rekke er:
: {1 \over 5379616} \approx {1,86 \cdot 10^{-7}}

Binomialkoeffisientene er koeffisienter i utvidelsen av binomet (x + y)^n (derav navnet):
: (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k. 

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 (x+y)^1 til x+y. Når eksponenten er 2, blir (x+y)^2 til (x+y)(x+y), som former ledd som følger. Det første leddet får vi ved å gange *x* fra begge faktorene, slik at vi får x^2; likeså for *y*, slik at vi får leddet y^2. 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 (x+y)^3 til (x+y)^2(x+y), hvor vi allerede vet at (x+y)^2 = x^2+2xy+y^2. Igjen oppstår ekstremene x^3 og y^3 på et unikt vis. Men leddet x^2y er enten 2*xy* ganget med *x* eller x^2 ganget med *y*, som gir koeffisienten 3; likeså oppstår xy^2 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 x^4 eller y^4), da oppstår leddet på to måter, fra tilstøtende koeffisienter med sammenlagt grad 3. For eksempel x^2y^2 er begge xy^2 ganget med *x* og x^2y 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 x^{n-k}y^{k} fra *n* faktorer av (x+y), 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 x^{n-k}y^k. For eksempel, listen &lang;4,1,2,3&rang; velger *x* fra faktorene 4 og 1, og *y* velger faktorer fra 2 og 3, som en måte å forme leddet x^2y^2.

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

Men den distinkte listen &lang;1,4,3,2&rang; 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 x^{n-k}y^k.

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 \mathbf x = (x_1,...,x_m), med eksponentene gitt i en annen liste, E=(e_1,...,e_m), kjent som et *multi-indeks*. Leddene i utvidelsen av (x_1+...+x_m)^n har formen

:{\mathbf x}^E = x_1^{e_1} x_2^{e_2} \cdots x_m^{e_m},

hvor |E|=e_1+...+e_m=n, og koeffisienten til et slikt ledd er multinomialkoeffisienten

:\frac{n!}{e_1! e_2! \cdots e_m!}.

Den enkle binomialkoeffisienten er tilfellet der *m*=2.

## Pascals trekant

Pascals regel er det viktige gjentakelsesforholdet 

: \mathrm{C}(n,k) +  \mathrm{C}(n,k+1) = C(n+1,k+1), \qquad (3) 

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
:(x + y)^5 = \mathbf{1}x^5 + \mathbf{5}x^4y + \mathbf{10}x^3y^2 + \mathbf{10}x^2y^3 + \mathbf{5}xy^4 + \mathbf{1}y^5.
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  \mathrm{C}(n, k) 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  \mathrm{C}(n, k).
* Det finnes  \mathrm{C}(n+1, k) 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  \mathrm{C}(n+k-1, k); 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:

: \mathrm{C}(n,k)= \mathrm{C}(n, n-k)\qquad\qquad(4)\,

Dette utledes fra (2) ved at (x + y)^n = (y + x)^n, og dette viser seg i den numeriske "symmetrien" i Pascals trekant.
: \sum_{k=0}^{n} \mathrm{C}(n,k) = 2^n \qquad (5) 

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.

: \sum_{k=1}^{n} k \mathrm{C}(n,k) = n 2^{n-1} \qquad (6) 

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

: \sum_{j} \mathrm{C}(m,j) \mathrm{C}(n-m,k-j) = \mathrm{C}(n,k) \qquad (7a) 

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 m og n.

: \sum_{m} \mathrm{C}(m,j) \mathrm{C}(n-m,k-j) = \mathrm{C}(n+1,k+1) \qquad (7b) 

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

: \sum_{k=0}^{n} \mathrm{C}(n,k)^2 = \mathrm{C}(2n,n) \qquad (8)

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

: \sum_{k=0}^{n} \mathrm{C}(n-k,k) = \mathrm{F}(n+1) \qquad (9) 

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

: \sum_{j=k}^{n} \mathrm{C}(j,k) = \mathrm{C}(n+1,k+1) \qquad (10)  

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 p^r er delelig med C(*n*, *k*), da er *r* likt antallet naturlige tall *j* slik at brøkdelen av k/p^j er større enn brøkdelen av n/p^j. Særskilt er C(*n*, *k*) alltid delelig med *n*/gcd(*n*, *k*).

## Ulikheter for binomialkoeffisienter

Følgende grenser for C(*n*, *k*) gjelder:
*  {n\choose k} \le \frac{n^k}{k!} 
*  {n\choose k} \le \left(\frac{n\cdot e}{k}\right)^k 
* {n\choose k} \ge \left(\frac{n}{k}\right)^k

## Generalisering til komplekse verdier

Binomialkoeffisienten {z\choose k} kan defineres for alle komplekse tall *z* og alle naturlige tall *k* som følger:
:{z\choose k} = \prod_{n=1}^{k}{z-k+n\over n}= \frac{z(z-1)(z-2)\cdots (z-k+1)}{k!} \qquad (11) 

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 f(z)={z\choose k} 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
: p(z) = \sum_{k=0}^{d} a_k {z\choose k} 
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
: (1+z)^{\alpha} = \sum_{r = 0}^{\infty}{\alpha\choose r}z^r = 1+{\alpha\choose1}z+{\alpha\choose 2}z^2+...

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 :*
*Binomial Coefficient
*Bounds for binomial coefficients 
*Proof that C(n,k) is an integer
*Generalized binomial coefficients