Binomický koeficient je koeficient před členem v expanzi Newtonova binomu v mocninách . Koeficient at je označen nebo a zní „binomický koeficient z by “ (nebo „počet kombinací z by “):
pro přírodní síly .
Binomické koeficienty lze také definovat pro libovolné reálné exponenty . V případě libovolného reálného čísla jsou binomické koeficienty definovány jako koeficienty rozšíření výrazu do nekonečné mocninné řady :
,kde v případě nezáporných celých čísel všechny koeficienty at zmizí, a proto je tento rozvoj konečným součtem.
V kombinatorice je binomický koeficient pro nezáporná celá čísla a interpretován jako počet kombinací by , tj . jako počet všech (nepřísných) podmnožin ( vzorků ) velikosti v -prvkové množině .
Binomické koeficienty často vyvstávají v problémech v kombinatorice a teorii pravděpodobnosti . Zobecnění binomických koeficientů jsou multinomické koeficienty .
Výpočtem koeficientů v rozšíření mocninné řady lze získat explicitní vzorce pro binomické koeficienty .
Pro všechna reálná čísla a celá čísla :
,kde označuje faktoriál . _
Pro nezáporná celá čísla a vzorce platí také:
.Pro celočíselné záporné exponenty jsou binomické expanzní koeficienty :
.Identita:
umožňuje uspořádat binomické koeficienty pro nezáporná celá čísla ve formě Pascalova trojúhelníku, ve kterém se každé číslo rovná součtu dvou vyšších:
.Trojúhelníkový stůl navržený Pascalem ve svém Pojednání o aritmetickém trojúhelníku (1654) se od zde napsaného liší otočením o 45°. Tabulky pro zobrazování binomických koeficientů byly známy již dříve ( Tartaglia , Omar Khayyam ).
Pokud jsou v každém řádku Pascalova trojúhelníku všechna čísla dělena (toto je součet všech čísel v řádku ), pak všechny řádky, jak jdou do nekonečna, budou mít tvar normální distribuční funkce .
Pro pevnou hodnotu je generující funkce posloupnosti binomických koeficientů :
.Pro pevnou hodnotu je generující funkce posloupnosti koeficientů :
.Dvourozměrná generující funkce binomických koeficientů pro celá čísla je:
, nebo .Z Lukovy věty vyplývá, že:
ale obecněji
.Konvoluce Vandermonde :
,kde . _ Tato identita je získána výpočtem koeficientu at v expanzi , přičemž se bere v úvahu identita . Součet přebírá všechna celá čísla , pro která . Pro libovolná reálná čísla bude počet nenulových členů v součtu konečný.
Důsledek konvoluce Vandermonde:
.Obecnější identita:
pokud .Dalším důsledkem konvoluce je následující identita: .
Existují také rovnosti:
Odkud to pochází:
,kde je počet umístění od do .
Vezmeme-li čtvercovou matici, počítáme prvky podél ramen Pascalova trojúhelníku a otočíme matici o kterýkoli ze čtyř rohů, pak je determinant těchto čtyř matic ±1 pro libovolný , a determinant matice s vrcholem trojúhelník v levém horním rohu je 1.
V matici čísla na diagonále opakují počty řádků Pascalova trojúhelníku ( ). Dá se rozložit na součin dvou striktně diagonálních matic: spodní trojúhelníkové a té, kterou z ní získáme transpozicí:
,kde . Inverzní matice k má tvar:
.Je tedy možné rozložit inverzní matici k na součin dvou přísně diagonálních matic: první matice je horní trojúhelníková a druhá je získána z první transpozicí, což nám umožňuje dát explicitní výraz pro inverzní prvky:
, kde , , , .Prvky inverzní matice se mění při změně její velikosti a na rozdíl od matice nestačí přiřadit nový řádek a sloupec. Sloupec matice je v argumentu polynom stupně , proto první p sloupce tvoří úplný základ v prostoru vektorů délky +1, jejichž souřadnice lze interpolovat polynomem stejného nebo menšího stupně . Spodní řádek matice je ortogonální k jakémukoli takovému vektoru.
for , kde je polynom stupně .Pokud lze vektor libovolné délky interpolovat polynomem stupně , pak je bodový součin s řádky (číslovanými od 0) matice nulový. Pomocí výše uvedené identity a jednoty bodového součinu spodního řádku matice a posledního sloupce matice získáme:
.Pro exponent větší můžete nastavit rekurzivní vzorec:
,kde je polynom
.Abychom to dokázali, nejprve stanovíme identitu:
.Pokud chcete najít vzorec ne pro všechny exponenty, pak:
.Nejvyšší koeficient je 1, k nalezení ostatních koeficientů bude zapotřebí hodnot a-1:
pro .Přímo ze Stirlingova vzorce vyplývá, že pro platí .
Binomické koeficienty , ... jsou celočíselné polynomy , to znamená, že berou celočíselné hodnoty pro celočíselné hodnoty , - to lze snadno pochopit například z Pascalova trojúhelníku. Navíc tvoří základ celočíselných polynomů, ve kterých jsou všechny celočíselné polynomy vyjádřeny jako lineární kombinace s celočíselnými koeficienty. [jeden]
Standardní báze , … zároveň neumožňuje vyjádřit všechny celočíselné polynomy, pokud jsou použity pouze celočíselné koeficienty, protože již má zlomkové koeficienty u mocnin .
Tento výsledek zobecňuje na polynomy v mnoha proměnných. Konkrétně, pokud má polynom stupně skutečné koeficienty a nabývá celočíselné hodnoty pro celočíselné hodnoty proměnných, pak
,kde je polynom s celočíselnými koeficienty. [2]
Binomické koeficienty lze vypočítat pomocí rekurzivního vzorce , pokud jsou hodnoty pro uloženy v každém kroku . Tento algoritmus je zvláště účinný, pokud potřebujete získat všechny hodnoty pro pevný . Algoritmus vyžaduje paměť ( při výpočtu celé tabulky binomických koeficientů) a čas (za předpokladu, že každé číslo zabírá jednotku paměti a operace s čísly se provádějí za jednotku času), kde — « » je velké .
S pevnou hodnotou lze binomické koeficienty vypočítat pomocí rekurzivního vzorce s počáteční hodnotou . Tato metoda vyžaduje paměť a čas k výpočtu hodnoty .
Pokud chcete vypočítat koeficienty pro pevnou hodnotu , můžete použít vzorec pro počáteční podmínku . V každém kroku iterace se čitatel sníží o (počáteční hodnota je ) a jmenovatel se odpovídajícím způsobem zvýší o (počáteční hodnota je ). Tato metoda vyžaduje paměť a čas k výpočtu hodnoty .