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

(\binom{n}{k}) = \frac{n!}{k! (n - k)!} hvis n \geq k \geq 0 (1)

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), _nC_k eller $C_{n}^{k}$ (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:

C (34, 7) = \frac{34!}{7! (34 - 7)!} = \frac{34!}{7! 27!} = \frac{34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29 \cdot 28}{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:

\frac{1}{5379616} \approx 1, 86 \cdot 1 0^{- 7}

Binomialkoeffisientene er koeffisienter i utvidelsen av binomet $(x + y)^{n}$ (derav navnet):

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{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} + 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 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 ⟨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 $𝐱 = (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

𝐱^{E} = x_{1}^{e_{1}} x_{2}^{e_{2}} \dots 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}! \dots e_{m}!} .

Den enkle binomialkoeffisienten er tilfellet der m=2.

Pascals trekant

Pascals regel er det viktige gjentakelsesforholdet

C (n, k) + C (n, k + 1) = C (n + 1, k + 1), (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} = 𝟏 x^{5} + 𝟓 x^{4} y + 𝟏 𝟎 x^{3} y^{2} + 𝟏 𝟎 x^{2} y^{3} + 𝟓 x y^{4} + 𝟏 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 $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 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:

C (n, k) = C (n, n - k) (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} C (n, k) = 2^{n} (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 C (n, k) = n 2^{n - 1} (6)

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

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

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} C (m, j) C (n - m, k - j) = C (n + 1, k + 1) (7 b)

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

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

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

\sum_{k = 0}^{n} C (n - k, k) = F (n + 1) (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} C (j, k) = C (n + 1, k + 1) (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:

$(\binom{n}{k}) \leq \frac{n^{k}}{k!}$
$(\binom{n}{k}) \leq {(\frac{n \cdot e}{k})}^{k}$
$(\binom{n}{k}) \geq {(\frac{n}{k})}^{k}$

Generalisering til komplekse verdier

Binomialkoeffisienten $(\binom{z}{k})$ kan defineres for alle komplekse tall z og alle naturlige tall k som følger:

(\binom{z}{k}) = \prod_{n = 1}^{k} \frac{z - k + n}{n} = \frac{z (z - 1) (z - 2) \dots (z - k + 1)}{k!} (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) = (\binom{z}{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} (\binom{z}{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)^{α} = \sum_{r = 0}^{\infty} (\binom{α}{r}) z^{r} = 1 + (\binom{α}{1}) z + (\binom{α}{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å

Referanser

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

Mal:Autoritetsdata

Binomialkoeffisient

Innhold

Utledning fra binomutvidelse

Pascals trekant

Kombinatorikk og statistikk

Formler som inneholder binomialkoeffisienter

Divisorer til binomialkoeffisienter

Ulikheter for binomialkoeffisienter

Generalisering til komplekse verdier

Generalisering til q-serie

Se også

Referanser

Navigasjonsmeny

Binomialkoeffisient

Utledning fra binomutvidelse

Pascals trekant

Kombinatorikk og statistikk

Formler som inneholder binomialkoeffisienter

Divisorer til binomialkoeffisienter

Ulikheter for binomialkoeffisienter

Generalisering til komplekse verdier

Generalisering til q-serie

Se også

Referanser

Navigasjonsmeny

Søk