Binomialkoefficient

Inom matematiken definieras binomialkoefficienten $\{n\; \backslash choose\; k\}$ kombinatoriskt som det naturliga taletet n och heltal k definierad 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\; \backslash choose\; k\}\; =\; \backslash frac\{n!\}\{k!(n-k)!\}\; =\; \backslash frac\; \{n(n-1)\backslash cdots(n-k+1)\}\{k!\}$ för $n\; \backslash ge\; k\; \backslash ge\; 0$

där $m!$ är fakultetenen av $m$ och

$\{n\; \backslash choose\; k\}\; =\; 0$ för 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änare algebraisk definition, där man för varje reellt tal a och varje naturligt tal k sätter

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

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

Två exempel:

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

och (enligt Newtons utvidgade definition)

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

Notationen $\{n\; \backslash 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\; =\; \backslash sum\_\{k=0\}^\{n\}\; \{n\; \backslash 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\; \backslash choose\; k\}$ ofta skrivs C(n, k), _nC_k eller $C^\{k\}\_\{n\}$, och är uttrycket för antalet sätt man kan skapa en delmängd med k element ur en mängd med n element.

Likheter

Binomialkoefficienterna uppfyller följande likheter

$\{n\; \backslash choose\; n-k\}=\{n\; \backslash choose\; k\}$

Vilket lätt kan visas:

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

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

$\backslash sum\_\{k=0\}^\{n\}\; \{n\backslash choose\; k\}\; =\; 2^n;$

Genom att derivera under summatecknet fås även

$\backslash sum\_\{k=1\}^\{n\}\; k\; \{n\backslash choose\; k\}\; =\; n\; 2^\{n-1\}\; \backslash qquad\; (6)$

Olikheter

Binomialkoefficienterna begränsas av följande olikheter:

• $\backslash mathrm\{C\}(n,\; k)\; \backslash le\; \backslash frac\{n^k\}\{k!\}$

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

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

Specialfall

Tal på formen

$\{2n\; \backslash choose\; n\}$

kallas centrala binomialkoefficienter.

Se även

• Pascals triangel