Binomialkoefficient

Från Wikipedia
Hoppa till: navigering, sök

Inom matematiken definieras binomialkoefficienten eller binomialtalet  {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. Man kan visa 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 man inte kan välja 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ännare algebraisk definition, där man för varje reellt tal a och varje naturligt tal k sätter

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

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

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 den allmänna binomialsatsen, vilken tillåter att exponenten n är negativ eller till och med ett godtyckligt komplext tal.

Binomialkoefficeinterna är också viktiga inom bland annat kombinatoriken och sannolikhetsteorin.

Beteckningar[redigera | redigera wikitext]

Beteckningen {n \choose k} lär ha introducerats av Andreas von Ettinghausen 1826[1], men koefficienterna användes långt tidigare (se Pascals triangel).

Andra beteckningssätt förekommer ibland, där {n \choose k} skrivs C(n, k), nCk eller C^{k}_{n},

Exempel[redigera | redigera wikitext]

För små naturliga tal n och k är det rätt enkelt att använda den kombinatoriska definitionen direkt för att beräkna en binomialkoefficient:

 {4 \choose 2} = 6,

därför att de enda sätten att välja ut två av bokstäverna a, b, c och d på om man inte tar hänsyn till i vilken ordning man väljer dem, är a och b, samt b och c, samt c och d, samt d och a, samt a och c, samt slutligen b och d; totalt sex olika möjligheter. Det går också att resonera mer systematiskt, i stället för att bara räkna upp alla möjligheter: Antalet sätt man kan välja ut två av bokstäverna a, b, c och d ordnat på är 4·3 = 12, eftersom man kan välja den första bokstaven på fyra sätt, och sedan välja den andra bokstaven på tre sätt (bland de bokstäver man inte redan har valt). Då har man emellertid räknat varje oordnat urval dubbelt, eftersom exempelvis både valet "b först och c sedan" och valet "c först och b sedan" motsvarar det oordnade valet "b och c, utan hänsyn till ordningen". Alltså är  {4 \choose 2} = \frac{12}{2} = 6.

På liknande sätt är

 {8 \choose 5} = \frac{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \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,

eftersom detta är antalet möjligheter att välja 5 element ordnat ur 8 (8·7·6·5·4) dividerat med antalet sätt att ordna de fem elementen (5·4·3·2·1).

Enligt Newtons utvidgade definition är

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


Likheter[redigera | redigera wikitext]

Binomialkoefficienterna uppfyller bland annat följande likheter, som i allmänhet kan bevisas både medelst kombinatoriska resonemang och medelst algebraiska eller analytiska manipulationer.

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

vilket är en omedelbar följd av definitionen: Man kan plocka bort n-k element av n element på lika många sätt som man kan lämna kvar k av elementen. Alternativt använder man att

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

Den grundläggande likheten för Pascals triangel är att varje tal däri (utom den översta ettan) är summan av de två talen närmast ovanför; eller, med andra ord, att

  • {n+1 \choose k+1} = {n \choose k} + {n \choose k+1}, om n och k är naturliga tal.

Vänsterledet är antalet sätt att välja ut en (k+1)-delmängd (d. v. s. en delmängd med k+1 element) ur en (n+1)-mängd M. Låter man x vara ett specifikt element i M, så kan man se att det finns två slags (k+1)-delmängder: Dels {n \choose k} stycken, som innehåller x samt k element till, och dels {n \choose k+1} stycken som inte innehåller x, utan k+1 av de övriga n elementen. Det sammanlagda antalet element av de två slagen är alltså precis högerledet i likheten. Eftersom vänsterledet och högerledet således är två sätt att ange samma antal på, så är de lika.

Alternativt kan man (i det intressanta fallet, där k < n) använda likheten (m+1)! = m!·(m+1), som gäller för alla naturliga tal m, och det algebraiska uttrycket för binomialkoefficienter:

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

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

  •  \sum_{k=0}^{n} {n\choose k} = 2^n.

Alternativt kan man notera att en n-mängd har precis 2n delmängder, därför att man för varje element i mängden har två möjligheter: Antingen är elementet med i delmängden, eller så är det inte med.

Genom att derivera under summatecknet fås även

  •  \sum_{k=1}^{n} k {n\choose k} = n 2^{n-1}.

Olikheter[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Tal på formen

{2n \choose n}

kallas centrala binomialkoefficienter.

Se även[redigera | redigera wikitext]

Noter[redigera | redigera wikitext]

  1. ^ Higham, Nicholas J.. Handbook of writing for the mathematical sciences. SIAM. sid. 25. ISBN 0898714206 
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.