Kombinační číslo

Kombinační číslo je matematická funkce, která udává počet kombinací, tzn. způsobů, jak vybrat $k$-prvkovou podmnožinu (bez ohledu na pořadí jejích prvků) 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:

Binomické koeficienty lze uspořádat do tvaru Pascalova trojúhelníka, ve kterém je každá hodnota součtem dvou hodnot ležících nad ní. Pokud počítáme od nuly, tak na $n$-tém řádku odshora a $k$-té pozici na daném řádku se nachází ${n \choose k}$.

Znázornění binomické expanze do čtvrté mocniny

${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}}={{0} \choose {0}}=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 \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í. 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

• 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

• Pascalův trojúhelník
• Binomická věta
• Pravidlo součtu
• Kombinatorika
• Variace – na rozdíl od kombinace, u variace záleží na pořadí vybraných prvků.

Externí odkazy

• Obrázky, zvuky či videa k tématu kombinační číslo na Wikimedia Commons
• Kombinační číslo na encyklopedii MathWorld (anglicky)
• Kalkulátor kombinačního čísla

Autoritní data	GND: 4145586-1

Portály: Matematika