Průvodní povídání 1

Až ke kombinačnímu číslu

Průvodní povídání je také k dispozici ve formátu pdf.

Milí pikomaťáci,

\def\deg{^\circ}\let\angle\sphericalangle toto je již druhý ročník průvodního povídání. Je to krátký text, v němž se dozvíš něco o matematice nad rámec základní školy, letos konkrétně o kombinatorice. V každé sérii se objeví jedna úloha, s níž by mělo průvodní povídání pomoci, můžeš tedy získané znalosti hned využít. Pokud by Ti něco v průvodním povídání nebylo jasné nebo by Tě zajímalo něco navíc, neváhej napsat na tento e-mail:

Kombinatorika je matematická disciplína, která se zabývá počítáním možností, jak lze něco udělat. V tomto textu se zaměříme na permutaci, variaci a kombinaci. Zní to vznešeně, ale ve skutečnosti budeme dávat odpovědi na celkem přirozené otázky.

Představ si, že máš skupinku čtyř lidí, kteří se jmenují Tom, Klátra, Honzík a Martin. Kolika způsoby z této skupinky můžeme vybrat jednoho člověka, kterému dáme bonbon? Inu, máme čtyři různé lidi, takže máme i čtyři způsoby. O něco těžší otázka je, kolika způsoby můžeme vybrat dva různé lidi, z nichž jednomu dáme bonbon a druhému zmrzlinu. Můžeme si to představit tak, že nejprve vybereme toho, kdo dostane bonbon. To už víme, že umíme udělat čtyřmi způsoby. Dále vybereme mezi ostatními toho, kdo dostane zmrzlinu. Zbývají tři lidé, takže máme tři možnosti. Například pokud bonbon dostane Tom, zmrzlinu může dostat Klátra, Martin, nebo Honzík. Dohromady tedy máme 4\cdot 3 = 12 možností.

Nyní zkusíme spočítat počet způsobů, jakými lze postavit Toma, Klátru, Martina a Honzíka za sebe do řady. Nejprve vybereme, kdo bude první, to jsou opět čtyři možnosti, pak kdo bude druhý, to jsou tři možnosti. Potom vybereme, kdo bude třetí, na což už zbývají jen dva lidé, a poslední je jednoznačně určený prvními třemi. Dohromady tedy máme 4\cdot 3\cdot 2\cdot 1 = 24 způsobů, jak čtyři lidi seřadit. Zkus si sám rozmyslet, kolik způsobů seřazení máme třeba pro šest lidí.

Seřazené skupince lidí říkáme permutace oné skupinky. Totéž platí pro libovolnou množinu, tj. skupinu čísel, kuliček či čehokoli jiného. Předchozí odstavec tedy lze shrnout následujícím způsobem: Existuje 24 permutací čtyřprvkové množiny. Protože permutace jsou důležité a matematici jsou líní, vzniklo následující značení:

Definice: Značíme n!=n\cdot (n-1) \cdots 2\cdot 1 a n! čteme „n faktoriál.“

Například 1! = 1, 2! = 2\cdot 1 = 2, 3! = 3\cdot 2\cdot 1 = 6. Navíc definujeme 0! = 1. Proč to dává smysl? Protože když máš seřadit žádného člověka do řady, máš jeden způsob, jak to udělat - neseřadíš nikoho.

Vyzkoušej si výše popsaný postup zopakovat v několika dalších situacích:

Úloha: Na parkovišti je pět parkovacích míst. Kolika způsoby na něm může zaparkovat červené, žluté a modré auto?

Úloha: V jednom vrhu se narodilo šest koťat. Každé koťátko dostane jeden ze šesti různobarevných obojků. Kolika způsoby to lze udělat?

Když máme definovaný faktoriál, můžeme se zkusit vrátit k příkladu se sladkostmi, zobecnit ho a dát na něj obecnou odpověď. Představ si, že máš n lidí a k sladkostí, které mezi ně chceš rozdat. Sladkostí je méně než lidí. Kdyby ti nezáleželo na tom, že někdo dostane víc sladkostí a někdo jiný zase žádnou, můžeš pro každou sladkost nezávisle na ostatních vybrat, komu ji dáš. Máš tedy n\cdot n\cdots n možností, kde n násobíš samo se sebou k-krát. To můžeme zkráceně zapsat jako n^k (čteno „n na k-tou“). Pokud ale chceš být spravedlivější a dát každému nanejvýš jednu sladkost, máš n možností jen pro tu první. Pro další máme už jen n-1 možností, pro ještě další n-2, a tak dál, až pro tu poslední máme jen n-k+1 možností. Dohromady tedy máme n\cdot (n-1) \cdot (n-2) \cdots (n-k+1) možností. Rozmysli si, že toto se dá také zapsat jako \frac{n!}{(n-k)!}. To, co jsme právě spočítali, je počet k-prvkových variací z n prvků.

Většinou ale k různých sladkostí nemáš, místo toho máš třeba k stejných bonbónů. Kolika způsoby je můžeš rozdat, pokud nikdo nemá dostat víc než jeden bonbon? Celkově budeme mít méně možností než v předchozím odstavci, protože v řeči prvního příkladu už nám nezáleží na tom, že jsme zmrzlinu dali Tomovi a bonbon Honzíkovi a ne naopak. Důležité je to, že sladkost dostal Tom a Honzík. Avšak předchozí odstavec nám dává odrazový můstek pro spočítání toho, co nás nyní zajímá. Představ si, že bonbony budeš rozlišovat. Pak seskupíš variace (tj. možnosti, jak je rozdat) podle toho, kdo bonbon dostal. Kolik bude možností v každé skupince? Pro každou skupinku možností máme k pevně daných lidí, kteří bonbon dostanou. Pro první bonbon tedy máme k možností, pro druhý k-1 a tak dále. To už ale přece známe, dohromady dostaneme k! možností v jedné skupince. Stačí nám tedy vydělit celkový počet variací počtem variací v jedné skupince. Dohromady dostáváme \frac{n!}{(n-k)!\cdot k!}. To, co jsme právě spočítali, je počet k-prvkových kombinací z n prvků. To je také velmi důležité číslo, pro které máme speciální značení.

Definice: Značíme \binom{n}{k} = \frac{n!}{(n-k)!\cdot k!}, kde \binom{n}{k} čteme „n nad k“. Tomuto výrazu se říká kombinační číslo nebo také někdy binomický koeficient.

Význam kombinačního čísla si můžeme představit také jako dávání k stejných kuliček do n přihrádek, aby v každé přihrádce byla nejvýše jedna kulička. Tím důležitým ve většině úloh je uvědomit si, co je přihrádka a co je kulička, což si ukážeme na následujících příkladech:

Příklad: Anička měla tabulku 3\times 3 a protože se na hodině matematiky nudila, vybarvila v ní tři různá políčka žlutě. Kolika způsoby to mohla udělat?

Řešení: Políček v tabulce je 3\cdot 3 = 9, z nich vybíráme tři, která budou vybarvena. Políčka v tomto příkladu hrají roli přihrádek a vybarvení jsou kuličky. Odpověď je tedy \binom{9}{3} = \frac{9!}{6!\cdot 3!} = \frac{9\cdot 8\cdot 7}{3\cdot 2\cdot 1} = 84.

Příklad: David má šachovnici 8\times 8, na níž stojí figurka prince v levém dolním rohu. Princ se může pohybovat jen o jedno políčko nahoru nebo o jedno políčko doprava. Kolika způsoby se může dostat do pravého horního rohu šachovnice?

Řešení: Princ musí udělat právě čtrnáct kroků, protože se nemůže vracet. Kroky budou naše přihrádky. Kuličky budou kroky doprava, neboť každý způsob, jak se princ může dostat z levého dolního rohu do pravého horního, odpovídá právě jednomu způsobu, jak ze čtrnácti kroků vybrat sedm kroků doprava. Odpověď tedy je \binom{14}{7}.

Na závěr si to vyzkoušej ještě sám:

Úloha: Zahradník je zmatený, a tak vykopal sedm děr pro ovocné stromky, zatímco potřebuje zasadit jen pět meruněk. Kolika způsoby to nyní může udělat? (Kopat nové díry samozřejmě nebude.)