Binomický koeficient

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 .

Explicitní vzorce

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 :

.

Pascalův trojúhelník

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 .

Vlastnosti

Generování funkcí

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 .

Dělitelnost

Z Lukovy věty vyplývá, že:

Základní identity

Newtonův binom a důsledky

ale obecněji

.

Vandermondova konvoluce a důsledky

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: .

Jiné identity

.

Existují také rovnosti:

Odkud to pochází:

,

kde  je počet umístění od do .

Maticové vztahy

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 .

Asymptotika a odhady

Přímo ze Stirlingova vzorce vyplývá, že pro platí .

Celočíselné polynomy

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]

Výpočtové algoritmy

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 .

Poznámky

  1. Prasolov V. V. Kapitola 12. Celočíselné polynomy // Polynomy . — M. : MTsNMO , 1999, 2001, 2003.
  2. Yu. Matiyaševič. Hilbertův desátý problém. - Věda, 1993.

Literatura