Vlastnosti kombinačních čísel

Pozn. k obsahu: Zdrojová prezentace se při převodu ukázala jako prázdná (obsah byl výhradně v animacích, které konverze nezachytila). Celý obsah tohoto tématu je proto nově napsaný a navazuje na Kombinace bez opakování, kde bylo kombinační číslo $(n k )$ zavedeno.

Kombinační čísla $(n k ) = k!(n - k)! n! $ mají několik užitečných vlastností, které se hodí jak k rychlému výpočtu, tak k důkazům dalších vzorců (např. binomické věty).

Krajní hodnoty

$(n 0 ) = 1$

$(n n ) = 1$

Existuje přesně jeden způsob, jak vybrat „nic” (prázdnou skupinu) nebo jak vybrat „všechno” (celou n-tici) z $n$ prvků.

Symetrie

$(n k ) = (n n - k )$

Vybrat $k$ prvků, které DO skupiny patří, je stejně možností jako vybrat $n - k$ prvků, které do skupiny nepatří — jde jen o dva pohledy na tentýž výběr.

Například: $(83 ) = (85 )$ , protože obojí se rovná $3! \cdot 5! 8! $ .

Pascalovo pravidlo (součtový vzorec)

$(n k ) = (n - 1 k - 1 ) + (n - 1 k )$

Toto pravidlo říká, že každé kombinační číslo je součtem dvou kombinačních čísel „o řádek výš” — je to přesně pravidlo, podle kterého se sestrojuje Pascalův trojúhelník: každé číslo je součtem dvou čísel nad ním.

Odvození (myšlenkově): vybíráme $k$ -člennou skupinu z $n$ prvků. Zaměříme se na jeden konkrétní prvek $X$ . Buď $X$ ve skupině je (pak zbývá vybrat $k - 1$ prvků ze zbylých $n - 1$ , tedy $(n - 1 k - 1 )$ možností), nebo $X$ ve skupině není (pak vybíráme celých $k$ prvků ze zbylých $n - 1$ , tedy $(n - 1 k )$ možností). Součet obou případů pokrývá všechny možnosti.

Součet řádku Pascalova trojúhelníku

$(n 0 ) + (n 1 ) + (n 2 ) + \dots + (n n ) = 2 n$

Součet všech kombinačních čísel v $n$ -tém řádku je $2 n$ — to odpovídá tomu, že $n$ -prvková množina má celkem $2 n$ různých podmnožin (každý prvek buď do podmnožiny patří, nebo ne — dvě možnosti pro každý z $n$ prvků).

Hodnoty, které se vyplatí znát nazpaměť

Kombinační čísla s malým $k$ (nebo s $k$ blízko $n$ ) se nemusí počítat přes faktoriály — po zkrácení zbude jednoduchý výraz.

Výběr jednoho prvku:

$(n 1 ) = n$

Výběr všech prvků kromě jednoho:

$(n n - 1 ) = n$

Výběr dvojice:

$(n 2 ) = 2 n (n - 1) $

Odvození: $(n 2 ) =$ $2! (n - 2)! n! =$ $2 (n - 2)! n (n - 1) (n - 2)! =$ $2 n (n - 1) $ . Dvojic uspořádaných je $n (n - 1)$ (to je $V (2, n)$ ), a protože na pořadí ve dvojici nezáleží, dělíme dvěma.

Výběr trojice:

$(n 3 ) = 6 n (n - 1) (n - 2) $

Rychlý výpočet libovolného kombinačního čísla: v čitateli $k$ činitelů od $n$ dolů, ve jmenovateli $k!$ — např. $(94 ) = 4 \cdot 3 \cdot 2 \cdot 1 9 \cdot 8 \cdot 7 \cdot 6 = 126$ . Je-li $k > 2 n $ , použijte nejdřív symetrii: $(2018 ) = (202 ) = 2 20 \cdot 19 = 190$ .

Typické úlohy na výběr dvojic

Vzorec $2 n (n - 1) $ se v úlohách objevuje pořád dokola, jen v jiném převleku:

Úloha	Proč dvojice	Počet
zápasy v turnaji „každý s každým“ ( $n$ týmů)	zápas = neuspořádaná dvojice týmů	$2 n (n - 1) $
podání rukou ( $n$ lidí, každý s každým)	podání ruky = dvojice lidí	$2 n (n - 1) $
přímky určené $n$ body (žádné tři na přímce)	přímka = dvojice bodů	$2 n (n - 1) $
úhlopříčky konvexního $n$ -úhelníku	spojnice dvou vrcholů, bez $n$ stran	$2 n (n - 1) - n = 2 n (n - 3) $
zápasy „doma a venku“ (každý s každým dvakrát)	záleží na tom, kdo je doma — uspořádaná dvojice	$n (n - 1)$
trojúhelníky s vrcholy v $n$ bodech (žádné tři na přímce)	trojúhelník = trojice bodů	$6 n (n - 1)(n - 2) $

Počet úhlopříček konvexního n-úhelníku:

$u n = 2 n (n - 3) $

Z každého vrcholu vede úhlopříčka do všech ostatních vrcholů kromě dvou sousedních (a sebe), tedy $n - 3$ úhlopříček; každou ale počítáme dvakrát (z obou konců), proto dělíme dvěma. Například: šestiúhelník má $2 6 \cdot 3 = 9$ úhlopříček.

Rovnice s kombinačními čísly

Kombinační číslo přepíšeme podle vzorců výše na výraz s $n$ , vyřešíme vzniklou (obvykle kvadratickou) rovnici a ponecháme jen přirozená řešení, která splňují podmínky ( $(n k )$ má smysl jen pro $n \geq k \geq 0$ ).

Například: $(n 2 ) = 28$ → $2 n (n - 1) = 28$ → $n 2 - n - 56 = 0$ → $n = 8$ (kořen $n = -7$ nevyhovuje).

Příklady

Příklad 1: Ověřte Pascalovo pravidlo pro $(62 )$ .

Výsledek: C(6,2) = 15. Podle pravidla by mělo platit C(5,1) + C(5,2) = 5 + 10 = 15. Souhlasí.

Příklad 2: Kolik podmnožin (včetně prázdné a celé množiny) má pětiprvková množina?

Výsledek: 2⁵ = 32 podmnožin — přímo podle vzorce pro součet řádku Pascalova trojúhelníku.

Příklad 3: Bez počítání faktoriálů určete, čemu se rovná $(107 )$ , víte-li, že $(103 ) = 120$ .

Výsledek: podle symetrie C(10,7) = C(10,3) = 120

Příklad 4: Kolik zápasů se odehraje v hokejové lize s 14 týmy, hraje-li každý s každým dvakrát (doma a venku)?

Výsledek: $14 \cdot 13 = 182$ zápasů — nebo $2 \cdot (142 ) = 2 \cdot 91 = 182$

Příklad 5: Na oslavě si všichni navzájem podali ruce, celkem došlo ke 45 podáním rukou. Kolik lidí bylo na oslavě?

Výsledek: $2 n (n - 1) = 45$ → $n 2 - n - 90 = 0$ → $n = 10$ (kořen $-9$ nevyhovuje)

Příklad 6: Který mnohoúhelník má 20 úhlopříček?

Výsledek: $2 n (n - 3) = 20$ → $n 2 - 3 n - 40 = 0$ → $n = 8$ , osmiúhelník (kořen $-5$ nevyhovuje)

Příklad 7: Řešte rovnici $(n n - 2 ) = 21$ .

Výsledek: podle symetrie $(n n - 2 ) = (n 2 )$ : $2 n (n - 1) = 21$ → $n 2 - n - 42 = 0$ → $n = 7$ (podmínka $n \geq 2$ )

Příklad 8: Řešte rovnici $(n 2 ) + (n + 1 2 ) = 49$ .

Výsledek: $2 n (n - 1) + 2 (n + 1) n =$ $2 n (n - 1 + n + 1) =$ $n 2 =$ $49$ → $n = 7$ (ověření: $21 + 28 = 49$ )

Zdroje

CALDA, Emil, DUPAČ, Václav. Matematika pro gymnázia. Kombinatorika, pravděpodobnost, statistika. Praha: Prometheus, 2006.