Binomialkoeffisient

Fra Wikipedia, den frie encyklopedi

Språk: Denne artikkelen trenger språkvask og korrektur for å oppnå en høyere språklig standard.

I statistikk og matematikk, spesielt innen kombinatorikk, er Binomialkoeffisienten av et naturlig tall n og et heltall k definert som det naturlige tallet

${n \choose k} = \frac{n!}{k!(n-k)!} \quad \mbox{hvis } n\geq k\geq 0 \qquad \mbox{(1)}$

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

der m! betegner fakultetet av m. 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), _nC_k eller $C^{k}_{n}$ (C står for det engelske ordet combination) og leses "n velg 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).

Innhold

1 Derivasjon fra binomutvidelse
2 Pascals trekant
3 Kombinatorikk og statistikk
4 Formeler som inneholder binomialkoeffisienter
5 Divisorer til binomialkoeffisienter
6 Grenser for binomialkoeffisienter
7 Generalisering til reele og komplekse argumenter
8 Generalisering til q-serie
9 Se også
10 Referenser

[rediger] Derivasjon 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 + 2 x y + y 2$ . Igjen oppstår ekstremene $x 3$ og $y 3$ på et unikt vis. Men leddet $x 2 y$ er enten 2xy ganget med x eller $x 2$ ganget med y, som gir koeffisienten 3; likeså oppstår $x y 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 2 y 2$ er begge $x y 2$ ganget med x og $x 2 y$ ganget med y, slik at leddets koeffisienten blir 3+3. Dette er opprinelsen 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 〈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 2 y 2$ .

(x +¹ y)(x +² y)(x +³ y)(x +⁴ 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 $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.

[rediger] 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 utifra 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.

[rediger] 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 $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 $C(n, k).$
Det finnes $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 $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.

[rediger] Formeler som inneholder binomialkoeffisienter

Følgende formeler 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)ⁿ 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).

[rediger] 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).

[rediger] Grenser 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$

[rediger] Generalisering til reele og komplekse argumenter

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 fast k, er uttrykket $f(z)={z\choose k}$ et polynom i z av grad k grad med rasjonale koeffisienter.