Bonus - Bijekce

Možná si říkáte, že v předchozí úloze by stačily části (a), (b). Část (a) se spočítá jako $100 + 99 + \dots + 2 + 1$ a část (b) je ta, kterou umíme snadno vyřešit jako ${101 \choose 2}$. A vlastně - části (a), (b) jsou ta samá úloha! To je naprostá pravda. Velmi často lze postup zkrátit tak, že vymyslíme jen jednu úlohu (například (a)) a tu vyřešíme dvěma způsoby (jako (a) a jako (b)). Tím získáme rovnost $$1+2+3+\dots+99+100 = {101 \choose 2}.$$ Tomuto přístupu se říká počítání dvěma způsoby. Pojďme si jej vyzkoušet na složitější úloze. Tentokrát ještě prozradíme oba způsoby, jak úlohu spočítat a vaším úkolem bude zjistit, jaký součet jsme díky tomu spočítali.

Úloha: Máme $101$ fotbalistů očíslovaných čísly $1$ až $101$. Vybereme z nich trenéra, kapitána a brankáře. Trenér bude mít nejvyšší číslo a nemůže zároveň hrát (tedy nemůže být kapitánem nebo brankářem). Kapitán může být zároveň i brankářem.

1. (a) Vybereme trenéra a tomu dáme úkol: Z lidí, kteří mají menší číslo než ty, vyber kapitána a brankáře (může se jednat o téhož člověka). Kolika způsoby může úkol splnit trenér číslo $7$?
   

1. Role přidělíme třem různým fotbalistům. Kolika způsoby lze provést výběr fotbalistů a rozdělení rolí v tomto případě? (Nezapomeňte, že trenér musí mít nejvyšší číslo.)
2. Vybereme jenom dva fotbalisty, kterým přiřadíme tři role. Kolika způsoby lze provést výběr fotbalistů a rozdělení rolí v tomto případě?

Zobrazit výsledek.

Pokud se vám počítání dvěma způsoby zamlouvá, máte příležitost si jej sami vyzkoušet. Nejtěžším krokem bývá obvykle vymyšlení úlohy, kterou se následně pokusíme řešit dvěma způsoby. Pro získání této dovednosti slouží následující úloha.

Úloha: Na párty se sešlo $k$ kluků a $h$ holek. Vymyslete úlohu, jejímž výsledkem bude:

1. (a) $k\cdot h$;
2. (b) $h \cdot {k \choose 4}$;
3. (c) ${h \choose 2} \cdot {k \choose 3}$;
4. (d) $5 \cdot {k \choose 5}$;
5. (e) $2^h$.

Řešení:

1. (a) Kolika způsoby lze vytvořit taneční pár (holka – kluk).
2. (b) Kolika způsoby lze vytvořit 5člennou skupinku, v níž bude jedna holka a $4$ kluci?
3. (c) Kolika způsoby lze vytvořit 5člennou skupinku, v níž budou $2$ holky a $3$ kluci?
4. (d) Kolika způsoby lze vytvořit 5člennou skupinku kluků a z ní vybrat kapitána?
5. (e) Jeden z kluků se rozhodl získat telefonní číslo od všech holek. Každá holka mu své telefonní číslo buď dá, nebo nedá. Kolika způsoby mohlo jeho snažení dopadnout? Stroze: Kolika způsoby lze vybrat libovolně velkou podskupinu (třeba i prázdnou) ze skupiny $h$ holek?

Pojďme si teď vyzkoušet počítání dvěma způsoby na vlastní kůži! Vlastně možná spíš nepočítání, to posuďte sami.

Úloha: Jste jedním z $n$ lidí, z nichž se vybere $k$ vyvolených.

1. (a) V kolika případech jste mezi vyvolenými?
2. (b) V kolika případech nejste mezi vyvolenými?
3. (c) Odvoďte vztah mezi ${n \choose k}$, ${n-1 \choose k}$ a ${n-1 \choose k-1}$.

Úloha: Rozmyslete si, že platí $${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose n-1} + {n \choose n} = 2^n.$$ (Vidíte-li vztah ihned z binomické věty, tak ji na chvíli zapomeňte.)

Nápověda: Pravou stranu interpretujte jako počet způsobů, kterými může dopadnout snaha získat od $n$ holek telefonní čísla. Poté rozlište případy podle toho, u kolika děvčat uspěl.

Úloha: Nahlédněte, že platí $$k{n \choose k} = n{n-1 \choose k-1}.$$

Nápověda: Počítejte, jak vybrat $k$ lidí z $n$ a ještě z nich vybrat jednoho kapitána.

Úloha: Rozmyslete si, že platí $$1\cdot{n \choose 1}+2\cdot{n \choose 2}+\dots+n\cdot{n \choose n} = n\cdot 2^{n-1}.$$

Nápověda: Z $n$ kluků vyberte $k$-členný tým a jeho kapitána. Použijte předchozí úlohy.

Úloha: Dokažte, že $$\binom{n}{0}\binom{n}{n}+\binom{n}{1}\binom{n}{n-1}+\binom{n}{2}\binom{n}{n-2}+\dots+\binom{n}{n}\binom{n}{0}=\binom{2n}{n}.$$

Nápověda: Ze skupiny $2n$ lidí vybereme $n$-člennou skupinu. Přitom ve skupině je $n$ kluků a $n$ holek.

Kde všude jsou kombinační čísla?

Rozhodně není pravda, že každá kombinatorická úloha (byť s pěkným zadáním) má pěkné řešení. Mnoho z nich ale má a pár takových si ještě ukážeme. Většinou platí, že pokud má úloha „pěkný výsledek“, pak pro to je i „dobrý důvod“. V takových případech se úloha většina dá přeložit na jinou úlohu, jejíž řešení je snadné. Zkuste si to na následujících, vůbec ne snadných, úlohách. Pokud se vám nebude dařit vhodný překlad najít, můžete využít nápovědy ve formě obrázku.

Úloha: Zjistěte, kolik cest délky $a+b$ vede z levého dolního rohu obdélníku $a \times b$ do jeho pravého horního rohu.

Nápověda:

Úloha: Na tramvajové lince je celkem $n$ zastávek. Protože je linka moc dlouhá, rozhodlo se město dvě zastávky zrušit. Aby však lidé neměli k novým zastávkám příliš daleko, nebudou se zastávky rušit vedle sebe. Kolika způsoby lze dvě nesousední linky zrušit?

Nápověda:

Úloha: Rovnostranný trojúhelník o straně délky $n$ je rozdělen jednotkovou trojúhelníkovou mřížkou (na obrázku pro $n=7$). Zjistěte počet rovnoběžníků, které lze do této mřížky nakreslit a jejichž strany jsou rovnoběžné se stranami rovnoběžníku na obrázku.

Nápověda:

Catalanova čísla aneb cestičky a náhrdelníky

Poměrně často se v matematice stává, že určitý problém neumíme vyřešit rovnou, ale umíme jej převést na jiné problémy. U nového problému doufáme, že bude pro nás snažší nebo že jsme jej už vlastně řešili. Ne vždy tomu tak je. Dovednost převádět problémy na jiné, jednodušší, je asi vůbec nejcennější dovednost v celé matematice.

Něco podobného si zkusíme na úlohách týkajících se tzv. Catalanových čísel. Je dosti pravděpodobné, že žádnou z následujících úloh nebudete umět spočítat. To (zatím) není cílem. Pro tuto chvíli si rozmyslete, že až na jednu „zrádnou“ úlohu se ty ostatní dají na sebe přeložit.

1. (a) (cesty v mřížce I) Uvažujme všechny cesty délky $2n$, které vedou z levého dolního rohu čtverce $n \times n$ do jeho pravého horního rohu. Kolik z nich se nachází nad diagonálou (mohou se diagonály dotýkat na více místech, ale neprotínají ji)?
   

Poznámka: Catalanovo číslo $C_n$ se nejčastěji definuje právě jako počet vyhovujících cest v části (a).

Nápovědy:

(a) $\Leftrightarrow$ (b)

(a) $\Leftrightarrow$ (c)

(b) $\Leftrightarrow$ (d)

(c) $\nLeftrightarrow$ (e)

Přirozené je úsečce tvaru $\diagup$ přiřadit (například) černý korálek a úsečce tvaru $\diagdown$ přiřadit bílý korálek. Začneme kupříkladu černým korálkem „nahoře“ a pokračujeme ve směru hodinových ručiček. Takové (ani žádné jiné) přiřazení ale nemůže fungovat už jenom z toho důvodu, že počet Dyckových cest a náhrdelníků se liší (už pro $n=3$). Rozmyslete si, ze kterých cest by tímto postupem vznikly stejné náhrdelníky.

(d) $\Leftrightarrow$ (f) Tento překlad je nejtěžší. Nestačí si uvědomit, jak z každé nakloněné Dyckovy cesty vyrobit náhrdelník. Je potřeba (a patrně náročnější) si uvědomit i to, že ze dvou nakloněných Dyckových cest nemůže vzniknout stejný náhrdelník. To je stejné popsat způsob, který z náhrdelníku vyrobí právě jednu nakloněnou Dyckovu cestu (výroba musí být nezávislá na tom, jak náhrdelník na začátku natočíme).

Pro výrobu náhrdelníku z nakloněné Dyckovy cesty zvolíme stejný postup jako dříve.

Tentokrát si rozmyslíme i to, že tento postup lze obrátit, tedy jak vyrobit nakloněnou Dyckovu cestu z náhrdelníku.

Poznámka: Tuto náročnější myšlenku bychom mohli popsat i mnoha jinými způsoby. Lze například říci, že náhrdelník lze natočit přesně jedním způsobem tak, že jej držíme za černý korálek (ruka drží náhrdelník za korálek, který je nejvýše) a vydáme-li se po směru hodinových ručiček, po celou dobu cesty platí, že jsme prošli více černých korálků než bílých. Toto tvrzení by však bylo potřeba dokázat (což se dá udělat například sporem, nicméně je nutné napsat několik řádek textu).

Jak Catalanova čísla spočítat?

Výsledkem pěti z přechozích šesti úloh je $n$-té Catalanovo číslo. Spočítat jakoukoliv z nich ovšem není úplně snadné. Rozmyslíme si, jak spočítat náhrdelníky v úloze (f), které jsou vytvořeny z $n+1$ černých a $n$ bílých korálků. Náhrdelníky se obvykle vytvářejí tak, že se korálky nejdříve navléknou na šňůrku a posléze se konce šňůrky svážou. Pro účely naší úlohy začneme výrobu náhrdelníku trochu jinak. Na jeden konec šňůrky dáme polovinu černého korálku, pak (v nějakém pořadí) navlékneme $n$ černých a $n$ bílých korálků a na druhý konec opět dáme půlku černého korálku. Obě půlky černého korálku slepíme a tím dostaneme náhrdelník z $n+1$ černých a $n$ bílých korálků.

Úloha: Kolika způsoby lze na šňůrku navléct $n$ černých a $n$ bílých korálků? (Z důvodů uvedených výše ještě na oba konce přidáme půlky černého korálku. Jedna taková šňůrka s navlečenými korálky je na obrázku.)

Výsledek: ${2n \choose n}$.

Komplikací ovšem je, že některé šňůrky s navlečenými korálky odpovídají témuž náhrdelníku.

Úloha: Pro $n=3$ najděte všechny šňůrky s navlečenými korálky, které odpovídají stejnému náhrdelníku jako šňůrka na obrázku. (Na obou koncích každé šňůrky jsou půlky černého korálku. Tyto půlky při výrobě náhrdelníku slepíme k sobě.)

I v obecném případě lze dokázat stejný výsledek jako jsme dostali v předchozí úloze. Skutečně platí, že přesně $n+1$ různých šňůrek odpovídá témuž náhrdelníku. Že jich není více, je celkem snadné – každý náhrdelník lze rozříznout na jednom z $n+1$ míst (rozřízneme některý z $n+1$ černých korálků). Je ale nutné si ještě rozmyslet, že každým rozříznutím dostaneme opravdu jiné uspořádání korálků na šňůrce.

Úloha: Ze $3$ černých a $3$ bílých korálků je možné udělat náhrdelník s následující vlastností: Rozříznutím některého černého korálku dostaneme stejné uspořádání korálků na šňůrce, jako bychom dostali při rozříznutí nějakého jiného černého korálku. Najděte takový náhrdelník.

Předchozí úloha ukazuje, že náhrdelníky z $n$ černých a $n$ bílých korálků (to jsou přesně ty z úlohy (e) předchozího podkapitoly) nemají tu vlastnost, že rozříznutím libovolného z černých korálků dostaneme vždy jiné uspořádání korálků na šňůrce.

Proč ji tedy náhrdelníky z $n+1$ černých a $n$ bílých korálků mají? Představme si, že bychom rozříznutím korálku $A$ dostali stejné uspořádání korálků na šňůrce, jako bychom dostali rozříznutím korálku $B$.

To znamená, že otočením náhrdelníku z korálku $A$ na $B$ (řekněme, že to je otočení o $k$ korálků) se náhrdelník nezmění. Náhrdelníku přitom odpovídá právě jedna nakloněná Dyckova cesta, která začíná na nějakém korálku. Protože náhrdelník se při otočení o $k$ korálků nezmění, je možné i nakloněnou Dyckovu cestu začít o $k$ korálků „později“. To je ale nesmysl, protože jsme si už dříve rozmysleli, že začátek nakloněné Dyckovy cesty je určen jednoznačně. Nemůže se tedy stát, že bychom že bychom rozříznutím jednoho korálku dostali stejně vypadající šňůrku jako rozříznutím jiného korálku.

Úloha: Už víme, kolika způsoby lze na šňůrku navléct $n$ černých a $n$ bílých korálků (a navíc na koncích jsou půlky černého korálku). Taky víme, kolik různých šňůrek odpovídá jednomu náhrdelníku. Kolik náhrdelníků lze tedy vyrobit z $n+1$ černých a $n$ bílých korálků?

Úlohy pro fajnšmekry

Úloha: (pyramidy z mincí) Do řady na stůl položíme $n$ mincí tak, aby se sousední mince dotýkaly. Poté na ně začneme stavět pyramidu tak, jak je naznačeno na obrázku. Kolik pyramid lze tímto způsobem postavit?

Na obrázku jsou všechny pyramidy pro $n=3$.

Nápověda: Hledejte Dyckovy cesty.

Úloha: (stánek s pivem) Ve stánku čepují vynikající pivo za 10 Kč. Před stánkem se vytvoří fronta $2n$ lidí, z nichž $n$ má u sebe desetikorunu a zbývající mají dvacetikorunu. Stánkaři nečekali takový zájem, a tak už nemají vůbec žádné drobné na vracení. Jsou zcela odkázáni na desetikoruny, které jim lidé dávají při placení. Kolika způsoby může být fronta seřazena tak, aby stánkaři mohli každému příchozímu ihned vrátit drobné?

(Např. pro $n=2$ by fronta $10, 20, 10, 20$ byla vyhovující, zatímco fronta $10, 20, 20, 10$ by byla nevyhovující.)

Nápověda: Zásobu desetikorun u stánkařů přeložte na Dyckovu cestu.

Úloha: Označme $C_0 = 1$ a dále $C_n$ počet Dyckových $n$-cest. Můžeme spočítat, že $$C_0 = 1, \quad C_1 = 1, \quad C_2 = 2, \quad C_3 = 5, \quad C_4 = 14, \quad C_5 = 42, \quad C_6 = 132, \dots$$ Pak platí vztahy $$\begin{equation*}\begin{split} C_2 &= C_0C_1 + C_1C_0, \\ C_3 &= C_0C_2 + C_1C_1 + C_2C_0, \\ C_4 &= C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0, \\ &\dots \end{split}\end{equation*}$$ Rozmyslete si, že platí $$C_{n+1} = \sum_{k=0}^n C_k C_{n-k} = C_0C_n + C_1C_{n-1} + \dots + C_{n-1}C_1+C_nC_0.$$

Nápověda: Použijte nakloněnou Dyckovu $n$-cestu a pomocí bodu nejbližšího čárkované čáře ji rozdělte na dvě kratší nakloněné Dyckovy cesty. Uvažujte pak všechny možné kombinace kratších nakloněných cest.

Na obrázku je nakloněná Dyckova $6$-cesta rozdělená červeným bodem na nakloněnou $3$-cestu a nakloněnou $2$-cestu.

Úloha: Mějme konvexní $(n+2)$-úhelník. Kolika způsoby je možné jej rozdělit na trojúhelníky kreslením neprotínajících se úhlopříček? (Jedná se o počet tzv. triangulací.)

Na obrázku jsou nakresleny všechny triangulace konvexního šestiúhelníku.

Nápověda: Zvolte si pevně jednu stranu $(n+2)$-úhelníka. Vyberte trojúhelník obsahující tuto stranu. Ten rozdělí $(n+2)$-úhelník na dva menší mnohoúhelníky. Uvažujte pak všechny možné kombinace triangulací těchto menších mnohoúhelníků. Postupným výběrem všech možných trojúhelníků obsahujících zvolenou stranu odvoďte vztah nápadně připomínající vztah $C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$ pro Catalanova čísla.

Úloha: Kolem kulatého stolu sedí $2n$ lidí. Kolika způsoby si mohou všichni s někým podat ruku tak, aby se jim ruce nekřížily?

Nápověda: Zvolte si pevně jednoho člověka a podívejte se, s kým si může podat ruku. Toto podání rukou rozdělí ostatní lidi na dvě menší skupiny, pro které řešíme tutéž úlohu. Postupným výběrem všech možných partnerů zvoleného člověka odvoďte vztah nápadně připomínající vztah $C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$ pro Catalanova čísla.