Binomialkoefficient

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Inom matematiken definieras binomialkoefficienten  {n \choose k} kombinatoriskt för det naturliga talet n och heltalet k som antalet oordnade urval av k olika element ur en mängd med n olika element, det vill säga antalet k-delmängder av en n-mängd. Det kan visas att detta är ekvivalent med att

 {n \choose k} = \frac{n!}{k!(n-k)!} = \frac {n(n-1)\cdots(n-k+1)}{k!} för n \ge k \ge 0

där m! är fakulteten av m och

 {n \choose k} = 0 för k < 0 eller k > n.

Den sista likheten beror på att det inte kan väljas ut ett negativt antal element ur en n-mängd, och inte heller fler än n element.

Denna algebraiska framställning generaliserades av Isaac Newton till en allmänare algebraisk definition, där det för varje reellt tal a och varje naturligt tal k sätts

 {a \choose k} = \frac {a(a-1)\cdots(a-k+1)}{k!}.

Senare har denna definition utvidgats, genom att tillåta a att vara ett godtyckligt komplext tal.

Två exempel:

 {8 \choose 5} = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \cdot (3 \cdot 2 \cdot 1)}= \frac{8 \cdot 7 \cdot 6 }{3 \cdot 2} = 56

Annorlunda uttryckt: antalet möjligheter att välja 5 ur 8 (8*7*6*5*4) dividerat med antalet permutationer av 5 (5*4*3*2*1) ger oss antalet sätt vi kan välja 5 ur 8, utan att ta hänsyn till varje enskild permutation.

Enligt Newtons utvidgade definition

 {-1{,}5 \choose 3} = \frac {(-1{,}5)(-2{,}5)(-3{,}5)} {1\cdot2\cdot3} = \frac{-35}{16} = -2{,}1875 .

Notationen {n \choose k} skall ha introducerats av Albert von Ettinghausen 1826 [källa behövs], fast själva koefficienterna hade använts redan långt tidigare (se Pascals triangel).

Binomialkoefficienterna är koefficienterna i utvecklingen av potenser av binomet x + y:

 (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k}.

Denna utveckling är generaliserad genom binomialsatsen, vilken tillåter att exponenten n är negativ eller till och med komplex.

Binomialkoefficeinterna är viktiga inom kombinatoriken, där {n \choose k} ofta skrivs C(n, k), nCk eller C^{k}_{n}, och är uttrycket för antalet sätt som det kan skapas en delmängd med k element ur en mängd med n element.

Innehåll

Likheter

Binomialkoefficienterna uppfyller följande likheter

{n \choose n-k}={n \choose k}

Vilket lätt kan visas:

{n \choose n-k}=\frac{n!}{(n-k)!(n-(n-k))!}=\frac{n!}{(n-k)!k!}={n \choose k}

Med insättning av x=y=1 i binomialsatsen fås

 \sum_{k=0}^{n} {n\choose k} = 2^n;

Genom att derivera under summatecknet fås även

 \sum_{k=1}^{n} k {n\choose k} = n 2^{n-1} \qquad (6)

Olikheter

Binomialkoefficienterna begränsas av följande olikheter:

  •  \mathrm{C}(n, k)  \le \frac{n^k}{k!}
  •  \mathrm{C}(n, k)  \le \left(\frac{n\cdot e}{k}\right)^k
  •  \mathrm{C}(n, k)  \ge \left(\frac{n}{k}\right)^k.

Specialfall

Tal på formen

{2n \choose n}

kallas centrala binomialkoefficienter.

Se även

Personliga verktyg