Kombinační číslo

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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í číslo se značí ve tvaru {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. Při použití faktoriálu je kombinační číslo obecně rovno


  {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í číslo se používá 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) či Leibnizově pravidle.

Základní vlastnosti[editovat | editovat zdroj]

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},
{{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[editovat | editovat zdroj]

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í. Vztah je tedy přirozeným zobecněním kombinačních čísel a je požíván hlavně ve 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[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]

  • MATOUŠEK, Jiří; NEŠETŘIL, Jaroslav. Kapitoly z diskrétní matematiky. 3., upravené a doplněné vyd. Praha : Karolinum, 2007. ISBN 978-80-246-1411-3. Kapitola 3. Kombinatorické počítání, s. 76–82.  
  • BARTSCH, Hans-Jochen. Matematické vzorce. 4., upravené vyd. Praha : Academia, 2006. ISBN 80-200-1448-9. Kapitola 1.7.1. Binomické koeficienty, binomická věta, s. 156–160.  

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]