Kombinační číslo

Pascalova trojúhelníka, ve kterém je každá hodnota součtem dvou hodnot ležících nad ní. Znázornění binomické expanze do čtvrté mocniny Kombinační číslo je matematická funkce, která udává počet kombinací, tzn. způsobů, jak vybrat k-prvkovou podmnožinu z n-prvkové množiny (k\, a n\, jsou čísla přirozená). Kombinační čísla zapisujeme {n \choose k} (čte se „n nad k“), někdy se používá také značení _n C_k\,, C(n, k)\, či C_n^k. Hodnotu kombinačních čísel lze vyjádřit pomocí faktoriálu: : {n \choose k} = \left\{ \begin{matrix} \frac{n!}{k!(n-k)!}\,&&\mbox{pro }n \geq k \geq 0; \\ 0\,&&\mbox{jinak,}\,\qquad\qquad \end{matrix} \right.

Platí rovnost :1 = {0 \choose 0} = {n \choose 0} = {n \choose n}.

Kombinační čísla se používají hlavně v kombinatorice, velice důležité je využití v binomické větě (přičemž je zde označováno jako binomický koeficient), v Leibnizově pravidle nebo při výpočtu pravděpodobnosti v binomickém rozdělení.

Základní vlastnosti

Pro přirozená čísla n a k, kde 0 \leqq k \leqq n a m \in \mathbb{N} platí

:{n \choose k} = {n \choose {n-k}},

:{{n} \choose {1}} = n,

:{{n} \choose {0}} = {{n} \choose {n}} = 1,

:{n \choose {k+1}} = {n \choose k}\frac{n-k}{k+1},

:{\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}},

:{{n+1} \choose {k}} = {n \choose k}+{n \choose {k-1}},

:{{n-1} \choose {k-1}} + {{n-1} \choose {k}} = {n \choose {k}},

:\sum_{i=k}^n {i \choose {k}} = {n+1 \choose {k+1}},

:\sum_{i=0}^n {{k+i} \choose {i}} = {k+n+1 \choose n},

:\sum_{i=0}^n {n \choose {i}} = 2^n,

:\sum_{i=0}^n (-1)^i{n \choose {i}} = 0,

:\sum_{i=0}^n {n \choose {i}}^2 = {2n \choose {n}}

:\sum_{i=0}^m {{n+i} \choose {n}}={{n+m+1} \choose {n+1}}

:\sum_{i=0}^m{{n+i} \choose k}={{n+m+1} \choose {k+1}}-{{n+1} \choose {k+1}}

:\sum_{i=1}^n{i}={{n+1} \choose {2}}={{n+1} \choose {n-1}}={\frac n 2}(n+1)

Zobecnění kombinačních čísel

Pokud definujeme kombinační číslo takto

{z \choose k} = \frac{z (z-1)(z-2)\cdots (z-k+1)}{k!},

kde k je nezáporné celé číslo, pak je zřejmé, že pravá strana má smysl, i když číslo z není celé nezáporné. Na číslo z dokonce nemusíme klást žádné podmínky, může se jednat dokonce o číslo komplexní. +more Vztah je tedy přirozeným zobecněním kombinačních čísel a je používán hlavně v zobecněné binomické větě.

Další možnou definici nám umožňuje nahrazení faktoriálu gama funkcí

{z \choose k} = \frac{\Gamma(z+1)}{\Gamma(z-k+1)\Gamma(k+1)}

kde z i k mohou být komplexní čísla - pak ovšem nebudou platit popsané vlastnosti kombinačních čísel pro všechny hodnoty.

Odkazy

Literatura

Související články

Pascalův trojúhelník * Binomická věta * Pravidlo součtu * Kombinatorika

Externí odkazy

[url=http://mathworld. wolfram. +morecom/BinomialCoefficient. html]Kombinační číslo na encyklopedii MathWorld[/url] (anglicky) * [url=http://www. elektro-energetika. cz/calculations/komb. php]Kalkulátor kombinačního čísla[/url].

Kategorie:Matematické funkce Kategorie:Kombinatorika