Binomialkoeffisient

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Binomialkoeffisienten er en grunnleggende matematisk funksjon i det matematiske delområdet kombinatorikk. Den angir hvor mange forskjellige kombinasjone 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 megde med n elementer.

For eksempel er  {34 \choose 7} antall mulige forskjellige trekninger i Lotto.

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

 {n \choose k} = 0 \quad \mbox{hvis } k<0 \mbox{ eller } k>n

der n! betegner fakultetet av n. Ifølge Nicholas J. Higham, ble notasjonen

 {n \choose k}

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^{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. \qquad (2)

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[rediger | rediger kilde]

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 2xy 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 nk 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 〈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^2y^2.

(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 (nk)! permutasjoner, og de k faktorene av y har k! permutasjoner. Derfor er n!/(nk)!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[rediger | rediger kilde]

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[rediger | rediger kilde]

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 nk 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 parantesuttrykk.

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

Formler som inneholder binomialkoeffisienter[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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[rediger | rediger kilde]

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

Se også[rediger | rediger kilde]

Referanser[rediger | rediger kilde]

Denne artikkelen bruker materiale fra følgende PlanetMath artikler, som er lisensiert under GFDL: