Variace a kombinace Shrneme základní poznatky z kombinatoriky. Výchozí kombinatorickou funkcí je faktoriál, který je pro každé číslo n G NU {0} definován předpisem: í 1 pro n = 0, n! = < I 1-2-3- ... -(n—lj-n pro n > 0. Další základní kombinatorickou funkcí je binomický koeficient, nebo též kombinační číslo, definované pro každá dvě čísla n, k G N U {0} splňující k < n předpisem: \kj k\\n-k)\' Všimněme si, že pak pro libovolné n G N U {0} platí 0=0- a dále pro libovolná n, k G N U {0} splňující k < n platí (fc) = (n - k) " Následující fakt lze považovat za rekurentní formuli pro binomické koeficienty. Tvrzení. Pro libovolná n, k G N splňující k < n platí Důkaz. Postupně dostáváme (n - 1\ | ín-l\ _ (n- 1)! | (n - 1)! k-lj ' V * / (fc-l)!-(n-fc)! fc!-(n-fc-l)! _ (n - l)\-(k + n - k) _ n\ _ ín\ ~ k\-{n-k)\ ~ k\-{n-k)\ ~ \k) l Následuje binomická věta. Věta. Pro libovolná 1,1/Ela pro libovolné n G N platí (* + y)" = £ Q*V-*. fc=0 ^ ' Důkaz. Postupujeme indukcí vzhledem k n. Pro n = 1 není co dokazovat. Nechť dále n > 1. Podle indukčního předpokladu pro n — 1 máme n—1 / (n k k=0 Odtud pak s využitím předchozí rekurentní formule pro binomické koeficienty dostáváme (x + y)n={x + y)n-1ix + y) = (£ (V) sV-*-1) ■(*+*) fc=0 ^ ' fc=0 ^ ' n — 1\ i, „._fc . / n — 1\ xky-n-k =e(::í)^ + ev t fc=l v 7 fc=0 x = £íľ)*v-fc fc=0 v ' Důsledky. Pro libovolné n G N U {0} platí n n ■ = >n fc=o v ' 1 pro n = 0, 0 pro n > 0. Důkaz. Pro n = 0 jsou obě rovnosti zřejmé a pro n > 0 plynou z binomické věty v prvním případě pro x = y = 1 a ve druhém případě pro x = — 1 a y = 1. Obecnější kombinatorickou funkcí je polynomický koeficient. Pro libovolná i G N a n, ..., kt G N U {0} splňující n = fci + ■ ■ ■ + ki je tento koeficient definován předpisem: Následuje rekurentní formule pro polynomické koeficienty. Tvrzení. Pro libovolná l G N, n G N a h,..., kt G N U {0} splňující n = k\ + ■ ■ ■ + ki platí kde suma je přes všechna j = 1,..., l taková, že k j G N. Důkaz je veden obdobným způsobem jako důkaz výše uvedené rekurentní formule pro binomické koeficienty. Následující věta je zobecněním binomické věty. Věta. Pro libovolné i G N, libovolná x\,..., X£ G M a libovolné n G N platí kde suma je přes všechny uspořádané £-tice (k\,... ,kt) čísel z N U {0} splňující n = k\ + ■ ■ ■ + k\. 3 Důkaz je podobný důkazu binomické věty s tím rozdílem, že nyní je využita předchozí rekurentní formule pro polynomické koeficienty. Důsledek. Pro libovolné l G N a libovolné n G NU {0} platí kde suma je přes všechny uspořádané £-tice (k\,... ,kt) čísel z N U {0} splňující n = k\ + ■ ■ ■ + k\. Důkaz. Pro n = 0 je tato rovnost zřejmá a pro n > 0 plyne z předchozí věty pro x\ = ■ ■ ■ = x t = 1. Nechť n, k G N splňují k < n a nechť S je n-prvková množina. Pak variace k-té třídy v množině S1 jsou libovolné uspořádané fc-tice vzájemně různých prvků a\, a,2,..., G S. Takovou uspořádanou fc-tici můžeme vnímat také jako prosté zobrazení množiny {1,..., k} do množiny S, které každému číslu i G {1,..., k} přiřazuje prvek a j G S. Takové zobrazení je možno přehledně zapsat například ve tvaru Tato zobrazení je ovšem možno uvažovat i pro k = 0, v tom případě se jedná o jediné, totiž prázdné zobrazení, a v takovém případě je možno připustit i n = 0, tedy prázdnou množinu S. Tvrzení. Nechť n, k G N U {0} splňují k < n. Pak počet všech variací k-té třídy v n-prvkové množině S* je roven číslu (dl, Gt2, • • • , Gtfc) (n-k)\' 4 Důkaz. Pro k = 0 je tvrzení jasné a pro n, k G N je třeba si uvědomit, že j0^y_ = n-{n — l)-{n — 2) -... - {n — k + 1). Nechť n G N U {0}. Pak variace n-té třídy v n-prvkové množině S se nazývají permutace množiny S. Důsledek. Nechť n G N U {0}. Pak počet všech permutací n-prvkové množiny S* je roven číslu n!. Nechť dále n G NU {0} a k G N jsou libovolná čísla a nechť S je n-prvková množina. Uvažujeme-li nyní zcela libovolné uspořádané fc-tice prvků množiny S, tedy libovolné prvky kartézské mocniny Sk, dostáváme variace k-té třídy v množině S s opakováním. Takové uspořádané fc-tice lze ovšem podobným způsobem jako výše nyní vnímat jako zcela libovolná zobrazení množiny {1,..., k} do množiny S. Tato zobrazení lze ovšem zase uvažovat i pro fc = 0av tom případě jde opět o jediné, totiž prázdné zobrazení. Tvrzení. Nechť n, k G N U {0}. Pak počet všech variací k-té třídy v n-prvkové množině S s opakováním je roven číslu nk. Poznámka. Aby toto tvrzení platilo i pro n = k = 0, je třeba klást 0° = 1. Nechť nyní n,k G NU{0} splňují k < n a nechť S je n-prvková množina. Pak kombinace k-té třídy v množině S jsou libovolné fc-prvkové podmnožiny T C S. Poznamenejme, že tyto fc-prvkové podmnožiny lze jednoznačně popsat pomocí jejich tzv. charakteristických zobrazení. Jde o libovolná zobrazení / : S —y {0,1} splňující podmínku X^aeS f(a) = ^- Přitom podmnožina T C S je popsána zobrazením / : S —>• {0,1}, které je dáno předpisem: (Va G S)(f (a) = 1 ^ a G T). 5 Tvrzení. Nechť n, k G N U {0} splňují k < n. Pak počet všech kombinací k-té třídy v n-prvkové množině S* je roven číslu fn\ _ n! \k) ~ kl{n-k)\ ' Důkaz plyne ihned z předminulého tvrzení této kapitoly a z jeho důsledku. Stačí totiž uvážit, kolik existuje permutací fc-prvkové podmnožiny T C S. Tyto permutace nejsou ovšem ničím jiným, než variacemi k-té třídy v n-prvkové množině S. Nechť dále n, G NU {0} jsou libovolná čísla a nechť S je n-prvková množina. Vedeni předchozím popisem obyčejných kombinací k-té třídy v množině S prostřednictvím jejich charakteristických zobrazení, definujeme nyní kombinace k-té třídy v množině S s opakováním jakožto libovolná zobrazení g : S —y N U {0} splňující podmínku X^eS #(a) = ^- Takové zobrazení lze interpretovat jako popis souboru k prvků vybraných z množiny S, v němž se některé prvky mohou vyskytovat opakovaně. Zmíněný popis spočívá v tom, že pro každý prvek a E S udává číslo g(a) počet výskytů prvku a v daném souboru, tedy v dané kombinaci s opakováním. Tvrzení. Nechť nGNa&GNU{0}. Pak počet všech kombinací k-té třídy v n-prvkové množině S s opakováním je roven číslu rn + k-1 V * Důkaz. Očíslujme prvky množiny S, takže můžeme psát S = {ai, Gt2,..., an}. Pak lze kombinace k-té třídy v množině S s opakováním jednoznačně zadávat pomocí posloupností nul a jedniček obsahujících k jedniček a n — 1 nul následujícím způsobem. Uvažme libovolnou takovou posloupnost. V této posloupnosti jednotlivé nuly rozdělují jedničky do n skupin: skupina před první nulou, skupina mezi první a druhou nulou, atd., až 6 skupina za poslední nulou. Některé tyto skupiny ovšem mohou být i prázdné. Přiřaďme nyní této poslounosti kombinaci k-té třídy v množině S s opakováním, která obsahuje tolik prvků a\, kolik je jedniček v první skupině, tolik prvků Gt2, kolik je jedniček ve druhé skupině, atd., až nakonec tolik prvků an, kolik je jedniček v poslední skupině. Je tedy počet uvažovaných kombinací s opakováním roven počtu výše popsaných posloupností nul a jedniček. Zadat takovou posloupnost ovšem znamená určit, na kterých k pozicích v této posloupnosti budou stát jedničky. Je tedy třeba zadat podmnožinu obsahující k pozic z celkového počtu n + k — 1 pozic. Podle tvrzení o počtu obyčejných kombinací k-té třídy je tento počet roven shora uvedenému číslu. Závěrem nechť n G N U {0} a nechť i G N. Nechť U je ^-prvková množina. Vypišme ji ve tvaru U = {fy, 62, • • •, fy}-Uvažme libovolnou kombinaci n-té třídy v množině U s opakováním chápanou jako soubor n prvků vybraných z množiny U, v němž se některé prvky vyskytují opakovaně. Nechť k\ je počet výskytů prvku 61, nechť k 1. Vezměme libovolnou permutaci s opakováním uvažovaného typu v množině U chápanou jako uspořádanou n-tici prvků. Vyjmeme-li z ní všechny výskyty prvku bi, dostaneme permutaci s opakováním v množině U — {bi}. Podle indukčního předpokladu je počet takovýchto konstrukci původní permutace s opakováním je třeba znát, na kterých ki pozicích v původní uspořádané n-tici stál prvek bt. Volbu těchto pozic je podle tvrzení o počtu kombinací, tentokrát ki-té třídy v n-prvkové množině, možno provést (^) způsoby. Odtud plyne, že pak celkový počet všech původně uvažovaných permutací s opakováním je roven číslu permutací s opakováním roven Přitom k re- n — ki ki\-(n - kt)\ hl ... -kt-i\ n\ (n — kg)\ 8