Binomický koeficient - Binomial coefficient

v matematika, binomické koeficienty jsou pozitivní celá čísla které se vyskytují jako koeficienty v binomická věta. Obvykle je binomický koeficient indexován dvojicí celých čísel n ≥ k ≥ 0 a je napsán ${displaystyle {binom {n} {k}}.}$ Je to koeficient X^k termín v polynomiální expanze z binomický Napájení (1 + X)ⁿ, a je to dáno vzorcem

${displaystyle {jin {n} {k}} = {frac {n!} {k! (n-k)!}}.}$

Například čtvrtá síla 1 + X je

${displaystyle {egin {aligned} (1 + x) ^ {4} & = {binom {4} {0}} x ^ {0} + {binom {4} {1}} x ^ {1} + {binom {4} {2}} x ^ {2} + {binom {4} {3}} x ^ {3} + {binom {4} {4}} x ^ {4} & = 1 + 4x + 6x ^ {2} + 4x ^ {3} + x ^ {4}, konec {zarovnáno}}}$

a binomický koeficient ${displaystyle {binom {4} {2}} = {frac {4!} {2! 2!}} = 6}$ je koeficient X² období.

Uspořádání čísel ${displaystyle {binom {n} {0}}, {binom {n} {1}}, ldots, {binom {n} {n}}}$ v po sobě jdoucích řádcích pro ${displaystyle n = 0,1,2, ldots}$ dává trojúhelníkové pole s názvem Pascalův trojúhelník, uspokojující relace opakování

${displaystyle {jin {n} {k}} = {jin {n-1} {k}} + {jin {n-1} {k-1}}.}$

Binomické koeficienty se vyskytují v mnoha oblastech matematiky, zejména v kombinatorika. Symbol ${displaystyle {binom {n} {k}}}$ se obvykle čte jako „n Vybrat k„protože existují ${displaystyle {binom {n} {k}}}$ způsoby, jak vybrat (neuspořádanou) podmnožinu k prvky z pevné sady n elementy. Například existují ${displaystyle {binom {4} {2}} = 6}$ způsoby, jak vybrat 2 prvky z ${displaystyle {1,2,3,4},}$ a to ${displaystyle {1,2} {ext {,}} {1,3} {ext {,}} {1,4} {ext {,}} {2,3} {ext {,}} {2,4 } {ext {,}}}$ a ${displaystyle {3,4}.}$

Binomické koeficienty lze zobecnit na ${displaystyle {binom {z} {k}}}$ pro jakékoli komplexní číslo z a celé číslo k ≥ 0a mnoho z jejich vlastností se nadále drží v této obecnější podobě.

Historie a notace

Andreas von Ettingshausen představil notaci ${displaystyle {binom {n} {k}}}$ v roce 1826,^[1] ačkoli čísla byla známa o staletí dříve (viz Pascalův trojúhelník ). Nejdříve známá podrobná diskuse o binomických koeficientech je v komentáři z desátého století, autor Halayudha, na starověku Sanskrt text, Pingala je Chandaḥśāstra. Asi v roce 1150 indický matematik Bhaskaracharya uvedl ve své knize výklad binomických koeficientů Līlāvatī.^[2]

Alternativní notace zahrnují C(n, k), _nC_k, ⁿC_k, C^k_n, Cⁿ_k, a C_n,k ve všech z nich C znamená kombinace nebo volby. Mnoho kalkulaček používá varianty C notace protože to mohou reprezentovat na jednořádkovém displeji. V této formě lze snadno porovnat binomické koeficienty k-permutace n, psáno jako P(n, k), atd.

Definice a interpretace

Pro přirozená čísla (zahrnuto včetně 0) n a k, binomický koeficient ${displaystyle {binom {n} {k}}}$ lze definovat jako součinitel z monomiální X^k v expanzi (1 + X)ⁿ. Stejný koeficient se také vyskytuje (pokud k ≤ n) v binomický vzorec

${displaystyle (x + y) ^ {n} = součet _ {k = 0} ^ {n} {jiné {n} {k}} x ^ {n-k} y ^ {k}}$

(∗)

(platí pro všechny prvky X, y a komutativní prsten ), který vysvětluje název „binomický koeficient“.

Další výskyt tohoto čísla je v kombinatorice, kde udává počet způsobů, bez ohledu na pořadí k objekty lze vybírat mezi n předměty; formálněji počet k-prvkové podmnožiny (nebo k-kombinace ) z n- sada prvků. Toto číslo lze považovat za stejné jako u první definice, nezávisle na kterémkoli z níže uvedených vzorců pro jeho výpočet: pokud je v každém z n faktory síly (1 + X)ⁿ jeden termín dočasně označí X s indexem i (běží od 1 do n), pak každá podskupina k indexy dává po expanzi příspěvek X^ka koeficient tohoto monomialu ve výsledku bude počet takových podmnožin. To ukazuje zejména to ${displaystyle {binom {n} {k}}}$ je přirozené číslo pro všechna přirozená čísla n a k. Existuje mnoho dalších kombinatorických interpretací binomických koeficientů (počítání problémů, na které je odpověď dána vyjádřením binomického koeficientu), například počet slov vytvořených z n bity (číslice 0 nebo 1), jejichž součet je k darováno ${displaystyle {binom {n} {k}}}$, zatímco počet způsobů psaní ${displaystyle k = a_ {1} + a_ {2} + cdots + a_ {n}}$ kde každý A_i je nezáporné celé číslo je dáno vztahem ${displaystyle {binom {n + k-1} {n-1}}}$. Většinu těchto interpretací lze snadno považovat za ekvivalent počítání k-kombinace.

Výpočet hodnoty binomických koeficientů

Existuje několik metod pro výpočet hodnoty ${displaystyle {binom {n} {k}}}$ bez skutečného rozšíření binomické síly nebo počítání k-kombinace.

Rekurzivní vzorec

Jedna metoda používá rekurzivní, čistě aditivní vzorec

${displaystyle {jin {n} {k}} = {jin {n-1} {k-1}} + {jin {n-1} {k}} quad {ext {pro všechna celá čísla}} n, k: 1leq kleq n-1,}$

s počátečními / hraničními hodnotami

${displaystyle {iný {n} {0}} = {iný {n} {n}} = 1quad {ext {pro všechna celá čísla}} ngeq 0,}$

Vzorec vyplývá z uvažování množiny {1, 2, 3, ..., n} a počítá se samostatně (a) k- seskupení prvků, které obsahují konkrétní prvek množiny, řekněme "i", v každé skupině (od"i„je již vybráno k vyplnění jednoho místa v každé skupině, stačí si vybrat k - 1 ze zbývajících n - 1) a (b) všechny k-skupiny, které neobsahují „i"; toto vyjmenovává vše možné k-kombinací n elementy. Vyplývá to také ze sledování příspěvků k X^k v (1 + X)ⁿ⁻¹(1 + X). Protože je nula Xⁿ⁺¹ nebo X⁻¹ v (1 + X)ⁿ, jeden by mohl rozšířit definici za výše uvedené hranice zahrnout ${displaystyle {binom {n} {k}}}$ = 0, když jeden k > n nebo k <0. Tento rekurzivní vzorec pak umožňuje konstrukci Pascalův trojúhelník, obklopen bílými mezerami, kde by byly nuly nebo triviální koeficienty.

Multiplikativní vzorec

Efektivnější metoda výpočtu jednotlivých binomických koeficientů je dána vzorcem

${displaystyle {jin {n} {k}} = {frac {n ^ {podtržení {k}}} {k!}} = {frac {n (n-1) (n-2) cdots (n- (k -1))} {k (k-1) (k-2) cdots 1}} = prod _ {i = 1} ^ {k} {frac {n + 1-i} {i}},}$

kde čitatel prvního zlomku ${displaystyle n ^ {podtržení {k}}}$ je vyjádřena jako a klesající faktoriální síla Tento vzorec je nejsnadněji pochopitelný pro kombinatorickou interpretaci binomických koeficientů. Čitatel udává počet způsobů, jak vybrat posloupnost k odlišné objekty, které si zachovávají pořadí výběru, ze sady n předměty. Jmenovatel počítá počet odlišných sekvencí, které definují totéž k-kombinace při ignorování objednávky.

Vzhledem k symetrii binomického koeficientu s ohledem na k a n − k, výpočet lze optimalizovat nastavením horní hranice produktu výše na menší z k a n − k.

Faktoriální vzorec

Nakonec, i když je výpočetně nevhodný, existuje kompaktní forma, často používaná v důkazech a odvozeninách, která opakovaně využívá známé faktoriál funkce:

${displaystyle {jin {n} {k}} = {frac {n!} {k!, (n-k)!}} quad {ext {for}} 0leq kleq n,}$

kde n! označuje faktoriál z n. Tento vzorec vyplývá z výše uvedeného multiplikativního vzorce vynásobením čitatele a jmenovatele číslem (n − k)!; v důsledku toho zahrnuje mnoho faktorů společných čitateli a jmenovateli. Pro explicitní výpočet je méně praktické (v případě, že k je malý a n je velký), pokud nebudou nejprve zrušeny společné faktory (zejména proto, že faktoriální hodnoty rostou velmi rychle). Vzorec vykazuje symetrii, která je méně patrná z multiplikativního vzorce (i když je z definic)

${displaystyle {jin {n} {k}} = {jin {n} {n-k}} quad {ext {for}} 0leq kleq n,}$

(1)

což vede k efektivnější multiplikativní výpočetní rutině. Za použití klesající faktoriální notace,

${displaystyle {jin {n} {k}} = {egin {cases} n ^ {podtržení {k}} / k! & {ext {if}} kleq {frac {n} {2}} n ^ {podtržení {nk}} / (nk)! & {ext {if}} k> {frac {n} {2}} end {cases}}.}$

Zobecnění a připojení k binomické řadě

Multiplikativní vzorec umožňuje rozšířit definici binomických koeficientů^[3] nahrazením n libovolným číslem α (negativní, skutečný, komplexní) nebo dokonce prvek libovolného komutativní prsten ve kterém jsou všechna kladná celá čísla invertovatelná:

${displaystyle {jiní {alpha} {k}} = {frac {alpha ^ {podtržení {k}}} {k!}} = {frac {alfa (alfa -1) (alfa -2) cdots (alpha -k + 1)} {k (k-1) (k-2) cdots 1}} quad {ext {for}} kin mathbb {N} {ext {and arbitrary}} alpha.}$

S touto definicí má člověk zobecnění binomického vzorce (s jednou z proměnných nastavenou na 1), což ospravedlňuje stále volání ${displaystyle {binom {alpha} {k}}}$ binomické koeficienty:

${displaystyle (1 + X) ^ {alpha} = součet _ {k = 0} ^ {infty} {alfa vyberte k} X ^ {k}.}$

(2)

Tento vzorec platí pro všechna komplexní čísla α a X s |X| <1. Lze jej také interpretovat jako identitu formální mocenské řady v X, kde ve skutečnosti může sloužit jako definice libovolných mocnin výkonové řady s konstantním koeficientem rovným 1; jde o to, že s touto definicí platí všechny identity, od kterých člověk očekává umocňování, zejména

${displaystyle (1 + X) ^ {alpha} (1 + X) ^ {eta} = (1 + X) ^ {alpha + eta} quad {ext {a}} quad ((1 + X) ^ {alpha} ) ^ {eta} = (1 + X) ^ {alfa eta}.}$

Li α je nezáporné celé číslo n, pak všechny termíny s k > n jsou nula a nekonečná řada se stává konečným součtem, čímž se získá binomický vzorec. Pro jiné hodnoty α, včetně záporných celých čísel a racionálních čísel, je řada opravdu nekonečná.

Pascalův trojúhelník

Pascalovo pravidlo je důležité relace opakování

${displaystyle {n zvolte k} + {n vyberte k + 1} = {n + 1 vyberte k + 1},}$

(3)

které lze použít k prokázání matematická indukce že ${displaystyle {binom {n} {k}}}$ je přirozené číslo pro celé číslo n ≥ 0 a celé číslo k, skutečnost, ze které není hned zřejmé formule 1). Nalevo a napravo od Pascalova trojúhelníku jsou všechny položky (zobrazené jako mezery) nulové.

Pascalovo pravidlo také dává vzniknout Pascalův trojúhelník:

0:									1
1:								1		1
2:							1		2		1
3:						1		3		3		1
4:					1		4		6		4		1
5:				1		5		10		10		5		1
6:			1		6		15		20		15		6		1
7:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

Číslo řádku n obsahuje čísla ${displaystyle {binom {n} {k}}}$ pro k = 0, ..., n. Je konstruováno tak, že nejprve umístíte 1 s do nejvzdálenějších pozic a poté vyplníte každou vnitřní pozici součtem dvou čísel přímo nad. Tato metoda umožňuje rychlý výpočet binomických koeficientů bez nutnosti zlomků nebo násobení. Například při pohledu na řádek číslo 5 trojúhelníku to lze rychle přečíst

${displaystyle (x + y) ^ {5} = {podtržení {1}} x ^ {5} + {podtržení {5}} x ^ {4} y + {podtržení {10}} x ^ {3} y ^ { 2} + {podtržení {10}} x ^ {2} y ^ {3} + {podtržení {5}} xy ^ {4} + {podtržení {1}} y ^ {5}.}$

Kombinatorika a statistika

Binomické koeficienty jsou důležité v kombinatorika, protože poskytují připravené vzorce pro určité časté problémy s počítáním:

• Existují ${displaystyle {binom {n} {k}}}$ způsoby, jak si vybrat k prvky ze sady n elementy. Vidět Kombinace.
• Existují ${displaystyle {binom {n + k-1} {k}}}$ způsoby, jak si vybrat k prvky ze sady n prvky, pokud je povoleno opakování. Vidět Multiset.
• Existují ${displaystyle {binom {n + k} {k}}}$ struny obsahující k ty a n nuly.
• Existují ${displaystyle {binom {n + 1} {k}}}$ řetězce skládající se z k ty a n nuly tak, že žádné dva nesousedí.^[4]
• The Katalánská čísla jsou ${displaystyle {frac {1} {n + 1}} {binom {2n} {n}}.}$
• The binomická distribuce v statistika je ${displaystyle {binom {n} {k}} p ^ {k} (1-p) ^ {n-k} !.}$

Binomické koeficienty jako polynomy

Pro jakékoli nezáporné celé číslo k, výraz ${displaystyle scriptstyle {jiné {t} {k}}}$ lze zjednodušit a definovat jako polynom vydělený k!:

${displaystyle {jin {t} {k}} = {frac {(t) _ {k}} {k!}} = {frac {(t) _ {k}} {(k) _ {k}}} = {frac {t (t-1) (t-2) cdots (t-k + 1)} {k (k-1) (k-2) cdots 2cdot 1}}}}$

toto představuje a polynomiální v t s Racionální koeficienty.

Jako takový jej lze vyhodnotit na jakémkoli reálném nebo komplexním čísle t definovat binomické koeficienty s takovými prvními argumenty. Tyto „zobecněné binomické koeficienty“ se objevují v Newtonova zobecněná binomická věta.

Pro každého k, polynom ${displaystyle {binom {t} {k}}}$ lze charakterizovat jako jedinečný stupeň k polynomiální p(t) uspokojující p(0) = p(1) = ... = p(k - 1) = 0 a p(k) = 1.

Jeho koeficienty jsou vyjádřitelné z hlediska Stirlingova čísla prvního druhu:

${displaystyle {jin {t} {k}} = součet _ {i = 0} ^ {k} s (k, i) {frac {t ^ {i}} {k!}}.}$

The derivát z ${displaystyle {binom {t} {k}}}$ lze vypočítat pomocí logaritmická diferenciace:

${displaystyle {frac {mathrm {d}} {mathrm {d} t}} {iný {t} {k}} = {jiný {t} {k}} součet _ {i = 0} ^ {k-1} {frac {1} {ti}}.}$

Binomické koeficienty jako základ pro prostor polynomů

Přes všechny pole z charakteristika 0 (tj. jakékoli pole, které obsahuje racionální čísla ), každý polynom p(t) stupně nanejvýš d je jednoznačně vyjádřitelný jako lineární kombinace ${displaystyle sum _ {k = 0} ^ {d} a_ {k} {jině {t} {k}}}$ binomických koeficientů. Koeficient A_k je kten rozdíl sekvence p(0), p(1), ..., p(k). Výslovně,^[5]

${displaystyle a_ {k} = součet _ {i = 0} ^ {k} (- 1) ^ {k-i} {jiné {k} {i}} p (i).}$

(4)

Celočíselné polynomy

Každý polynom ${displaystyle {binom {t} {k}}}$ je celočíselná hodnota: má celočíselnou hodnotu na všech celočíselných vstupech ${displaystyle t}$(Jedním ze způsobů, jak to dokázat, je indukce dne k, použitím Pascalova identita.) Proto je jakákoli celočíselná lineární kombinace polynomů s binomickým koeficientem také celočíselná. Naopak, (4) ukazuje, že jakýkoli celočíselný polynom je celočíselná lineární kombinace těchto polynomů s binomickým koeficientem. Obecněji pro jakýkoli podřetězec R charakteristického pole 0 K., polynom v K.[t] bere hodnoty v R ve všech celých číslech, právě když je to R-lineární kombinace polynomů s binomickým koeficientem.

Příklad

Celočíselný polynom 3t(3t + 1) / 2 lze přepsat jako

${displaystyle 9 {binom {t} {2}} + 6 {binom {t} {1}} + 0 {binom {t} {0}}.}$

Identity zahrnující binomické koeficienty

Faktoriální vzorec usnadňuje související blízké binomické koeficienty. Například pokud k je kladné celé číslo a n je tedy libovolný

${displaystyle {jiní {n} {k}} = {frac {n} {k}} {jiní {n-1} {k-1}}}$

(5)

a s trochou více práce

${displaystyle {jiný {n-1} {k}} - {iný {n-1} {k-1}} = {frac {n-2k} {n}} {jiný {n} {k}}.}$

Užitečné může být navíc:

${displaystyle {jiný {n} {h}} {jiný {n-h} {k}} = {iný {n} {k}} {jiný {n-k} {h}}.}$

Pro konstantní n, máme následující opakování:

${displaystyle {jin {n} {k}} = {frac {n + 1-k} {k}} {jin {n} {k-1}}.}$

Součty binomických koeficientů

Vzorec

${displaystyle sum _ {k = 0} ^ {n} {jin {n} {k}} = 2 ^ {n}}$

(∗∗)

říká prvky v nČtvrtá řada Pascalova trojúhelníku vždy přidává až 2 zvýšené k nth síla. To se získá z binomické věty (∗) nastavením X = 1 a y = 1. Vzorec má také přirozenou kombinatorickou interpretaci: levá strana shrnuje počet podmnožin {1, ..., n} velikostí k = 0, 1, ..., n, udávající celkový počet podmnožin. (To znamená, že levá strana počítá napájecí sada z {1, ..., n}.) Tyto podmnožiny však lze také generovat postupným výběrem nebo vyloučením každého prvku 1, ..., n; the n nezávislé binární volby (bitové řetězce) umožňují celkem ${displaystyle 2 ^ {n}}$ volby. Levá a pravá strana jsou dva způsoby, jak spočítat stejnou kolekci podmnožin, takže jsou stejné.

Vzorce

${displaystyle sum _ {k = 0} ^ {n} k {jin {n} {k}} = n2 ^ {n-1}}$

(6)

a

${displaystyle sum _ {k = 0} ^ {n} k ^ {2} {jin {n} {k}} = (n + n ^ {2}) 2 ^ {n-2}}$

následovat z binomické věty po rozlišování s ohledem na X (dvakrát pro druhé) a poté střídat X = y = 1.

The Chu – Vandermonde identita, který platí pro všechny komplexní hodnoty m a n a jakékoli nezáporné celé číslo k, je

${displaystyle sum _ {j = 0} ^ {k} {jiné {m} {j}} {jiné {n-m} {k-j}} = {jiné {n} {k}}}$

(7)

a lze je zjistit zkoumáním koeficientu ${displaystyle x ^ {k}}$ v expanzi (1 + X)^m(1 + X)^n−m = (1 + X)ⁿ pomocí rovnice (2). Když m = 1, rovnice (7) redukuje na rovnici (3). Ve zvláštním případě n = 2m, k = m, použitím (1), expanze (7) se stane (jak je vidět na Pascalově trojúhelníku vpravo)

${displaystyle sum _ {j = 0} ^ {m} {jin {m} {j}} ^ {2} = {jin {2m} {m}},}$

(8)

kde výraz na pravé straně je a centrální binomický koeficient.

Další forma identity Chu – Vandermonde, která platí pro všechna celá čísla j, k, a n uspokojující 0 ≤ j ≤ k ≤ n, je

${displaystyle sum _ {m = 0} ^ {n} {jiné {m} {j}} {jiné {n-m} {k-j}} = {jiné {n + 1} {k + 1}}.}$

(9)

Důkaz je podobný, ale využívá rozšíření binomické řady (2) se zápornými celočíselnými exponenty j = k, rovnice (9) dává identita hokejky

${displaystyle sum _ {m = k} ^ {n} {jin {m} {k}} = {jin {n + 1} {k + 1}}}$

a jeho příbuzný

${displaystyle sum _ {r = 0} ^ {m} {jin {n + r} {r}} = {jin {n + m + 1} {m}}.}$

Nechat F(n) označují n-th Fibonacciho číslo.Pak

${displaystyle sum _ {k = 0} ^ {lfloor n / 2floor} {jiné {n-k} {k}} = F (n + 1).}$

To lze dokázat indukce použitím (3) nebo Zeckendorfovo zastoupení. Níže je uveden kombinatorický důkaz.

Multisekce částek

Pro celá čísla s a t takhle ${displaystyle 0leq t$ série multisection dává následující identitu pro součet binomických koeficientů:

${displaystyle {jin {n} {t}} + {jin {n} {t + s}} + {jin {n} {t + 2s}} + ldots = {frac {1} {s}} součet _ { j = 0} ^ {s-1} vlevo (2cos {frac {pi j} {s}} ight) ^ {n} cos {frac {pi (n-2t) j} {s}}.}$

Pro malé s, tyto série mají obzvláště pěkné formy; například,^[6]

${displaystyle {jiný {n} {0}} + {iný {n} {3}} + {iný {n} {6}} + cdots = {frac {1} {3}} vlevo (2 ^ {n} + 2cos {frac {npi} {3}} ight)}$

${displaystyle {jiný {n} {1}} + {iný {n} {4}} + {iný {n} {7}} + cdots = {frac {1} {3}} vlevo (2 ^ {n} + 2cos {frac {(n-2) pi} {3}} vpravo)}$

${displaystyle {iný {n} {2}} + {iný {n} {5}} + {iný {n} {8}} + cdots = {frac {1} {3}} vlevo (2 ^ {n} + 2cos {frac {(n-4) pi} {3}} vpravo)}$

${displaystyle {jiný {n} {0}} + {iný {n} {4}} + {iný {n} {8}} + cdots = {frac {1} {2}} vlevo (2 ^ {n- 1} + 2 ^ {frac {n} {2}} cos {frac {npi} {4}} ight)}$

${displaystyle {iný {n} {1}} + {iný {n} {5}} + {iný {n} {9}} + cdots = {frac {1} {2}} vlevo (2 ^ {n- 1} + 2 ^ {frac {n} {2}} sin {frac {npi} {4}} ight)}$

${displaystyle {iný {n} {2}} + {iný {n} {6}} + {iný {n} {10}} + cdots = {frac {1} {2}} vlevo (2 ^ {n- 1} -2 ^ {frac {n} {2}} cos {frac {npi} {4}} ight)}$

${displaystyle {iný {n} {3}} + {iný {n} {7}} + {iný {n} {11}} + cdots = {frac {1} {2}} vlevo (2 ^ {n- 1} -2 ^ {frac {n} {2}} hřích {frac {npi} {4}} hned)}$

Částečné částky

Ačkoli neexistuje uzavřený vzorec pro částečné částky

${displaystyle sum _ {j = 0} ^ {k} {jiné {n} {j}}}$

binomických koeficientů,^[7] lze znovu použít (3) a indukce, která to ukáže pro k = 0, ..., n − 1,

${displaystyle sum _ {j = 0} ^ {k} (- 1) ^ {j} {jiné {n} {j}} = (- 1) ^ {k} {jiné {n-1} {k}} ,}$

se zvláštním pouzdrem^[8]

${displaystyle sum _ {j = 0} ^ {n} (- 1) ^ {j} {jiné {n} {j}} = 0}$

pro n > 0. Tento druhý výsledek je také zvláštním případem výsledku z teorie konečné rozdíly že pro jakýkoli polynom P(X) stupně menší než n,^[9]

${displaystyle sum _ {j = 0} ^ {n} (- 1) ^ {j} {jiné {n} {j}} P (j) = 0.}$

Rozlišování (2) k časy a nastavení X = -1 dává toto pro${displaystyle P (x) = x (x-1) cdots (x-k + 1)}$, když 0 ≤ k < na následuje obecný případ tím, že se vezmou jejich lineární kombinace.

Když P(X) je stupně menší nebo rovno n,

${displaystyle sum _ {j = 0} ^ {n} (- 1) ^ {j} {jiné {n} {j}} P (n-j) = n! a_ {n}}$

(10)

kde ${displaystyle a_ {n}}$ je koeficient stupně n v P(X).

Obecněji pro (10),

${displaystyle sum _ {j = 0} ^ {n} (- 1) ^ {j} {jiné {n} {j}} P (m + (nj) d) = d ^ {n} n! a_ {n} }$

kde m a d jsou komplexní čísla. Toto následuje okamžité použití (10) na polynom ${displaystyle Q (x): = P (m + dx)}$ namísto ${displaystyle P (x)}$a to pozorovat ${displaystyle Q (x)}$ stále má stupeň menší nebo rovný n, a to jeho koeficient stupně n je dⁿA_n.

The série${displaystyle {frac {k-1} {k}} součet _ {j = 0} ^ {infty} {frac {1} {jiné {j + x} {k}}} = {frac {1} {jiné { x-1} {k-1}}}}$ je konvergentní pro k ≥ 2. Tento vzorec se používá při analýze Problém německého tanku. Vyplývá to z ${displaystyle {frac {k-1} {k}} součet _ {j = 0} ^ {M} {frac {1} {jiné {j + x} {k}}} = {frac {1} {jiné { x-1} {k-1}}} - {frac {1} {jiné {M + x} {k-1}}}}$což dokazuje indukce na M.

Totožnosti s kombinatorickými důkazy

Mnoho identit zahrnujících binomické koeficienty lze dokázat pomocí kombinatorické prostředky. Například pro nezáporná celá čísla ${displaystyle {n} geq {q}}$, identita

${displaystyle sum _ {k = q} ^ {n} {jiné {n} {k}} {jiné {k} {q}} = 2 ^ {n-q} {jiné {n} {q}}}$

(což snižuje na (6) když q = 1) lze zadat a důkaz dvojího počítání, jak následuje. Levá strana počítá počet způsobů výběru podmnožiny [n] = {1, 2, ..., n} minimálně q prvky a značení q vybrané prvky. Pravá strana počítá totéž, protože existují ${displaystyle {binom {n} {q}}}$ způsoby výběru sady q prvky k označení a ${displaystyle 2 ^ {n-q}}$ vybrat, který ze zbývajících prvků [n] také patří do podmnožiny.

V Pascalově identitě

${displaystyle {n zvolte k} = {n-1 vyberte k-1} + {n-1 vyberte k},}$

obě strany počítají počet k-prvkové podmnožiny [n]: dva výrazy na pravé straně je seskupí do těch, které obsahují prvek n a ti, kteří ne.

Identita (8) má také kombinatorický důkaz. Přečte se identita

${displaystyle sum _ {k = 0} ^ {n} {jiné {n} {k}} ^ {2} = {jiné {2n} {n}}.}$

Předpokládejme, že máte ${displaystyle 2n}$ prázdné čtverce uspořádané v řadě a chcete je označit (vybrat) n z nich. Existují ${displaystyle {binom {2n} {n}}}$ způsoby, jak to udělat. Na druhou stranu můžete vybrat svůj n čtverce výběrem k čtverce z prvních n a ${displaystyle n-k}$ čtverce ze zbývajících n čtverce; žádný k od 0 do n bude pracovat. To dává

${displaystyle sum _ {k = 0} ^ {n} {jiné {n} {k}} {jiné {n} {n-k}} = {jiné {2n} {n}}.}$

Nyní použijte (1) k získání výsledku.

Pokud někdo označuje pomocí F(i) posloupnost Fibonacciho čísla, indexováno tak, že F(0) = F(1) = 1, pak totožnost

má následující kombinatorický důkaz.^[10] Jeden může ukázat indukce že F(n) počítá počet způsobů, jak a n × 1 pruh čtverců může být zakryt 2 × 1 a 1 × 1 dlaždice. Na druhou stranu, pokud takový obklad používá přesně k z 2 × 1 dlaždice, pak to používá n − 2k z 1 × 1 dlaždice, a tak používá n − k dlaždice celkem. Existují ${displaystyle {binom {n-k} {k}}}$ způsoby objednání těchto dlaždic, a tedy součet tohoto koeficientu přes všechny možné hodnoty k dává identitu.

Řádek součtu koeficientů

Počet k-kombinace pro všechny k, ${displaystyle sum _ {0leq {k} leq {n}} {jině {n} {k}} = 2 ^ {n}}$, je součet nth řádek (počítáno od 0) binomických koeficientů. Tyto kombinace jsou vyčísleny 1 číslicemi sady základna 2 čísla od 0 do ${displaystyle 2 ^ {n} -1}$, kde každá pozice číslice je položkou ze sady n.

Dixonova identita

Dixonova identita je

${displaystyle sum _ {k = -a} ^ {a} (- 1) ^ {k} {2a zvolte k + a} ^ {3} = {frac {(3a)!} {(a!) ^ {3 }}}}$

nebo obecněji

${displaystyle sum _ {k = -a} ^ {a} (- 1) ^ {k} {a + b zvolit a + k} {b + c vybrat b + k} {c + a vybrat c + k} = {frac {(a + b + c)!} {a!, b!, c!}} ,,}$

kde A, b, a C jsou nezáporná celá čísla.

Kontinuální identity

Některé trigonometrické integrály mají hodnoty vyjádřené z hlediska binomických koeficientů: Pro libovolné ${displaystyle m, nin mathbb {N},}$

${displaystyle int _ {- pi} ^ {pi} cos ((2m-n) x) cos ^ {n} (x) dx = {frac {pi} {2 ^ {n-1}}} {jiné {n } {m}}}$

${displaystyle int _ {- pi} ^ {pi} sin ((2m-n) x) sin ^ {n} (x) dx = {egin {cases} (- 1) ^ {m + (n + 1) / 2 } {frac {pi} {2 ^ {n-1}}} {jiné {n} {m}}, & n {ext {odd}} 0, a {ext {jinak}} konec {případů}}}$

${displaystyle int _ {- pi} ^ {pi} cos ((2m-n) x) sin ^ {n} (x) dx = {egin {cases} (- 1) ^ {m + (n / 2)} { frac {pi} {2 ^ {n-1}}} {jiný {n} {m}}, & n {ext {even}} 0, a {ext {jinak}} konec {případů}}}$

To lze prokázat pomocí Eulerův vzorec převést trigonometrické funkce na komplexní exponenciály, rozšiřující se pomocí binomické věty a integrující pojem po členu.

Generování funkcí

Obyčejné generující funkce

Pro pevné n, obyčejná generující funkce sekvence ${displaystyle {binom {n} {0}}, {binom {n} {1}}, {binom {n} {2}}, ldots}$ je

${displaystyle sum _ {k = 0} ^ {infty} {n zvolte k} x ^ {k} = (1 + x) ^ {n}.}$

Pro pevné k, běžná generující funkce sekvence ${displaystyle {binom {0} {k}}, {binom {1} {k}}, {binom {2} {k}}, ldots,}$ je

${displaystyle sum _ {n = k} ^ {infty} {n zvolte k} y ^ {n} = {frac {y ^ {k}} {(1-y) ^ {k + 1}}}.}$

The bivariate generující funkce binomických koeficientů je

${displaystyle sum _ {n = 0} ^ {infty} sum _ {k = 0} ^ {n} {n zvolte k} x ^ {k} y ^ {n} = {frac {1} {1-y- xy}}.}$

Další, symetrická, dvojrozměrná generující funkce binomických koeficientů je

${displaystyle sum _ {n = 0} ^ {infty} sum _ {k = 0} ^ {infty} {n + k zvolte k} x ^ {k} y ^ {n} = {frac {1} {1- xy}}.}$

Funkce exponenciálního generování

Symetrický exponenciální funkce generující bivariate binomických koeficientů je:

${displaystyle sum _ {n = 0} ^ {infty} sum _ {k = 0} ^ {infty} {n + k zvolte k} {frac {x ^ {k} y ^ {n}} {(n + k )!}} = e ^ {x + y}.}$

Vlastnosti dělitelnosti

V roce 1852 Kummer dokázal, že pokud m a n jsou nezáporná celá čísla a p je prvočíslo, pak největší síla p dělení ${displaystyle {binom {m + n} {m}}}$ rovná se p^C, kde C je počet přeprav, když m a n jsou přidány v základně pRovnocenně exponent prvočísla p v ${displaystyle {binom {n} {k}}}$se rovná počtu nezáporných celých čísel j takové, že zlomková část z k/p^j je větší než zlomková část souboru n/p^j. Z toho lze odvodit, že ${displaystyle {binom {n} {k}}}$ je dělitelné n/gcd (n,k). Z toho tedy zejména vyplývá p rozděluje ${displaystyle {binom {p ^ {r}} {s}}}$ pro všechna kladná celá čísla r a s takhle s < p^r. To však neplatí pro vyšší pravomoci p: například 9 se nerozdělí ${displaystyle {binom {9} {6}}}$.

Trochu překvapivý výsledek od David Singmaster (1974) je, že každé celé číslo dělí téměř všechny binomické koeficienty. Přesněji, opravte celé číslo d a nechte F(N) označují počet binomických koeficientů ${displaystyle {binom {n} {k}}}$ s n < N takhle d rozděluje ${displaystyle {binom {n} {k}}}$. Pak

${displaystyle lim _ {N o infty} {frac {f (N)} {N (N + 1) / 2}} = 1.}$

Od počtu binomických koeficientů ${displaystyle {binom {n} {k}}}$ s n < N je N(N + 1) / 2, to znamená, že hustota binomických koeficientů dělitelná d jde na 1.

Binomické koeficienty mají vlastnosti dělitelnosti související s nejméně běžnými násobky po sobě jdoucích celých čísel. Například:^[11]

${displaystyle {jiný {n + k} {k}}}$ rozděluje ${displaystyle {frac {{ext {lcm}} (n, n + 1, ldots, n + k)} {n}}}$.

${displaystyle {jině {n + k} {k}}}$ je násobkem ${displaystyle {frac {{ext {lcm}} (n, n + 1, ldots, n + k)} {ncdot {ext {lcm}} ({jiné {k} {0}}, {jiné {k} { 1}}, ldots, {jiný {k} {k}})}}}$.

Další fakt: Celé číslo n ≥ 2 je prvočíslo, pokud a pouze pokud jsou všechny střední binomické koeficienty

${displaystyle {jin {n} {1}}, {jin {n} {2}}, ldots, {jin {n} {n-1}}}$

jsou dělitelné n.

Důkaz: Kdy p je hlavní, p rozděluje

${displaystyle {jiní {p} {k}} = {frac {pcdot (p-1) cdots (p-k + 1)} {kcdot (k-1) cdots 1}}}$ pro všechny 0 < k < p

protože ${displaystyle {binom {p} {k}}}$ je přirozené číslo a p rozdělí čitatele, ale ne jmenovatele n je složený, ať p být nejmenším hlavním faktorem n a nechte k = n / p. Pak 0 < p < n a

${displaystyle {jin {n} {p}} = {frac {n (n-1) (n-2) cdots (n-p + 1)} {p!}} = {frac {k (n-1) (n-2) cdots (n-p + 1)} {(p-1)!}} nebo ekvivalent 0 {pmod {n}}}$

jinak čitatel k(n − 1)(n − 2)×...×(n − p + 1) musí být dělitelné n = k×p, to může být pouze tehdy, když (n − 1)(n − 2)×...×(n − p + 1) je dělitelné p. Ale n je dělitelné p, tak p nerozděluje n − 1, n − 2, ..., n − p + 1 a protože p je prime, víme to p nerozděluje (n − 1)(n − 2)×...×(n − p + 1) a tak čitatel nemůže být dělitelný n.

Hranice a asymptotické vzorce

Následující hranice pro ${displaystyle {binom {n} {k}}}$ podržet pro všechny hodnoty n a k takové, že 1 ≤k ≤ n:

${displaystyle {frac {n ^ {k}} {k ^ {k}}} leq {n zvolte k} leq {frac {n ^ {k}} {k!}}$.

První nerovnost vyplývá ze skutečnosti, že

${displaystyle {n choose k} = {frac {n} {k}} cdot {frac {n-1} {k-1}} cdots {frac {n- (k-1)} {1}}}$

a každý z nich ${displaystyle k}$ výrazy v tomto produktu jsou ${displaystyle geq {frac {n} {k}}}$. Podobný argument lze uvést, aby ukázal druhou nerovnost. Konečná přísná nerovnost je ekvivalentní k ${displaystyle e ^ {k}> k ^ {k} / k!}$, to je jasné, protože RHS je člen exponenciální řady ${displaystyle e ^ {k} = součet _ {j = 0} ^ {infty} k ^ {j} / j!}$.

Z vlastností dělitelnosti to můžeme odvodit

${displaystyle {frac {{ext {lcm}} (nk, ldots, n)} {(nk) cdot {ext {lcm}} ({jiný {k} {0}}, ldots, {jiný {k} {k }})}} leq {jiné {n} {k}} leq {frac {{ext {lcm}} (nk, ldots, n)} {nk}}}$,

kde lze dosáhnout obou rovností.^[11]

Oba n a k velký

Stirlingova aproximace poskytuje následující přibližnou hodnotu, platnou když ${displaystyle n, k}$ oba mají sklon k nekonečnu:

${displaystyle {n zvolte k} sim {sqrt {n nad 2pi k (n-k)}} cdot {n ^ {n} nad k ^ {k} (n-k) ^ {n-k}}}$

Protože formy nerovnosti Stirlingova vzorce také vázaly faktoriály, mírné varianty výše uvedené asymptotické aproximace dávají přesné hranice.

Zejména když ${displaystyle n}$ je dostatečně velký:

${displaystyle {2n choose n} sim {frac {2 ^ {2n}} {sqrt {pi n}}}}$a ${displaystyle {sqrt {n}} {2n vyberte n} geq 2 ^ {2n-1}}$

a obecně pro m ≥ 2 a n ≥ 1,^{[proč? ]}

${displaystyle {sqrt {n}} {mn zvolit n} geq {frac {m ^ {m (n-1) +1}} {(m-1) ^ {(m-1) (n-1)}} }}$

Další užitečná asymptotická aproximace, když obě čísla rostou stejnou rychlostí^{[je zapotřebí objasnění ]} je

${displaystyle log _ {2} {n select k} sim nH (k / n) = klog _ {2} (n / k) + (n-k) log _ {2} (n / (n-k))}$

kde ${displaystyle H (p) = - plog _ {2} (p) - (1-p) log _ {2} (1-p)}$ je funkce binární entropie.

Li n je velký a k je blízko n / 2existují různé přesné asymptotické odhady pro binomický koeficient ${displaystyle {jiný {n} {k}}}$. Například pokud ${displaystyle | n / 2-k | ​​= o (n ^ {2/3})}$ pak^[12]

${displaystyle {jin {n} {k}} sim {jin {n} {frac {n} {2}}} e ^ {- d ^ {2} / (2n)} sim {frac {2 ^ {n} } {sqrt {{frac {1} {2}} npi}}} e ^ {- d ^ {2} / (2n)}}$

kde d = n − 2k.

n mnohem větší než k

Li n je velký a k je Ó(n) (tj. pokud k/n → 0), pak

kde znovu Ó je malý o zápis.^[13]

Součty binomických koeficientů

Jednoduchou a hrubou horní hranici pro součet binomických koeficientů lze získat pomocí binomická věta:

${displaystyle sum _ {i = 0} ^ {k} {n zvolte i} leq sum _ {i = 0} ^ {k} n ^ {i} cdot 1 ^ {ki} leq (1 + n) ^ {k }}$

Přesnější hranice jsou dány

${displaystyle {frac {1} {sqrt {8nepsilon (1-epsilon)}}} cdot 2 ^ {H (epsilon) cdot n} leq sum _ {i = 0} ^ {k} {jiné {n} {i} } leq 2 ^ {H (epsilon) cdot n}.}$

což platí pro všechna celá čísla ${displaystyle ngeq kgeq 1}$ s ${displaystyle epsilon doteq k / nleq 1/2}$.^[14]

Zobecněné binomické koeficienty

The nekonečný produktový vzorec pro funkci gama také dává výraz pro binomické koeficienty

${displaystyle (-1) ^ {k} {z zvolte k} = {- z + k-1 vyberte k} = {frac {1} {gama (-z)}} {frac {1} {(k + 1 ) ^ {z + 1}}} prod _ {j = k + 1} {frac {(1+ {frac {1} {j}}) ^ {- z-1}} {1- {frac {z + 1} {j}}}}}$

který poskytuje asymptotické vzorce

${displaystyle {z choose k} cca {frac {(-1) ^ {k}} {Gamma (-z) k ^ {z + 1}}} qquad mathrm {a} qquad {z + k zvolte k} = { frac {k ^ {z}} {Gamma (z + 1)}} vlevo (1+ {frac {z (z + 1)} {2k}} + {mathcal {O}} vlevo (k ^ {- 2} hned) hned)}$

tak jako ${displaystyle k o infty}$.

Toto asymptotické chování je obsaženo v aproximaci

${displaystyle {z + k zvolit k} přibližně {frac {e ^ {z (H_ {k} -gamma)}} {gama (z + 1)}}}$

také. (Tady ${displaystyle H_ {k}}$ je k-th harmonické číslo a ${displaystyle gamma}$ je Euler – Mascheroniho konstanta.)

Dále asymptotický vzorec

${displaystyle {frac {z + k zvolte j} {k zvolte j}} o vlevo (1- {frac {j} {k}} vpravo) ^ {- z} quad {ext {and}} quad {frac {j zvolte jk} {jz vyberte jk}} o doleva ({frac {j} {k}} vpravo) ^ {z}}$

držte se, kdykoli ${displaystyle k o infty}$ a ${displaystyle j / k o x}$ pro nějaké komplexní číslo ${displaystyle x}$.

Zobecnění

Zobecnění na multinomálie

Binomické koeficienty lze zobecnit na multinomiální koeficienty definováno jako číslo:

${displaystyle {n zvolte k_ {1}, k_ {2}, ldots, k_ {r}} = {frac {n!} {k_ {1}! k_ {2}! cdots k_ {r}!}}}$

kde

${displaystyle sum _ {i = 1} ^ {r} k_ {i} = n.}$

Zatímco binomické koeficienty představují koeficienty (X+y)ⁿ, multinomiální koeficienty představují koeficienty polynomu

${displaystyle (x_ {1} + x_ {2} + cdots + x_ {r}) ^ {n}.}$

Pouzdro r = 2 dává binomické koeficienty:

${displaystyle {n zvolit k_ {1}, k_ {2}} = {n zvolit k_ {1}, n-k_ {1}} = {n zvolit k_ {1}} = {n zvolit k_ {2}}. }$

Kombinatorickou interpretací multinomálních koeficientů je distribuce n rozeznatelné prvky r (rozlišitelné) kontejnery, z nichž každý obsahuje přesně k_i prvky, kde i je index kontejneru.

Multinomiální koeficienty mají mnoho vlastností podobných vlastnostem binomických koeficientů, například relace opakování:

${displaystyle {n zvolte k_ {1}, k_ {2}, ldots, k_ {r}} = {n-1 vyberte k_ {1} -1, k_ {2}, ldots, k_ {r}} + {n -1 vyberte k_ {1}, k_ {2} -1, ldots, k_ {r}} + ldots + {n-1 vyberte k_ {1}, k_ {2}, ldots, k_ {r} -1}}$

a symetrie:

${displaystyle {n choose k_ {1}, k_ {2}, ldots, k_ {r}} = {n choose k_ {sigma _ {1}}, k_ {sigma _ {2}}, ldots, k_ {sigma _ {r}}}}$

kde ${displaystyle (sigma _ {i})}$ je permutace z (1, 2, ..., r).

Taylor série

Použitím Stirlingova čísla prvního druhu the rozšíření série kolem libovolně zvoleného bodu ${displaystyle z_ {0}}$ je

${displaystyle {egin {aligned} {z choose k} = {frac {1} {k!}} součet _ {i = 0} ^ {k} z ^ {i} s_ {k, i} & = součet _ { i = 0} ^ {k} (z-z_ {0}) ^ {i} součet _ {j = i} ^ {k} {z_ {0} zvolte ji} {frac {s_ {k + ij, i} } {(k + ij)!}} & = součet _ {i = 0} ^ {k} (z-z_ {0}) ^ {i} součet _ {j = i} ^ {k} z_ {0 }^{ji}{j choose i}{frac {s_{k,j}}{k!}}.end{aligned}}}$

Binomial coefficient with n = 1/2

The definition of the binomial coefficients can be extended to the case where ${displaystyle n}$ is real and ${displaystyle k}$ is integer.

In particular, the following identity holds for any non-negative integer ${displaystyle k}$ :

${displaystyle {{1/2} choose {k}}={{2k} choose {k}}{frac {(-1)^{k+1}}{2^{2k}(2k-1)}}.}$

This shows up when expanding ${displaystyle {sqrt {1+x}}}$ into a power series using the Newton binomial series :

${displaystyle {sqrt {1+x}}=sum _{kgeq 0}{ inom {1/2}{k}}x^{k}.}$

Products of binomial coefficients

One can express the product of two binomial coefficients as a linear combination of binomial coefficients:

${displaystyle {z choose m}{z choose n}=sum _{k=0}^{m}{m+n-k choose k,m-k,n-k}{z choose m+n-k},}$

where the connection coefficients are multinomial coefficients. In terms of labelled combinatorial objects, the connection coefficients represent the number of ways to assign m + n − k labels to a pair of labelled combinatorial objects—of weight m a n respectively—that have had their first k labels identified, or glued together to get a new labelled combinatorial object of weight m + n − k. (That is, to separate the labels into three portions to apply to the glued part, the unglued part of the first object, and the unglued part of the second object.) In this regard, binomial coefficients are to exponential generating series what falling factorials are to ordinary generating series.

The product of all binomial coefficients in the nth row of the Pascal triangle is given by the formula:

${displaystyle prod _{k=0}^{n}{ inom {n}{k}}=prod _{k=1}^{n}k^{2k-n-1}.}$

Rozklad částečné frakce

The partial fraction decomposition of the reciprocal is given by

${displaystyle {frac {1}{z choose n}}=sum _{i=0}^{n-1}(-1)^{n-1-i}{n choose i}{frac {n-i}{z-i}},qquad {frac {1}{z+n choose n}}=sum _{i=1}^{n}(-1)^{i-1}{n choose i}{frac {i}{z+i}}.}$

Newton's binomial series

Newton's binomial series, named after Sir Isaac Newton, is a generalization of the binomial theorem to infinite series:

${displaystyle (1+z)^{alpha }=sum _{n=0}^{infty }{alpha choose n}z^{n}=1+{alpha choose 1}z+{alpha choose 2}z^{2}+cdots .}$

The identity can be obtained by showing that both sides satisfy the diferenciální rovnice (1 + z) F'(z) = α F(z).

The radius of convergence of this series is 1. An alternative expression is

${displaystyle {frac {1}{(1-z)^{alpha +1}}}=sum _{n=0}^{infty }{n+alpha choose n}z^{n}}$

where the identity

${displaystyle {n choose k}=(-1)^{k}{k-n-1 choose k}}$

is applied.

Multiset (rising) binomial coefficient

Binomial coefficients count subsets of prescribed size from a given set. A related combinatorial problem is to count multisety of prescribed size with elements drawn from a given set, that is, to count the number of ways to select a certain number of elements from a given set with the possibility of selecting the same element repeatedly. The resulting numbers are called multiset coefficients;^[15] the number of ways to "multichoose" (i.e., choose with replacement) k items from an n element set is denoted ${displaystyle left(!!{ inom {n}{k}}!!ight)}$.

To avoid ambiguity and confusion with n 's main denotation in this article,
nechat F = n = r + (k – 1) and r = F – (k – 1).

Multiset coefficients may be expressed in terms of binomial coefficients by the rule

${displaystyle { inom {f}{k}}=left(!!{ inom {r}{k}}!!ight)={ inom {r+k-1}{k}}.}$

One possible alternative characterization of this identity is as follows:We may define the falling factorial tak jako

${displaystyle (f)_{k}=f^{underline {k}}=(f-k+1)cdots (f-3)cdot (f-2)cdot (f-1)cdot f}$,

and the corresponding rising factorial as

${displaystyle {color {white}{ ig |}}r^{(k)}=,r^{overline {k}}=,rcdot (r+1)cdot (r+2)cdot (r+3)cdots (r+k-1)}$;

so, for example,

${displaystyle 17cdot 18cdot 19cdot 20cdot 21=(21)_{5}=21^{underline {5}}=17^{overline {5}}=17^{(5)}}$.

Then the binomial coefficients may be written as

${displaystyle { inom {f}{k}}={frac {(f)_{k}}{k!}}={frac {(f-k+1)cdots (f-2)cdot (f-1)cdot f}{1cdot 2cdot 3cdot 4cdot 5cdots k}}}$,

while the corresponding multiset coefficient is defined by replacing the falling with the rising factorial:

${displaystyle left(!!{ inom {r}{k}}!!ight)={frac {r^{(k)}}{k!}}={frac {rcdot (r+1)cdot (r+2)cdots (r+k-1)}{1cdot 2cdot 3cdot 4cdot 5cdots k}}}$.

Generalization to negative integers n

Pro všechny n,

${displaystyle { egin{aligned}{ inom {-n}{k}}&={frac {-ncdot -(n+1)dots -(n+k-2)cdot -(n+k-1)}{k!}}&=(-1)^{k};{frac {ncdot (n+1)cdot (n+2)cdots (n+k-1)}{k!}}&=(-1)^{k}{ inom {n+k-1}{k}}&=(-1)^{k}left(!!{ inom {n}{k}}!!ight);.end{aligned}}}$

In particular, binomial coefficients evaluated at negative integers n are given by signed multiset coefficients. In the special case ${displaystyle n=-1}$, this reduces to ${displaystyle (-1)^{k}={ inom {-1}{k}}=left(!!{ inom {-k}{k}}!!ight).}$

Například pokud n = −4 and k = 7, then r = 4 and F = 10:

${displaystyle { egin{aligned}{ inom {-4}{7}}&={frac {-10cdot -9cdot -8cdot -7cdot -6cdot -5cdot -4}{1cdot 2cdot 3cdot 4cdot 5cdot 6cdot 7}}&=(-1)^{7};{frac {4cdot 5cdot 6cdot 7cdot 8cdot 9cdot 10}{1cdot 2cdot 3cdot 4cdot 5cdot 6cdot 7}}&=left(!!{ inom {-7}{7}}!!ight)left(!!{ inom {4}{7}}!!ight)={ inom {-1}{7}}{ inom {10}{7}}.end{aligned}}}$

Two real or complex valued arguments

The binomial coefficient is generalized to two real or complex valued arguments using the gamma function nebo beta function přes

${displaystyle {x choose y}={frac {Gamma (x+1)}{Gamma (y+1)Gamma (x-y+1)}}={frac {1}{(x+1)mathrm {B} (x-y+1,y+1)}}.}$

This definition inherits these following additional properties from ${displaystyle Gamma }$:

${displaystyle {x choose y}={frac {sin(ypi )}{sin(xpi )}}{-y-1 choose -x-1}={frac {sin((x-y)pi )}{sin(xpi )}}{y-x-1 choose y};}$

moreover,

${displaystyle {x choose y}cdot {y choose x}={frac {sin((x-y)pi )}{(x-y)pi }}.}$

The resulting function has been little-studied, apparently first being graphed in (Fowler 1996 ). Notably, many binomial identities fail: ${displaystyle extstyle {{n choose m}={n choose n-m}}}$ ale ${displaystyle extstyle {{-n choose m}eq {-n choose -n-m}}}$ pro n positive (so ${displaystyle -n}$ negative). The behavior is quite complex, and markedly different in various octants (that is, with respect to the X a y axes and the line ${displaystyle y = x}$), with the behavior for negative X having singularities at negative integer values and a checkerboard of positive and negative regions:

• in the octant ${displaystyle 0leq yleq x}$ it is a smoothly interpolated form of the usual binomial, with a ridge ("Pascal's ridge").
• in the octant ${displaystyle 0leq xleq y}$ and in the quadrant ${displaystyle xgeq 0,yleq 0}$ the function is close to zero.
• in the quadrant ${displaystyle xleq 0,ygeq 0}$ the function is alternatingly very large positive and negative on the parallelograms with vertices

${displaystyle (-n,m+1),(-n,m),(-n-1,m-1),(-n-1,m)}$

• in the octant ${displaystyle 0>x>y}$ the behavior is again alternatingly very large positive and negative, but on a square grid.
• in the octant ${displaystyle -1>y>x+1}$ it is close to zero, except for near the singularities.

Generalization to q-series

The binomial coefficient has a q-analog generalization known as the Gaussian binomial coefficient.

Generalization to infinite cardinals

The definition of the binomial coefficient can be generalized to nekoneční kardinálové by defining:

${displaystyle {alpha choose eta }=|{Bsubseteq A:|B|= eta }|}$

where A is some set with mohutnost ${displaystyle alpha}$. One can show that the generalized binomial coefficient is well-defined, in the sense that no matter what set we choose to represent the cardinal number ${displaystyle alpha}$, ${displaystyle {alpha choose eta }}$ will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.

Assuming the Axiom výběru, lze to ukázat ${displaystyle {alpha choose alpha }=2^{alpha }}$ for any infinite cardinal ${displaystyle alpha}$.

Binomial coefficient in programming languages

Zápis ${displaystyle {n choose k}}$ is convenient in handwriting but inconvenient for psací stroje a počítačové terminály. Mnoho programovací jazyky do not offer a standard podprogram for computing the binomial coefficient, but for example both the Programovací jazyk APL and the (related) J programming language use the exclamation mark: k ! n .

Naive implementations of the factorial formula, such as the following snippet in Krajta:

are very slow and are useless for calculating factorials of very high numbers (in languages such as C nebo Jáva they suffer from overflow errors because of this reason). A direct implementation of the multiplicative formula works well:

(In Python, range(k) produces a list from 0 to k–1.)

Pascal's rule provides a recursive definition which can also be implemented in Python, although it is less efficient:

The example mentioned above can be also written in functional style. Následující Systém example uses the recursive definition

${displaystyle {n choose k+1}={frac {n-k}{k+1}}{n choose k}}$

Rational arithmetic can be easily avoided using integer division

${displaystyle {n choose k+1}=left[(n-k){n choose k}ight]div (k+1)}$

The following implementation uses all these ideas

When computing ${displaystyle extstyle {n choose k+1}=left[(n-k){n choose k}ight]div (k+1)}$ in a language with fixed-length integers, the multiplication by ${displaystyle (n-k)}$ may overflow even when the result would fit. The overflow can be avoided by dividing first and fixing the result using the remainder:

${displaystyle {n choose k+1}=left[ extstyle {n choose k}div (k+1)ight](n-k)+{left[{n choose k} mathrm {mod} (k+1)ight](n-k) over (k+1)}}$

Implementation in the C language:

Another way to compute the binomial coefficient when using large numbers is to recognize that

${displaystyle {n choose k}={frac {n!}{k!,(n-k)!}}={frac {Gamma (n+1)}{Gamma (k+1),Gamma (n-k+1)}}=exp(ln Gamma (n+1)-ln Gamma (k+1)-ln Gamma (n-k+1)),}$

kde ${displaystyle ln}$ ${displaystyle Gamma (n)}$ označuje přirozený logaritmus z gamma function na ${displaystyle n}$. It is a special function that is easily computed and is standard in some programming languages such as using log_gamma v Maxima, LogGamma v Mathematica, gammaln v MATLAB and Python's SciPy module, lngamma v PARI/GP nebo lgamma in C, R,^[16] a Julie. Roundoff error may cause the returned value to not be an integer.

Viz také

Poznámky

Reference

externí odkazy

• „Binomické koeficienty“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Andrew Granville (1997). "Aritmetické vlastnosti binomických koeficientů I. Binomické koeficienty modulo prime power". Konference CMS Proc. 20: 151–162. Archivovány od originál dne 2015-09-23. Citováno 2013-09-03.

Tento článek včlení materiál z následujícího PlanetMath články, které jsou licencovány podle Creative Commons Attribution / Share-Alike License: Binomický koeficient, Horní a dolní mez na binomický koeficient, Binomický koeficient je celé číslo, Zobecněné binomické koeficienty.