Kapitola 1 - Kombinatorika
Obsah
Kapitola 1 - Kombinatorika¶
Základní kombinatorická pravidla¶
Definice 1.1 - Kombinatorické pravidlo součinu
Nechť množina \(A_i\) má \(n_i\) prvků pro \(i=1, 2, \ldots, k\). Pak počet všech uspořádaných \(k\)-tic \((a_1 , a_2, \ldots, a_k)\), kde \(a_1 \in A_1, a_2 \in A_2,\ldots, a_k\in A_k\), je roven \(\prod_{i=1}^k n_i\).
Poznámka 1.1 - Alternativní definice kombinatorického pravidla součinu
Počet všech uspořádaných \(k\)-tic, jejichž první člen lze vybrat \(n_1\) způsoby, druhý člen po výběru prvního členu \(n_2\) způsoby atd. až \(k\)-tý člen po výběru všech předchozích členů \(n_k\) způsoby je roven \(n_1 \cdot n_2 \cdot \ldots \cdot n_k\).
Příklad 1.1
Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou.
Zobrazit řešení
Na místě desítek může být libovolná číslice kromě nuly (v takovém případě bychom neobdrželi dvojciferné číslo). Ke každé z těchto devíti možností pro výběr číslice na místě desítek existuje devět možností, jak vybrat číslici pro místo jednotek (tentokrát to může být \(0\) a k tomu jakákoliv z osmi číslic, která se liší od číslice na místě desítek).
Počet uvažovaných čísel je tak \(9 \cdot 9 = 81\).
Definice 1.2 - Kombinatorické pravidlo součtu
Nechť množina \(A_i\) má \(n_i\) prvků pro \(i=1, 2, \ldots, k\) a nechť \(A_i \cap A_j = \emptyset\) pro \(i\neq j\). Pak množina \(\bigcup_{i=1}^k A_i\) má \(\sum_{i=1}^k n_i\) prvků.
Poznámka 1.2 -Alternativní definice Kombinatorického pravidla součtu
Jsou-li \(A_1, A_2, \ldots , A_k\) konečné množiny, které mají po řadě \(p_1, p_2, \ldots, p_k\) prvků a jsou-li každé dvě disjunktní, pak počet prvků množiny \(a_1 \cup A_2 \cup \ldots \cup A_k\) je roven \(p_1 + p_2 + \ldots + p_n\).
Příklad 1.1
Určete počet všech přirozených dvojciferných čísel, v jejichž dekadickém zápisu se každá číslice vyskytuje nejvýše jednou (s pomocí kombinatorického pravidla součtu).
Zobrazit řešení
Všechna přirozená čísla lze rozložit do dvou disjunktních skupin tak, že v první jsou dvojciferná čísla s různými a ve druhé dvojciferná čísla s týmiž číslicemi. Je zřejmé, že všech dvojciferných čísel je \(90\) a dvojciferných čísel s týmiž číslicemi \(9\) (jedná se o čísla \(11, 22, 33, \ldots ,99\)); označíme-li \(p\) hledaný počet dvojciferných čísel s různými číslicemi, platí \(p + 9 = 90\), tedy \( p = 81\).
Příklad 1.2
Je dán čtverec \(ABCD\) a na jeho každé straně \(n\) vnitřních bodů. Určete počet všech trojúhelníků, jejichž vrcholy leží v daných bodech a na různých stranách čtverce \(ABCD\).
Příklad 1.3
Z místa \(A\) do místa \(B\) vedou \(4\) turistické značky, z místa \(B\) do místa \(C\) tři. Určete, kolika způsoby lze vybrat trasu z \(A\) do \(C\) a zpět tak, že z těchto sedmi cest je právě jedna použita dvakrát.
Variace bez opakování¶
Příklad 1.4 - Motivační úloha
Kolika způsoby je možné rozdat červený, modrý a bílý balónek mezi \(4\) děti?
Zobrazit řešení
Ptáme se v podstatě na to, kolika způsoby lze ze \(4\) dětí sestavit uspořádanou trojici (děti si označme \(a, b, c, d\) a nyní například uspořádaná trojice \((a, c, d)\) znamená, že dítě \(a\) dostane červený balónek, dítě \(c\) modrý balónek a dítě \(d\) bílý balónek.
Vypíšeme všechny možnosti:
\((a, b, c), (a, c, b), (a, b, d), (a, d, b), (a, c, d), (a, d, c)\),
\((b, a, c), (b, c, a), (b, a, d), (b, d, a), (b, c, d), (b, d, c)\),
\((c, a, b), (c, b, a), (c, a, d), (c, d, a), (c, b, d), (c, d, b)\),
\((d, a, b), (d, b, a), (d, a, c), (d, c, a), (d, b, c), (d, c, b)\).
Celkem je tedy \(24\) možností. K tomuto výsledku bychom dospěli rovněž užitím kombinatorického pravidla součinu: \(4 \cdot 3 \cdot 2 = 24\).
Definice 1.3
\(k\)-členná variace z \(n\) prvků je uspořádaná \(k\)-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou.
Věta 1.1
Počet všech \(k\)-členných variací z \(n\) prvků značíme \(V(k,n)\), popřípadě \(V_k(n)\) a platí
případně s využitím faktoriálu
Příklad 1.5
K sestavení vlajky, která má být složena ze tří různobarevných vodorovných pruhů, jsou k dispozici látky barvy bílé, červené, modré, zelené a žluté.
a) Určete počet vlajek, které lze z látek těchto barev sestavit.
b) Kolik z nich má modrý pruh?
c) Kolik jich má modrý pruh uprostřed?
d) Kolik jich nemá uprostřed červený pruh?
Příklad 1.6
Určete počet všech nejvíce pěticiferných přirozených čísel, v jejichž dekadickém zápisu se každá z deseti číslic vyskytuje nejvýše jednou.
Kolik z nich je menší než \(50 000\)?
Permutace bez opakování¶
Definice 1.4
Permutace z \(n\) prvků je každá \(n\)-členná variace z těchto prvků, tj. uspořádaná \(n\)-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje právě jednou.
Věta 1.2
Počet \(P(n)\) všech permutací z \(n\) prvků je
případně s využitím faktoriálu
Poznámka 1.3
Symbol \(n!\) čteme: \(n\) faktoriál.
\(n!\) definujeme pro přirozená čísla, přičemž \(0! = 1\).
\(\displaystyle P(n) = V(n,n)\).
\(\displaystyle V(k,n)={\frac{n!}{(n-k)!}}\)
Příklad 1.7
S připomínkami k navrhovanému zákonu chce v parlamentu vystoupit \(6\) poslanců \(A, B, C, D, E, F\). Určete počet
a) všech možných pořadí jejich vystoupení;
b) všech pořadí, v nichž vystupuje \(A\) po \(E\);
c) všech pořadí, v nichž vystupuje \(A\) ihned po \(E\).
Příklad 1.8
Určete, kolika způsoby může \(n\) táborníků při nástupu na ranní rozcvičku nastoupit a) do řady;
b) do řady, v níž je táborník Adrian na kraji;
c) do řady, v níž táborníci Adrian a Bedřich nestojí vedle sebe;
d) do kruhu, v němž záleží jen na vzájemném rozmístění, nikoliv na umístění vzhledem k ostatním předmětům.
Příklad 1.9
Určete počet všech pěticiferných čísel, v jejichž dekadickém zápisu je každá z číslic \(0, 1, 3, 4, 7\). Kolik z těchto čísel je
a) dělitelných \(6\);
b) větších než \(70~134\)?
Příklad 1.10
V množině \(\mathbb{N}\) všech přirozených čísel řešte rovnici:
Kombinace bez opakování¶
Srovnejme variace bez opakování a kombinace bez opakování:
variace bez opakování: záleží na pořadí
kombinace bez opakování: nezáleží na pořadí
Příklad 1.11
Šachového turnaje se zúčastní \(4\) hráči \(A, B, C, D\). Mají hrát systémem každý s každým jednokolově. Kolik sehrají partií?
Definice 1.5
\(k\)-členná kombinace z \(n\) prvků bez opakování je neuspořádaná \(k\)-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše jednou.
Věta 1.3
Počet všech \(k\)-členných kombinací z \(n\) prvků značíme \(K(k,n)\) a platí
Definice 1.6
Pro \(k, n\in \mathbb{N}, k\leq n\), definujeme kombinační číslo:
Poznámka 1.4
Symbol \({n \choose k}\) čteme: \(n\) nad \(k\).
\(\displaystyle K(k,n)={n \choose k}\).
\(\displaystyle {n \choose {n-k}}={n \choose k}\).
\(\displaystyle {n \choose 0}={n \choose n}=1\).
\(\displaystyle {n \choose 1}=n\).
Příklad 1.12
Určete, kolika způsoby lze na šachovnici \(8 \times 8\) vybrat
a) trojici políček;
b) trojici políček neležících v témže sloupci;
c) trojici políček neležících v témže sloupci ani v téže řadě;
d) trojici políček, která nejsou všechna téže barvy.
Příklad 1.13
Určete, kolika způsoby je možno ze sedmi mužů a čtyř žen vybrat šestičlennou skupinu, v níž jsou
a) právě dvě ženy;
b) aspoň dvě ženy.
Variace s opakování¶
Záleží na pořadí, prvky se mohou opakovat.
Definice 1.7
\(k\)-členná variace s opakováním z \(n\) prvků je uspořádaná \(k\)-tice sestavená z těchto prvků tak, že každý se v ní vyskytuje nejvýše \(k\)-krát.
Věta 1.4
Počet všech \(k\)-členných variací s opakováním z \(n\) prvků je
Příklad 1.14
Určete, kolik značek Morseovy abecedy lze utvořit sestavením teček a čárek do skupin o jednom až čtyřech prvcích.
Příklad 1.15
Určete počet všech podmnožin \(k\)-prvkové množiny.
Příklad 1.16
Příklad. Dalibor zapomněl heslo. Pouze si pamatoval, že na prvních třech místech byla písmena a na dalších čtyřech místech číslice. Kolik by musel vyzkoušet možností? Je možné použít \(26\) písmen.
Permutace s opakování¶
Definice 1.8
\(k\)-členná permutace s opakováním z \(n\) prvků je uspořádaná \(k\)-tice sestavená z těchto \(n\) prvků tak, že jednotlivé prvky mají pevně daný počet opakování
(tj. první prvek se vyskytuje \(k_1\)-krát, druhý prvek se vyskytuje \(k_2\)-krát,\(\ldots\), \(n\)-tý prvek se vyskytuje \(k_n\) krát a musí platit \(k_1+k_2+\ldots+k_n=k\)).
Věta 1.5
Počet \(P'(k_1, k_2, \ldots, k_n)\) \(k\)-členných permutací s opakováním z \(n\) prvků, v nichž se jednotlivé prvky opakují \(k_1, k_2, \ldots , k_n\)-krát, je
Příklad 1.17
Určete počet způsobů, jimiž lze přemístit písmena slova ABRAKADABRA. Určete, v kolika z nich
a) žádná dvojice sousedních písmen není tvořena písmeny A;
b) žádná pětice sousedních písmen není tvořena pěti písmeny A.
Příklad 1.18
Určete počet všech čtyřciferných přirozených čísel dělitelných devíti, v jejichž dekadickém zápisu nejsou jiné číslice než \(0, 1, 2, 5, 7\).
Kombinace s opakování¶
Nezáleží na pořadí, prvky se mohou opakovat.
Příklad 1.19
Kolik částek můžeme zaplatit právě \(2\) mincemi, máme-li k dispozici korunové, dvoukorunové, pětikorunové a desetikorunové mince a to každý druh alespoň ve dvou exemplářích?
Zobrazit řešení
Výčtem: \((1,1), (1,2), (1,5), (1,10), (2,2), (2,5), (2,10), (5,5), (5,10), (10,10)\).
Příklad si trochu více rozebereme:
Předchozí dvoučlenné kombinace ze \(4\) prvků můžeme znázornit pomocí \(4\) přihrádek (první pro koruny, druhou pro dvoukoruny, třetí pro pětikoruny, čtvrtou pro desetikoruny) následovně:
\((1,1) \ldots \circ\circ│││\)
\((1,2) \ldots \circ│\circ││\)
\((1,5) \ldots \circ││\circ│ \)
\((1,10) \ldots \circ│││\circ \)
\((2,2) \ldots │\circ\circ││ \)
\((2,5) \ldots │\circ│\circ│ \)
\((2,10) \ldots │\circ││\circ\)
\((5,5) \ldots ││\circ\circ│ \)
\((5,10) \ldots ││\circ│\circ \)
\((10,10) \ldots │││\circ\circ\)
Tudíž každé dvoučlenné kombinaci s opakováním ze \(4\) prvků \(1, 2, 5, 10\) odpovídá jediná uspořádaná pětice o dvou tečkách a třech čárkách a naopak. Pro počet všech dvoučlenných kombinací s opakováním ze \(4\) prvků \(K'(2,4)\) tak platí \(K'(2,4) = P'(2,3)\).
Definice 1.9
\(k\)-členná kombinace s opakováním z \(n\) prvků je neuspořádaná \(k\)-tice sestavená z těchto prvků tak, že každý prvek se v ní vyskytuje nejvýše \(k\)-krát.
Věta 1.5
Počet \(K'(k, n)\) \(k\)-členných kombinací s opakováním z \(n\) prvků je
Příklad 1.19
Určete počet všech trojúhelníků, z nichž žádné dva nejsou shodné a jejichž každá strana má velikost vyjádřenou některým z čísel \(n + 1\), \(n + 2\), \(n + 3\), \(\ldots\) , \(2 n\), kde \(n\) je přirozené číslo. Kolik těchto trojúhelníků je
a) rovnoramenných;
b) rovnostranných?
Příklad 1.20
V sáčku jsou červené, modré a zelené kuličky, přičemž kuličky téže barvy jsou nerozlišitelné. Určete, kolika způsoby lze vybrat pět kuliček, jestliže v sáčku je
a) aspoň pět kuliček od každé barvy;
b) pět červených, čtyři modré a čtyři zelené?
Dirichletův přihrádkový princip¶
Věta 1
Je-li aspoň \(k+1\) předmětů rozmístěno do \(k\) přihrádek, pak v některé přihrádce jsou aspoň \(2\) předměty.
Věta 1.6
Je-li aspoň \(k+1\) předmětů rozmístěno do \(k\) přihrádek, pak v některé přihrádce jsou aspoň \(2\) předměty.
Příklad 1.21
Kolikrát po sobě je třeba hodit třemi hracími kostkami, aby při těchto hodech padl aspoň čtyřikrát týž součet ok na všech třech hracích kostkách.
Příklad 1.22
Každý z deseti přátel poslal pěti z ostatních přátel vždy po jedné pohlednici. Dokažte, že aspoň dva z nich si poslali pohlednice navzájem.
Příklad 1.23
Šachista se \(77\) dní připravoval na turnaj. V rámci přípravy odehrál každý den aspoň jednu partii. Celkově však nesehrál více než \(132\) partií. Dokažte, že v několika po sobě jdoucích dnech odehrál dohromady právě \(21\) partií.
Pascalův trojúhelník¶
Poznámka 1.5
Pro konečnou množinu \(A\) budeme symbolem \(|A|\) značit počet jejích prvků.
Věta 1.7
Nechť \(a_i\) , \(i=1, 2, \ldots, n\) jsou konečné množiny. Pak platí
Poznámka 1.6
Speciálně pro tři množiny platí:
Příklad 1.24
Ze \(100\) dětí se \(28\) učí angličtinu, \(30\) němčinu a \(42\) francouzštinu. Angličtinu a němčinu se současně učí \(8\) žáků, angličtinu s francouzštinou \(10\) žáků a francouzštinu s němčinou \(5\) žáků, přitom \(3\) žáci se učí všem třem jazykům současně. Určete, kolik z těchto \(100\) dětí se neučí žádný z uvedených cizích jazyků.
Příklad 1.25
Ve třídě je \(28\) žáků, z nichž každý řeší aspoň jednu ze tří olympiád: matematickou, fyzikální, chemickou. Každou z uvedených olympiád řeší právě \(14\) žáků třídy. Počet žáků, kteří řeší aspoň dvě olympiády je šestkrát větší než počet žáků řešících všechny tři olympiády. Dokažte, že existuje aspoň \(6\) žáků třídy, kteří soutěží právě v jedné a téže olympiádě.
Pascalův trojúhelník a binomická věta¶
Poznámka 1.8
Již jsme zmínili symetrickou vlastnost kombinačního čísla:
\(\displaystyle {n \choose k}={n \choose {n-k}}\).
Ukažme další zajímavou vlastnost:
\(\displaystyle {n \choose k}+{n \choose {k+1}}={{n+1} \choose {k+1}}\).
Příklad 1.26
:class: warning Vyjádřete jediným kombinačním číslem součet:
\(\displaystyle {3 \choose 3}+{4 \choose 3}+{5 \choose 3}+{6 \choose 3}+{7 \choose 3}\)
Poznámka 1.8
Vlastnosti kombinačních čísel je možné promítnout do tzv. Pascalova trojúhelníku.
Příklad 1.26
Příklad. Ve čtvercové síti tvořené jednotkovými čtverci je dán obdélník \(ABCD\), jehož strany leží v přímkách této sítě a mají velikost \(│AB│=5\), \(│BC│=4\). Určete, kolika různými způsoby je možné se dostat z bodu \(A\) do bodu \(C\), postupujeme-li pouze po přímkách dané sítě a můžeme jít nahoru nebo vpravo.
Věta 1.8 - Věta binomická
Pro všechna čísla \(a, b\) a každé přirozené číslo \(n\) platí:
Příklad 1.27
Pomocí binomické věty dokažte, že číslo
je dělitelné \(100\).