Kombinační čísla

Řešení příkladu:

Musíme vybrat tým o \(5\) členech, kde jsou přesně \(3\) chlapci a \(2\) dívky.

Počet způsobů, jak vybrat \(3\) chlapce z \(8\), je \( \frac{8!}{3! \times 5!} \).

Počet způsobů, jak vybrat \(2\) dívky z \(7\), je \( \frac{7!}{2! \times 5!} \).

Celkový počet možností je součin těchto dvou hodnot:

\[ \frac{8!}{3! \times 5!} \times \frac{7!}{2! \times 5!} \]

Vypočítáme jednotlivě:

\( \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \)

\( \frac{7 \times 6}{2 \times 1} = 21 \)

Celkem tedy:

\( 56 \times 21 = 1176 \)

Odpověď: Existuje \(1176\) různých týmů, které obsahují právě \(3\) chlapce a \(2\) dívky.

Řešení příkladu:

Máme \(6\) studentů a chceme je rozdělit do dvou skupin po \(3\) studentech.

Pořadí skupin nezáleží, ale pořadí studentů ve skupině ano. To znamená, že uvnitř skupiny je důležité pořadí, ale skupiny samy o sobě jsou nerozlišitelné.

Nejprve vybereme první skupinu \(3\) studentů z \(6\), což je \( \frac{6!}{3! \times 3!} \).

Ve vybrané skupině je možné uspořádat studenty \(3!\) způsoby (pořadí ve skupině).

Zbývající \(3\) studenti vytvoří druhou skupinu, kterou také můžeme uspořádat \(3!\) způsoby.

Celkový počet uspořádání je:

\[ \frac{6!}{3! \times 3!} \times 3! \times 3! = 20 \times 6 \times 6 = 720 \]

Protože pořadí skupin nezáleží, musíme ještě vydělit počtem jejich permutací (\(2!\)), abychom neopakovali stejné rozdělení v jiném pořadí skupin.

Tedy konečný počet je:

\( \frac{720}{2} = 360 \)

Odpověď: Existuje \(360\) různých způsobů, jak uspořádat \(6\) studentů do dvou \(3\)členných skupin s pořadím ve skupinách.

Řešení příkladu:

Ze \(12\) knih chceme vybrat \(5\). \(3\) konkrétní knihy musí být vybrány vždy.

Nejprve vybereme těchto povinných \(3\) knih (toto je už pevně dané, počet možností = 1).

Zbývá vybrat ještě \(5 – 3 = 2\) knihy z ostatních \(12 – 3 = 9\) knih.

Počet způsobů, jak vybrat těchto \(2\) knih z \(9\), je:

\( \frac{9!}{2! \times 7!} = \frac{9 \times 8}{2 \times 1} = 36 \)

Odpověď: Existuje \(36\) různých způsobů, jak vybrat \(5\) knih včetně těch \(3\) konkrétních.

Řešení příkladu:

Slovo „MATEMATIKA“ má celkem \(10\) písmen.

Počítáme počet uspořádání písmen, přičemž některá se opakují:

• M se vyskytuje \(2\times\)
• A se vyskytuje \(3\times\)
• T se vyskytuje \(2\times\)
• E, I, K se vyskytují \(1\times\)

Celkový počet permutací je:

\[ \frac{10!}{2! \times 3! \times 2!} = \frac{3628800}{2 \times 6 \times 2} = \frac{3628800}{24} = 151200 \]

Odpověď: Slovo „MATEMATIKA“ lze uspořádat \(151200\) různými způsoby.

Řešení příkladu:

Komise má \(4\) členy a musí obsahovat alespoň \(2\) ženy.

Možné případy podle počtu žen v komisi jsou \(2\), \(3\) nebo \(4\) ženy.

Počet výběrů:

Pro \(2\) ženy:

\( \frac{6!}{2! \times 4!} \times \frac{10!}{2! \times 8!} \)

Pro \(3\) ženy:

\( \frac{6!}{3! \times 3!} \times \frac{10!}{1! \times 9!} \)

Pro \(4\) ženy:

\( \frac{6!}{4! \times 2!} \times \frac{10!}{0! \times 10!} \)

Vypočítáme jednotlivě:

\( \frac{6 \times 5}{2 \times 1} = 15, \quad \frac{10 \times 9}{2 \times 1} = 45 \quad \Rightarrow 15 \times 45 = 675 \)

\( \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20, \quad 10 \quad \Rightarrow 20 \times 10 = 200 \)

\( \frac{6 \times 5 \times 4 \times 3}{4 \times 3 \times 2 \times 1} = 15, \quad 1 \quad \Rightarrow 15 \times 1 = 15 \)

Celkem tedy:

\( 675 + 200 + 15 = 890 \)

Odpověď: Komisi lze vybrat \(890\) různými způsoby.

Řešení příkladu:

Volíme \(3\) různé funkce z \(9\) členů, přičemž pořadí je důležité (každá funkce je jiná).

Počet způsobů, jak vybrat a uspořádat \(3\) členy z \(9\), je počet variací:

\[ \frac{9!}{(9-3)!} = \frac{9!}{6!} = 9 \times 8 \times 7 = 504 \]

Odpověď: Existuje \(504\) různých způsobů, jak vybrat a uspořádat prezidenta, místopředsedu a tajemníka.

Řešení příkladu:

Nejprve spočítáme celkový počet způsobů, jak vybrat \(4\) studenty z \(15\) bez omezení:

\( \frac{15!}{4! \times 11!} = \frac{15 \times 14 \times 13 \times 12}{4 \times 3 \times 2 \times 1} = 1365 \)

Poté spočítáme počet výběrů, kdy jsou oba konkrétní studenti spolu ve výboru.

Pokud jsou oba vybráni, zbývá vybrat ještě \(2\) ze zbylých \(13\) studentů:

\( \frac{13!}{2! \times 11!} = \frac{13 \times 12}{2 \times 1} = 78 \)

Počet výběrů, které nesplňují podmínku, je \(78\).

Počet výběrů splňujících podmínku je tedy:

\( 1365 – 78 = 1287 \)

Odpověď: Existuje \(1287\) způsobů, jak vybrat \(4\)členný výbor bez současného výskytu obou konkrétních studentů.

Řešení příkladu:

Celkový počet výběrů \(3\) knih z \(10\) je:

\( \frac{10!}{3! \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120 \)

Počet výběrů bez konkrétní knihy (tedy zbylých \(9\) knih) je:

\( \frac{9!}{3! \times 6!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84 \)

Počet výběrů obsahujících alespoň jednu konkrétní knihu je:

\( 120 – 84 = 36 \)

Odpověď: Existuje \(36\) takových výběrů.

Řešení příkladu:

Počet kombinací \(5\) prvků z \(12\) je dán vzorcem:

\[ \frac{12!}{5! \times 7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = \frac{95040}{120} = 792 \]

Odpověď: Existuje \(792\) různých pětičlenných podmnožin množiny o \(12\) prvcích.

Řešení příkladu:

Jeden konkrétní student musí být vždy ve družstvu, takže ho považujeme za vybraného.

Zbývá vybrat z ostatních \(14 – 1 = 13\) studentů dalších \(6 – 1 = 5\) členů družstva.

Počet způsobů výběru je tedy:

\[ \frac{13!}{5! \times 8!} = \frac{13 \times 12 \times 11 \times 10 \times 9}{5 \times 4 \times 3 \times 2 \times 1} = \frac{154440}{120} = 1287 \]

Odpověď: Existuje \(1287\) družstev obsahujících daného studenta.

Řešení příkladu:

Nejprve vybereme \(2\) dívky z \(5\):

\( \frac{5!}{2! \times 3!} = \frac{5 \times 4}{2 \times 1} = 10 \)

Zbylých \(3\) členy týmu vybereme z \(9\) chlapců:

\( \frac{9!}{3! \times 6!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84 \)

Celkový počet týmů je:

\( 10 \times 84 = 840 \)

Odpověď: Takových týmů lze vytvořit \(840\).

Řešení příkladu:

Uvažujeme dvě možnosti:

1) Obě osoby jsou ve výboru:

Vybereme ještě \(4\) osoby z \(8\) zbývajících:

\( \frac{8!}{4! \times 4!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70 \)

2) Ani jedna z nich není ve výboru:

Vybereme \(6\) osob z \(8\):

\( \frac{8!}{6! \times 2!} = \frac{8 \times 7}{2 \times 1} = 28 \)

Celkový počet výborů:

\( 70 + 28 = 98 \)

Odpověď: Výborů je možné sestavit \(98\).

Řešení příkladu:

Pro výběr \(4\) kuliček bez po sobě jdoucích čísel převedeme problém na výběr zmenšené množiny.

Zavádíme substituci: mezi každými dvěma vybranými musí být alespoň \(1\) nevybraná, čímž snížíme efektivní velikost množiny.

Počet výběrů je dán kombinací:

\( \frac{9!}{4! \times 5!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126 \)

Odpověď: Požadovaný počet výběrů je \(126\).

Řešení příkladu:

Počítáme zvlášť případy:

\(3\) ženy a \(2\) muži: \( \frac{6!}{3! \times 3!} \times \frac{6!}{2! \times 4!} = 20 \times 15 = 300 \)

\(4\) ženy a \(1\) muž: \( \frac{6!}{4! \times 2!} \times \frac{6!}{1! \times 5!} = 15 \times 6 = 90 \)

\(5\) žen: \( \frac{6!}{5! \times 1!} = 6 \)

Celkem: \( 300 + 90 + 6 = 396 \)

Odpověď: Takových týmů lze vytvořit \(396\).

Řešení příkladu:

Bez ohledu na pořadí znamená, že výběr jedné skupiny určuje i druhou.

Počet výběrů jedné skupiny (druhá je tím daná):

\( \frac{8!}{4! \times 4!} = 70 \)

Protože pořadí skupin nehraje roli, dělíme dvěma:

\( \frac{70}{2} = 35 \)

Odpověď: Takových rozdělení je \(35\).

Řešení příkladu:

Pro každý výběr \(6\) písmen bez sousedů potřebujeme mezi každými dvěma vybranými alespoň \(1\) nevybraný prvek.

Celkem máme \(26\) písmen, potřebujeme vybrat \(6\) nesousedících, což je kombinace:

\( \frac{21!}{6! \times 15!} = \frac{21 \times 20 \times 19 \times 18 \times 17 \times 16}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 54264 \)

Odpověď: Takových výběrů existuje \(54264\).

Řešení příkladu:

Nejprve vybereme předsedu: \(20\) možností.

Zbývá \(19\) žáků z různých tříd. Předpokládejme, že máme \(3\) různé třídy po \(7\), \(6\) a \(6\) žácích.

Vybereme po jednom členu z každé třídy: \(7 \times 6 \times 6 = 252\)

Celkový počet možností: \(20 \times 252 = 5040\)

Odpověď: Výbor lze sestavit \(5040\) způsoby.

Řešení příkladu:

Nejprve vybereme \(10\) prvků, které tvoří obě podmnožiny (dohromady):

\( \frac{16!}{10! \times 6!} = 8008 \)

Z těchto \(10\) vybereme jednu \(5\)člennou podmnožinu, druhá je dána:

\( \frac{10!}{5! \times 5!} = 252 \)

Každý pár podmnožin je započítán dvakrát, takže:

\( \frac{8008 \times 252}{2} = 1005120 \)

Odpověď: Existuje \(1\,005\,120\) takových dvojic.

Řešení příkladu:

Počet kombinací \(3\) písmen z \(6\):

\( \frac{6!}{3! \times 3!} = 20 \)

Odpověď: Lze sestavit \(20\) různých řetězců bez ohledu na pořadí.

Řešení příkladu:

Nejprve rozmístíme ženy: \(4! = 24\)

Mezi nimi vznikne \(5\) pozic pro muže (mezi ženami a na krajích).

Vybereme \(3\) pozice z \(5\) pro muže: \( \frac{5!}{3! \times 2!} = 10 \)

Muže v těchto pozicích můžeme uspořádat: \(3! = 6\)

Celkem: \(24 \times 10 \times 6 = 1440\)

Odpověď: Existuje \(1440\) takových uspořádání.

Řešení příkladu:

Počet způsobů, jak rozdělit \(10\) lidí do \(5\) dvojic, je dán vzorcem:

\( \frac{10!}{(2!)^{5} \times 5!} = \frac{3628800}{32 \times 120} = 945 \)

Odpověď: Lze je rozdělit \(945\) způsoby.

Řešení příkladu:

Celkový počet výborů bez omezení:

\( \frac{12!}{4! \times 8!} = 495 \)

Počet výborů bez žen (jen muži):

\( \frac{7!}{4! \times 3!} = 35 \)

Počet výborů s alespoň jednou ženou:

\( 495 – 35 = 460 \)

Odpověď: \(460\) výborů obsahuje alespoň jednu ženu.

Řešení příkladu:

Celkový počet trojic:

\( \frac{15!}{3! \times 12!} = 455 \)

Počet trojic obsahujících oba zakázané studenty:

Vybereme \(1\) dalšího z \(13\): \( \frac{13!}{1! \times 12!} = 13 \)

Počet vyhovujících kombinací:

\( 455 – 13 = 442 \)

Odpověď: \(442\) kombinací splňuje podmínku.

Řešení příkladu:

Musíme vybrat \(4\) číslice z \(7\):

\( \frac{7!}{4! \times 3!} = 35 \)

Každá čtveřice dává právě jedno vzestupné číslo.

Odpověď: Takových čísel je \(35\).

Řešení příkladu:

Vybereme \(2\) společné osoby: \( \frac{12!}{2! \times 10!} = 66 \)

Zbývá \(3\) osoby do první skupiny z \(10\): \( \frac{10!}{3! \times 7!} = 120 \)

Zbývá \(3\) osoby do druhé skupiny z \(7\) (aby byly odlišné): \( \frac{7!}{3! \times 4!} = 35 \)

Celkem: \( 66 \times 120 \times 35 = 277200 \)

Odpověď: Existuje \(277200\) takových dvojic skupin.

Řešení příkladu:

Nejprve rozmístíme ženy: \(5! = 120\)

Mezi ženami je \(4\) mezery pro muže (mezi a na krajích). Vybereme \(3\) z nich:

\(\frac{4!}{3! \times 1!} = 4\)

Muže lze uspořádat: \(3! = 6\)

Celkem: \(120 \times 4 \times 6 = 2880\)

Odpověď: \(2880\) možných uspořádání.

Řešení příkladu:

Výběr \(3\) knih: \(\frac{6!}{3! \times 3!} = 20\)

Počet uspořádání těchto knih: \(3! = 6\)

Celkem: \(20 \times 6 = 120\)

Odpověď: \(120\) způsobů umístění.

Řešení příkladu:

Z \(4\) studentů vybíráme \(6\) různých pro ceny — nelze, protože \(6 > 4\).

Každý může dostat max jednu cenu \Rightarrow pouze \(4\) ceny lze rozdat.

Počet možností vybrat \(4\) ceny z \(6\): \(\frac{6!}{4! \times 2!} = 15\)

Počet přiřazení \(4\) cen \(4\) studentům: \(4! = 24\)

Celkem: \(15 \times 24 = 360\)

Odpověď: \(360\) možných rozdělení.

Řešení příkladu:

Musíme vybrat \(6\) číslic z \(8\):

\(\frac{8!}{6! \times 2!} = 28\)

Každý výběr dává právě jedno klesající číslo.

Odpověď: Existuje \(28\) takových čísel.

Řešení příkladu:

Výběr \(3\) osob z \(10\): \(\frac{10!}{3! \times 7!} = 120\)

Počet uspořádání (funkcí): \(3! = 6\)

Celkem: \(120 \times 6 = 720\)

Odpověď: Existuje \(720\) možností rozdělení funkcí.

Řešení příkladu:

Každá podmnožina o pěti prvcích z osmi je kombinací \(5\) prvků z \(8\).

Počet těchto kombinací určíme pomocí vzorce:

\( C(8,5) = \frac{8!}{5! \cdot (8 – 5)!} = \frac{8!}{5! \cdot 3!} \)

\( = \frac{40320}{120 \cdot 6} = \frac{40320}{720} = 56 \)

Odpověď: Lze vytvořit \(56\) různých podmnožin o pěti prvcích.

Řešení příkladu:

Celkový počet trojic bez omezení:

\( C(12,3) = \frac{12!}{3! \cdot 9!} = \frac{1320}{6} = 220 \)

Počet trojic, které obsahují oba zakázané studenty:

Zbývá vybrat \(1\) dalšího z \(10\) studentů: \( C(10,1) = 10 \)

Počet přípustných trojic: \( 220 – 10 = 210 \)

Odpověď: \(210\) trojic splňuje podmínku.

Řešení příkladu:

Dva konkrétní lidé tvoří pevnou dvojici, kterou musíme zahrnout.

Zbývá vybrat \(2\) další z \(8\) ostatních osob:

\( C(8,2) = \frac{8!}{2! \cdot 6!} = \frac{40320}{2 \cdot 720} = \frac{40320}{1440} = 28 \)

Odpověď: Existuje \(28\) takových porot.

Řešení příkladu:

Nejprve vybereme \(3\) osoby ze \(9\):

\( C(9,3) = \frac{9!}{3! \cdot 6!} = 84 \)

Každé této trojici můžeme přiřadit jednoho jako vedoucího: \(3\) možnosti

Celkem: \( 84 \cdot 3 = 252 \)

Odpověď: Existuje \(252\) různých skupin s vedoucím.

Řešení příkladu:

Výběr \(2\) chlapců z \(5\): \( C(5,2) = \frac{5!}{2! \cdot 3!} = 10 \)

Výběr \(3\) dívek z \(6\): \( C(6,3) = \frac{6!}{3! \cdot 3!} = 20 \)

Celkem: \( 10 \cdot 20 = 200 \)

Odpověď: Lze vytvořit \(200\) různých smíšených skupin.

Řešení příkladu:

Slovo má \( 9 \) písmen, všechna jsou různá.

Počet všech možných permutací je:

\( 9! = 362880 \)

Odpověď: Lze vytvořit \( 362880 \) různých slov.

Řešení příkladu:

Nejprve určíme celkový počet výborů bez omezení:

\( \binom{7}{4} = 35 \)

Počet výborů, které obsahují oba zakázané členy:

Pokud jsou oba v výboru, vybíráme ještě \( 2 \) členy z \( 5 \) zbývajících:

\( \binom{5}{2} = 10 \)

Počet vyhovujících výborů je tedy:

\( 35 – 10 = 25 \)

Odpověď: Existuje \( 25 \) výborů splňujících podmínku.

Řešení příkladu:

Předpokládejme, že počty karet jednotlivých barev jsou: červená \( 10 \), zelená \( 10 \), modrá \( 12 \).

Nejprve vybereme \( 1 \) kartu z každé barvy:

\( \binom{10}{1} \cdot \binom{10}{1} \cdot \binom{12}{1} = 10 \cdot 10 \cdot 12 = 1200 \)

Pořadí těchto tří karet může být libovolné:

\( 3! = 6 \)

Celkem tedy:

\( 1200 \cdot 6 = 7200 \)

Odpověď: Existuje \( 7200 \) možností výběru tří karet různých barev.

Řešení příkladu:

Označme dva konkrétní studenty jako jeden celek – „blok“. Spolu s ostatními třemi studenty máme celkem \( 4 \) objekty k uspořádání.

Počet uspořádání těchto \( 4 \) objektů je:

\( 4! = 24 \)

Uvnitř bloku mohou být tito dva studenti ve dvou různých pořadích:

\( 2! = 2 \)

Celkový počet uspořádání je tedy:

\( 24 \cdot 2 = 48 \)

Odpověď: Existuje \( 48 \) různých pořadí.

Řešení příkladu:

Celkový počet dvojic bez omezení je:

\( \binom{8}{2} = \frac{8!}{2! \cdot 6!} = 28 \)

Zakázaná dvojice představuje \( 1 \) možnost.

Počet přípustných dvojic je tedy:

\( 28 – 1 = 27 \)

Odpověď: Existuje \( 27 \) dvojic splňujících podmínku.

Řešení příkladu:

Tato rovnost je známa jako Pascalova identita.

Dosadíme pomocí vzorce pro kombinační číslo:

\( C(n, k) + C(n, k – 1) = \frac{n!}{k! \cdot (n – k)!} + \frac{n!}{(k – 1)! \cdot (n – k + 1)!} \)

Společným jmenovatelem je \( k! \cdot (n – k + 1)! \)

Po úpravách dostáváme: \( \Rightarrow \frac{(n + 1)!}{k! \cdot (n + 1 – k)!} = C(n + 1, k) \)

Rovnost tedy platí.

Řešení příkladu:

Pro kombinace s opakováním platí vzorec:

\( C(n + k – 1, k) \), kde \( n = 6 \), \( k = 4 \)

\( C(6 + 4 – 1, 4) = C(9, 4) = \frac{9!}{4! \cdot 5!} = 126 \)

Odpověď: Existuje \( 126 \) možností výběru.

Řešení příkladu:

Každý výsledek je kombinací s opakováním \( 4 \) čísel z \( 6 \).

\( C(6 + 4 – 1, 4) = C(9, 4) = 126 \)

Odpověď: \( 126 \) nerozlišitelných výsledků.

Řešení příkladu:

Každý prvek množiny má dvě možnosti: buď je, nebo není v podmnožině.

Počet všech podmnožin množiny o \( n \) prvcích je \( 2^n \).

Součet \( C(n, 0) + C(n, 1) + \ldots + C(n, n) \) odpovídá počtu všech podmnožin.

\( \Rightarrow \sum_{k = 0}^{n} C(n, k) = 2^n \)

Rovnost je dokázána.

Řešení příkladu:

Sudé číslice: \( 2 \), \( 4 \), \( 6 \), \( 8 \) → \( 4 \) možnosti na poslední cifru.

Po výběru sudé cifry zůstává \( 8 \) číslic pro první \( 4 \) pozice.

Počet možností: \( 4 \cdot P(8, 4) = 4 \cdot \frac{8!}{(8 – 4)!} = 4 \cdot 1680 = 6720 \)

Odpověď: \( 6720 \) různých čísel.

Řešení příkladu:

Binomická identita: počet kombinací \( n \) prvků z množiny o \( 2n \) prvcích (rozdělené na dvě poloviny).

Vybereme \( k \) prvků z první a \( n-k \) z druhé poloviny:

\( \sum_{k=0}^{n} C(n,k) \cdot C(n,n-k) = \sum_{k=0}^{n} C(n,k)^2 = C(2n,n) \)

Identita je dokázána.

Řešení příkladu:

Nejprve vybereme \( 2 \) jiné číslice než \( 7 \): \( C(9,2) = 36 \)

Umístění tří \( 7 \) v pětici: \( C(5,3) = 10 \)

Zbývající \( 2 \) pozice se zaplní dvěma různými číslicemi na \( 2 \) místa: \( 2! = 2 \)

Celkem: \( 36 \cdot 10 \cdot 2 = 720 \)

Odpověď: \( 720 \) možností

Řešení příkladu:

Počet výběrů první skupiny: \( C(10,5) = 252 \)

Druhá skupina je určena automaticky → výsledek dělit \( 2 \):

\( \Rightarrow \frac{252}{2} = 126 \)

Odpověď: \( 126 \) různých rozdělení

Řešení příkladu:

Celkem možností: \( C(12,4) = 495 \)

Počet výběrů bez žádného člena ze \( 4 \)-členné skupiny: \( C(8,4) = 70 \)

\( \Rightarrow 495 – 70 = 425 \)

Odpověď: \( 425 \) skupin obsahuje alespoň jednoho člena dané podskupiny.

Řešení příkladu:

Číslo musí začínat číslicí \( 1 \)–\( 4 \) (menší než \( 5 \)): \( 4 \) možnosti

Další tři číslice z \( 6 \) zbývajících: \( P(6,3) = 120 \)

Celkem: \( 4 \cdot 120 = 480 \)

Odpověď: \( 480 \) různých čtyřciferných čísel

Řešení příkladu:

Levou stranu lze interpretovat jako součet všech vážených počtů výběrů s ohledem na pozici jednoho konkrétního prvku.

Každý prvek z \( n \) se v polovině podmnožin vyskytuje: \( \Rightarrow \frac{2^n}{2} = 2^{n-1} \)

Proto každý z \( n \) prvků se vyskytuje v \( 2^{n-1} \) podmnožinách.

Celkem: \( n \cdot 2^{n-1} \)

Rovnost je dokázána.

Řešení příkladu:

Jedná se o binomickou expanzi \( (1 – 1)^n = 0 \)

Rozepíšeme pomocí binomické věty:

\( (1 – 1)^n = \sum_{k=0}^{n} C(n, k) \cdot (-1)^k = 0 \)

Rovnost platí pro všechna \( n \geq 1 \)

Řešení příkladu:

Celkem čísel bez opakování: \( P(9, 5) = \frac{9!}{(9-5)!} = 15120 \)

Přibližně polovina z nich má sudý ciferný součet.

Odpověď: \( \frac{15120}{2} = 7560 \)

Řešení příkladu:

Levá strana: počet výběrů \( r \) prvků z \( n \).

Pravá strana: vybereme konkrétní prvek (např. prvního), ten je součástí výběru (proto \( r \) možností, kde může být), zbývající \( r-1 \) z \( n-1 \).

Počet možností: \( r \cdot C(n-1, r-1) \).

Po úpravě rovnosti: \( \Rightarrow C(n, r) = \frac{n}{r} \cdot C(n-1, r-1) \).

Řešení příkladu:

Slovo má \(9\) písmen, všechna různá

Počet permutací: \(9! = 362880\)

Odpověď: \(362880\) různých slov

Řešení příkladu:

Počet lichých čísel: \(10\), sudých také \(10\)

Vybereme \(1\) liché: \( C(10,1) = 10 \)

Vybereme \(3\) sudá: \( C(10,3) = 120 \)

Celkem: \( 10 \cdot 120 = 1200 \)

Odpověď: \(1200\) kombinací

Řešení příkladu:

Použijeme vzorec pro kombinace s opakováním:

\( C(n + k – 1, k) \), kde \( n = 3, k = 5 \)

\( C(3 + 5 – 1, 5) = C(7,5) = 21 \)

Odpověď: \(21\) kombinací

Řešení příkladu:

Počet možností: \( C(8,3) = 56 \)

Skupiny jsou různě veliké → neřešíme přeznačení

Odpověď: \(56\) způsobů

Řešení příkladu:

Celkový počet výběrů: \( C(10,3) = 120 \)

Zakázaná dvojice: \(2\) osoby, doplníme \(1\) osobou z jiných \(8\): \( C(8,1) = 8 \)

Odečteme zakázané: \( 120 – 8 = 112 \)

Odpověď: \(112\) způsobů

Řešení příkladu:

Tato identita je známa jako Chu-Vandermondeova identita

Indukční důkaz nebo kombinatorická interpretace: počítáme počet způsobů výběru \(n\) objektů s „růstem“ podmínek

Dokázat lze rozpisem a úpravou kombinací

Platí: \( \Rightarrow \sum_{r=0}^{n} C(m + r, r) = C(m + n + 1, n) \)

Řešení příkladu:

Počet podmnožin o lichém počtu prvků je součet kombinací pro liché velikosti:

\( C(10,1) + C(10,3) + C(10,5) + C(10,7) + C(10,9) \)

\( = 10 + 120 + 252 + 120 + 10 = 512 \)

Celkový počet všech podmnožin: \( 2^{10} = 1024 \), polovina z nich má lichý počet prvků.

Odpověď: \(512\) způsobů

Řešení příkladu:

Použijeme odhad založený na Stirlingově vzorci: \( n! \approx \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \)

Po dosazení a zjednodušení dostaneme asymptotické chování:

\( C(2n, n) \approx \frac{4^n}{\sqrt{\pi n}} \Rightarrow C(2n, n) \geq \frac{4^n}{2\sqrt{n}} \)

Nerovnost je platná od určité velikosti \( n \), pro přirozená čísla ověřit indukcí nebo konkrétními hodnotami.

Řešení příkladu:

Vybereme \(2\) písmena ze \(4\): \( C(4,2) = 6 \)

Počet všech řetězců délky \(6\) ze \(2\) písmen: \( 2^6 = 64 \)

Odečteme ty, které obsahují jen \(1\) druh: \( 2 \cdot 1 = 2 \)

Pro každou dvojici máme \( 64 – 2 = 62 \) možností

Celkem: \( 6 \cdot 62 = 372 \)

Řešení příkladu:

Levou stranu lze interpretovat jako výběr dvou nezávislých množin o velikosti \( n \)

Pro každé \( k \): vybereme \( k \) prvků z první a \( k \) z druhé množiny nezávisle

Suma přes všechny \( k \): \( \sum_{k=0}^n C(n,k)^2 = C(2n,n) \)

Jde o důsledek kombinatorického rozvoje \( (1 + x)^n \cdot (1 + x)^n = (1 + x)^{2n} \)

Řešení příkladu:

Bez ohledu na pořadí: \( \frac{C(10,5)}{2} = \frac{252}{2} = 126 \)

Každé rozdělení je symetrické – skupiny nejsou odlišitelné

Řešení příkladu:

Přirozená čísla → převedeme substitucí \( x‘ = x-1 \), atd.

Nová rovnice: \( x‘ + y‘ + z‘ = 7 \), \( x‘, y‘, z‘ \geq 0 \)

Počet řešení: \( C(7 + 3 – 1, 2) = C(9,2) = 36 \)

Řešení příkladu:

Podmínka: \( x_1 + x_2 + x_3 + x_4 = 8 \), \( x_i \geq 1 \)

Substituce: \( x_i‘ = x_i – 1 \Rightarrow x_1’+x_2’+x_3’+x_4′ = 4 \)

Řešení: \( C(4 + 4 – 1, 3) = C(7,3) = 35 \)

Řešení příkladu:

Výběr 4 číslic ze 6: \( C(6,4) = 15 \)

Každý výběr lze uspořádat: \( 4! = 24 \)

Celkem: \( 15 \cdot 24 = 360 \)

Řešení příkladu:

Celkem: \( C(12,7) = 792 \)

Pouze lichá čísla: z \(6\) lichých → \( C(6,7) = 0 \)

Platí: všechny podmnožiny obsahují alespoň jedno sudé číslo

Odpověď: \(792\)

Řešení příkladu:

Indukce nebo kombinatorická interpretace: počítáme počet výběrů \( r+1 \) prvků z \( n+1 \) prvků s posledním prvkem na pozici \( k+1 \)

Suma přes všechna \( k \) od \( r \) do \( n \): \( \sum_{k=r}^{n} C(k, r) = C(n+1, r+1) \)

Řešení příkladu:

Základ indukce: Pro \( n = 1 \) platí \( (-1)^0 C(1,0) + (-1)^1 C(1,1) = 1 – 1 = 0 \)

Předpoklad: Platí pro \( n \)

Indukční krok: Pro \( n+1 \):

\( \sum_{k=0}^{n+1} (-1)^k C(n+1,k) = \sum_{k=0}^{n+1} (-1)^k [C(n,k) + C(n,k-1)] \)

Rozdělíme a použijeme posunutí indexů, dostaneme dvě opačné sumy \(\Rightarrow 0\)

Řešení příkladu:

Použijeme substituci: \( x_i‘ = x_i – 2 \Rightarrow x_1′ + x_2′ + x_3′ + x_4′ = 12 \), \( x_i‘ \geq 0 \)

Počet řešení: \( C(12 + 4 – 1, 3) = C(15,3) = 455 \)

Řešení příkladu:

Vyjádříme pomocí binomické věty: \( \sum_{k=0}^{n} C(n,k) \cdot 2^k = (1 + 2)^n = 3^n \)

Odpověď: \( 3^n \)

Řešení příkladu:

Kombinatorický výklad: máme \( n+1 \) prvků a vybíráme \( r \) – jeden prvek je speciální

Případ 1: speciální není vybrán → vybíráme \( r \) z \( n \) → \( C(n, r) \)

Případ 2: speciální je vybrán → zbývá vybrat \( r-1 \) z \( n \) → \( C(n, r-1) \)

Součet možností: \( C(n, r) + C(n, r-1) = C(n+1, r) \)

Řešení příkladu:

Výběr \(5\) číslic z \(10\): \( C(10,5) = 252 \)

Každou pětici lze uspořádat: \( 5! = 120 \)

Musíme odečíst případy, kdy číslo začíná nulou

Počet pětic obsahujících \(0\): vybereme \(4\) číslice z \(9\) zbývajících → \( C(9,4) = 126 \)

V těchto případech \(0\) může být na první pozici: ve čtvrtině uspořádání → \( 126 \cdot 4! = 3024 \), 1/5 z nich začíná \(0\) → \( \frac{3024}{5} = 604.8 \approx 605 \)

Celkem čísel: \( 252 \cdot 120 – 605 = 30235 \)

Řešení příkladu:

Výraz je rovný \( (1 – 1)^n = 0 \) podle binomické věty

Odpověď: \(0\)

Řešení příkladu:

Všechny trojice: \( C(10,3) = 120 \)

Trojice bez studenta A: \( C(9,3) = 84 \)

Trojice s A: \( 120 – 84 = 36 \)

Řešení příkladu:

Použijeme derivaci binomické věty: \( (1+x)^n \Rightarrow \frac{d}{dx}(1+x)^n = n(1+x)^{n-1} \)

Po dosazení \( x = 1 \): \( \sum_{k=1}^{n} k \cdot C(n,k) = n \cdot 2^{n-1} \)

Řešení příkladu:

Dívky: \( C(7,4) = 35 \)

Chlapci: \( C(5,3) = 10 \)

Celkem: \( 35 \cdot 10 = 350 \)

Řešení příkladu:

Jedná se o očekávaný počet vybraných prvků ze všech podmnožin

Matematický důkaz opět pomocí derivace binomické věty

\( \sum_{k=0}^{n} k \cdot C(n,k) = n \cdot 2^{n-1} \)

Řešení příkladu:

Existuje známý vzorec: \( \sum_{k=1}^{n} k^2 \cdot C(n,k) = n(n+1) \cdot 2^{n-2} \)

Ověření pomocí derivace binomické věty je možné, ale náročné. Doporučujeme spíše využít jako známý vzorec.

Řešení příkladu:

Rozvoj: \( \sum_{k=0}^{5} C(5,k) \cdot (2x)^{5-k} \cdot (-3)^k \)

Postupně:

\( C(5,0)(2x)^5(-3)^0 = 32x^5 \)

\( C(5,1)(2x)^4(-3)^1 = -240x^4 \)

\( C(5,2)(2x)^3(-3)^2 = 720x^3 \)

\( C(5,3)(2x)^2(-3)^3 = -1080x^2 \)

\( C(5,4)(2x)^1(-3)^4 = 810x \)

\( C(5,5)(2x)^0(-3)^5 = -243 \)

Výsledný rozvoj: \( 32x^5 – 240x^4 + 720x^3 – 1080x^2 + 810x – 243 \)

Řešení příkladu:

Počet všech podmnožin: \( 2^n \)

Každou podmnožinu s lichým počtem prvků lze spárovat s podmnožinou se sudým počtem prvků – výměnou jednoho prvku

Z toho plyne, že počet podmnožin s lichým počtem je \( \frac{2^n}{2} = 2^{n-1} \)

Řešení příkladu:

Kombinační čísla jsou symetrická: \( C(n,k) = C(n,n-k) \)

Maximum nastává pro \( k = \left\lfloor \frac{n}{2} \right\rfloor \) nebo \( k = \left\lceil \frac{n}{2} \right\rceil \)

Například pro \( n = 10 \): největší hodnota je \( C(10,5) = 252 \)

Řešení příkladu:

Celkem trojprvkových podmnožin: \( C(7,3) = 35 \)

Počet trojic, které neobsahují prvek \( a \): \( C(6,3) = 20 \)

Tedy hledaný počet: \( 35 – 20 = 15 \)

Řešení příkladu:

Kombinatorický důkaz: představme si výběr \( n \) prvků z množiny \( 2n \) prvků, rozdělené na dvě množiny po \( n \) prvcích

Každý výběr může obsahovat \( k \) prvků z první množiny a \( n-k \) z druhé → \( C(n,k) \cdot C(n,n-k) = C(n,k)^2 \)

Součet přes všechna \( k \): \( \sum_{k=0}^{n} C(n,k)^2 = C(2n,n) \)

Řešení příkladu:

Pomocí Lucasovy věty lze určit, zda je \( C(n,k) \) liché

Použijeme binární reprezentaci čísel a zjistíme, pro kolik \( k \) platí, že bitově \( k_i \leq n_i \)

Pro \( n = 11 \): binárně \( 1011 \), takže počet lichých hodnot je \( 2^r \), kde \( r \) je počet jedniček v binárním zápise 11 → 3 jedničky → \( 2^3 = 8 \)

Řešení příkladu:

Substituce: \( x_i‘ = x_i – 1 \Rightarrow x_1′ + \dots + x_5′ = 10 \), \( x_i‘ \geq 0 \)

Počet řešení: \( C(10 + 5 – 1, 4) = C(14,4) = 1001\)

Řešení příkladu:

Musíme vybrat \(4\) různé číslice z \(9\): \( C(9,4) = 126 \)

Každou čtveřici lze uspořádat: \( 4! = 24 \)

Celkem: \( 126 \cdot 24 = 3024 \)

Řešení příkladu:

Celkem možností bez omezení: \( C(20,4) = 4845 \)

Počet případů, kdy jsou obě osoby ve výboru: \( C(18,2) = 153 \)

Hledaný počet: \( 4845 – 153 = 4692 \)

Řešení příkladu:

Využijeme fakt, že \( \sum_{k=1}^{n} k \cdot C(n,k) = n \cdot 2^{n-1} \)

Dokazujeme kombinatoricky:

Každý z \( n \) prvků může být přítomen v polovině všech podmnožin množiny \( n \) prvků → každá položka se vyskytne ve \( 2^{n-1} \) podmnožinách

Celkový počet výskytů prvků ve všech podmnožinách: \( n \cdot 2^{n-1} \)

Na druhé straně: každý člen \( k \cdot C(n,k) \) reprezentuje přítomnost \( k \) prvků ve všech \( k \)-prvkových podmnožinách → celkový součet je rovný

Řešení příkladu:

Každá řádka musí mít dvě jedničky → počet možností pro jednu řádku: \( C(3,2) = 3 \)

Každá ze tří řádek je nezávislá → celkově: \( 3^3 = 27 \) takových matic

Řešení příkladu:

Počet takových permutací je označen \( c(n,k) \) – Stirlingova čísla prvního druhu

Výpočet rekurzí: \( c(n,k) = (n-1) \cdot c(n-1,k) + c(n-1,k-1) \)

Příklad: \( c(4,2) = (3) \cdot c(3,2) + c(3,1) = 3 \cdot 3 + 2 = 11 \)

Řešení příkladu:

Počet takových rozdělení je dán Stirlingovým číslem druhého druhu: \( S(10,3) \)

Pro výpočet použijeme rekurzi nebo tabulku, platí: \( S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1) \)

Z tabulky: \( S(10,3) = 9330 \)

Řešení příkladu:

Využijeme rozklad: \( (1 + 1)^n = 2^n \) a \( (1 – 1)^n = 0 \)

Součet na sudých pozicích: \( C(n,0) + C(n,2) + \dots \)

Součet na lichých pozicích: \( C(n,1) + C(n,3) + \dots \)

Z \( (1 + 1)^n + (1 – 1)^n = 2^n + 0 = 2 \cdot \text{sudé pozice} \Rightarrow \text{sudé pozice} = 2^{n-1} \)

Řešení příkladu:

Čísla \(< 1000\) mají \(1\) až \(3\) cifry

Jednociferná: pouze \(7 → 1\) možnost

Dvouciferná: pozice \(7\) může být na prvním nebo druhém místě → \( 1 \cdot 8 = 8 \) možností (vždy vynecháme 7 na jiné pozici)

Tříciferná: \(3\) pozice, jednu zvolíme pro \(7\): \( C(3,1) = 3 \), zbytek vybereme z \(0–9\) bez \(7\): \(8\) nebo \(9\) možností → dohromady \( 3 \cdot 9 \cdot 9 = 243 \)

Celkem: \( 1 + 8 + 243 = 252 \)

Řešení příkladu:

Pro určení poslední cifry využijeme fakt, že \( C(100,50) \) je sudé a dělitelné \(5\), protože ve faktoriálech se vyskytují mnohé pětky a dvojky

Faktorizace ukáže, že číslo končí na \(0\)

Řešení příkladu:

Vzhledem k symetrii platí \( C(n,k) = C(n,n-k) \), takže výraz je \( C(n,k)^2 \)

Maximum nastává, když \( C(n,k) \) je největší → při \( k = \lfloor \frac{n}{2} \rfloor \)

Hodnota: \( C(n, \lfloor \frac{n}{2} \rfloor)^2 \)

Řešení příkladu:

Vyplývá přímo z binomické věty: \( (1 – 1)^n = 0 \)

Rozvoj: \( \sum_{k=0}^{n} C(n,k) \cdot (-1)^k = 0 \)

Řešení příkladu:

Průměr \(4\) čísel je celé číslo \( \Rightarrow \) součet je dělitelný \(4\)

Vybereme všechny \(4\)-prvkové kombinace bez opakování: \( C(9,4) = 126 \)

Otestujeme, kolik z těchto kombinací má součet dělitelný 4 → zkontrolujeme pomocí programování nebo ručně

Například kombinace \( \{1,2,3,4\} \): součet = \(10\) → ne

Například \( \{2,4,6,8\} \): součet = \(20\) → ano

Celkem je takových kombinací \(48\), každou lze uspořádat: \( 4! = 24 \)

Celkový počet uspořádaných výběrů: \( 48 \cdot 24 = 1152 \)