ï»ż

 

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)}

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 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

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 x2; likesÄ for y, slik at vi fÄr leddet y2. 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 = x2 + 2xy + y2. Igjen oppstÄr ekstremene x3 og y3 pÄ et unikt vis. Men leddet x2y er enten 2xy ganget med x eller x2 ganget med y, som gir koeffisienten 3; likesÄ oppstÄr xy2 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 x4 eller y4), da oppstÄr leddet pÄ to mÄter, fra tilstÞtende koeffisienter med sammenlagt grad 3. For eksempel x2y2 er begge xy2 ganget med x og x2y 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 xn − kyk 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 xn − kyk. 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 x2y2.

(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 xn − kyk.

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 = (e1,...,em), kjent som et multi-indeks. Leddene i utvidelsen av (x1 + ... + xm)n har formen

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

hvor | E | = e1 + ... + em = 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)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).

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 pr er delelig med C(n, k), da er r likt antallet naturlige tall j slik at brĂžkdelen av k / pj er stĂžrre enn brĂžkdelen av n / pj. 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.

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 binom serie 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.

rediger Generalisering til q-serie

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

rediger Se ogsÄ

rediger Referenser

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.