kombinatorika

Příklad 162

Kolika způsoby lze postavit 5 mužů a 7 žen do řady tak, aby žádní 2 muži nestáli vedle sebe?

Řešení	Ukázat
7 žen vytváří 8 pozic, z nichž vybereme 5 pozic pro muže. Ale ženy jsou rozlišitelné, takže je můžeme přerovnat $7!$ způsoby a stejně tak můžeme přerovnat $5!$ způsoby muže na vybraných pozicích. Výběr i přerovnání jsou nezávislé, takže celkový počet $n={8\choose5}\cdot7!\cdot5!$

Příklad 163

Kolika způsoby můžeme rozdat 27 knih osobám A, B, C tak, aby A a B dohromady dostali dvakrát víc knih než C?

Řešení	Ukázat
Nejprve vybereme 9 knih, které dostane C. To lze ${27\choose9}$ způsoby. U každé ze zbývajících knih máme vždy dvě možnosti komu je dát (A nebo B). Celkový počet možností je ${27\choose9}\cdot2^{18}.$

Příklad 164

V Senátu zasedá 100 senátorů, po 2 z každého z 50-ti států. Kolika způsoby lze zvolit 4-členný výbor tak, aby v něm nebyli 2 senátoři z téhož státu?

Řešení	Ukázat
Vybereme 4 státy ${50\choose4}$ způsoby. U každého vybraného státu pak máme dvě možnost pro výběr senátorů. ${50\choose4}\cdot2^4$

Příklad 165

Množinu $B=\{a,b,c,d,e,f,g\}$ uspořádáme všemi možnými způsoby. V kolika případech bude prvek $b$ před prvkem $c?$ (kdekoliv!)

Řešení	Ukázat
Vybereme pozice pro $b$ a $c$ ${7\choose2}$ způsoby. Zbylých 5 prvků můžeme přerovnat $5!$ způsoby. $n=5!\cdot{7\choose2}$

Příklad 166

Určete, kolika způsoby lze na šachovnici $8\times8$ postavit 5 různých figur tak, aby 2 stály na černých a 3 na bílých polích.

Řešení	Ukázat
Vybereme 2 figury na černá pole ${5\choose2}.$ Jejich umístění jsou variace. $n={5\choose2}\cdot V_2(32)\cdot V_3(32)$

Příklad 167

Kolika způsoby můžeme uspořádat 5 červených, 5 zelených a 5 modrých míčů do řady, když žádné dva modré míče nesmí být vedle sebe? (Míče stejné barvy jsou nerozlišitelné)

Řešení	Ukázat
Seřadíme si červené a zelené míče. To lze $\frac{10!}{5!\cdot5!}$ způsoby. V takto vytvořené řadě je 11 mezer, z nichž musíme vybrat 5 mezer pro modré míče. To lze ${11\choose5}$ způsoby. $n=\frac{10!}{5!\cdot5!}\cdot{11\choose5}$

Příklad 168

V pokoji na koleji bydlí tři studenti. Dohromady mají 4 různé šálky, k nim 5 různých podšálků a 6 různých čajových lžiček. Kolika způsoby můžou na kulatý stůl naaranžovat tři soupravy?

Řešení	Ukázat
${4\choose3}\cdot{5\choose3}\cdot{6\choose3}\cdot2!\cdot3!\cdot3!$

Příklad 169

Na maturitním večírku je 15 hochů a 12 děvčat. Určete, kolika způsoby z nich lze vybrat čtyři současně tančící taneční páry.

Řešení	Ukázat
${15\choose4}\cdot{12\choose4}\cdot4!$

Příklad 170

Určete, kolika způsoby lze ze sedmi chlapců a čtyř dívek vybrat šestičlennou skupinu, v níž jsou právě dvě dívky.

Řešení	Ukázat
${7\choose4}\cdot{4\choose2}$

Příklad 171

Ve je skupině 18 chlapců a 14 dívek. Kolika způsoby lze zvolit 3 zástupce mají-li to být dva chlapci a jedna divka?

Řešení	Ukázat
${18\choose2}\cdot{14\choose1}$

Příklad 172

Spolek má 20 členů, z toho je 8 žen. Kolikerým způsobem lze vybrat tříčlenný výbor spolku tak, aby v něm byla právě jedna žena?

Řešení	Ukázat
${12\choose2}\cdot{8\choose1}$

Příklad 173

Ve sportovním oddílu je 12 děvčat a 10 chlapců. Kolikerým způsobem lze vybrat šestičlenné družstvo, aby v něm byli 3 chlapci a 3 děvčata?

Řešení	Ukázat
${12\choose3}\cdot{10\choose3}$

Příklad 174

Kolika způsoby můžeme rozdělit 8 chlapců a 4 dívky do dvou rozlišitelných družstev po šesti, když v každém družstvu musí být dvě dívky?

Řešení	Ukázat
${8\choose4}\cdot{4\choose2}$

Příklad 175

Kolika způsoby lze rozdělit 8 dívek a 12 chlapců na dvě neoznačená desetičlenná družstva tak, aby v každém družstvu byla 4 děvčata a 6 chlapců?

Řešení	Ukázat
$\frac12\cdot{8\choose4}\cdot{12\choose6}$

Příklad 176

Kolika způsoby můžeme rozdělit 20 lidí do tří skupin tak, že v první skupině je 10 lidí, ve druhé 6 lidí a ve třetí zbytek?

Řešení	Ukázat
${20\choose10}\cdot{10\choose6}$

666 příkladů z kombinatoriky

Kombinace bez opakování 2