Binomialkoefficient

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. Det går att visa att detta är ekvivalent med

Binomialkoefficienterna kan arrangeras som Pascals triangel

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

där '!' betecknar fakultet och

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

Den sista likheten beror på att det inte går att 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 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 a tillåts 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

Beteckningen ${n \choose k}$ lär ha introducerats av Andreas von Ettinghausen 1826, 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), _nC_k eller $C_{n}^{k}$.

Exempel

För små naturliga tal n och k är det 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å element från {a, b, c, d} om ingen hänsyn tas till i vilken ordning de väljs, är {a, b}, {b, c}, {c, d}, {d, a}, {a, c}, samt {b, 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 att välja två av bokstäverna a, b, c och d som ordnade par är 4·3 = 12, eftersom den första bokstaven kan väljas på fyra sätt och den andra bokstaven på tre sätt (bland de bokstäver som inte redan valts). Då har emellertid varje oordnat urval räknats 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\cdot 2\cdot 3}}={\frac {-35}{16}}=-2{,}1875$.

Likheter

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 2ⁿ 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}=n2^{n-1}$.

Olikheter

Binomialkoefficienterna begränsas av olikheterna

• $\mathrm {C} (n,k)\leq {\frac {n^{k}}{k!}}$

• $\mathrm {C} (n,k)\leq \left({\frac {n\cdot e}{k}}\right)^{k}$

• $\mathrm {C} (n,k)\geq \left({\frac {n}{k}}\right)^{k}.$

Specialfall

Tal på formen

${2n \choose n}$

kallas centrala binomialkoefficienter.

Se även

• Fibonomialkoefficient

Referenser