Kombinace

Typický příklad může být sportka, kde se ze čtyřiceti devíti čísel tahá šest kuliček, přičemž nezáleží, které číslo bylo vylosované jako první. Hráč musí prostě uhádnout, jaká čísla byla tažena, nic víc se po něm nechce. Vzorec pro počítání kombinací poté vypadá velice podobně jako je tomu u variací:

Zkusíme si spočítat ten příklad se sportkou. Máme tedy 49 čísel (n) a taháme z nich 6 čísel (k). Dosadíme do vzorce:

Existuje přes třináct milionů kombinací, z čehož plyne, že i kdyby všichni obyvatelé naší překrásné republiky vsadili právě jednu kombinaci do sportky, výhra by nebyla jistá.

Toto pravidlo je zcela jednoduché a většina lidí ho zná takřka od přírody. Pokud například máte dvě množiny a chcete zjistit, kolik existuje různých dvojic, složených z jedné i druhé množiny, vynásobíte pouze počet členů jedné množiny, počtem členů druhé množiny. V praxi si to můžeme ukázat na jednoduchém příkladu:

Kolik existuje různých dvojciferných čísel? Pokud neaplikujeme selský rozum, ale matematiku, dostáváme takovýto výpočet: na prvním místě dvojciferného čísla se mohou vyskytovat všechny číslice vyjma nuly, což znamená celkem devět číslic. Na druhém místě se již nula vyskytnout může, takže to dělá celkem deset číslic. Počet kombinací získáme vynásobením počtu číslic, devět krát deset a to je devadesát. Existuje celkem devadesát různých dvojciferných čísel.

Kolik existuje různých trojciferných čísel, kde se žádná číslice nesmí vyskytnout dvakrát? Tady už selský rozum moc nepomůže, nicméně naše kombinatorické pravidlo součinu aplikovat můžeme. Na prvním místě může být opět devět čísílek, nulou číslo začínat nemůže. Na druhém místě mohou být všechna čísla včetně nuly, ale nesmí tam být číslice vysktující se na první pozici, takže od počtu deseti možných číslic odečteme jedničku (například pokud naše trojciferné číslo zrovna začíná čtyřkou, je jasné, že na druhé pozici se již čtyřka vyskytovat nemůže, protože by v celém čísle bylo dvakrát). Na třetím místě mohou být opět všechny číslice, ale nesmí tam číslice, která je na prvním nebo na druhém místě. Od celkového počtu deseti číslic musíme odečíst dvojku. Nyní už jen vynásobíme 9 · 9 · 8 = 648. Celkový počet kombinací je šestset čtyřicet osm.

Opět i toto pravidlo není moc třeba vysvětlovat. Začneme nejlépe na příkladu: Kolik existuje různých dvojciferných nebo jednociferných čísel? Logika říká, že devadesát devět, ale pojďme si to spočítat. Z předchozí kapitoly víme, že počet všech různých dvouciferných čísel je devadesát. Zároveň víme, že jednociferných je devět. Nyní tyto dva dílčí výsledky sečteme, čímž aplikujeme kombinatorické pravidlo součtu a získáme výsledek. Ten je opravdu devadesát devět.

Kombinatorické pravidlo součtu se používá v případě, kdy ty dílčí množiny (zde jednociferná a dvojciferná čísla) na sebe nejsou nijak závislé, zatímco kombinatorické pravidlo součinu použijete, když na sebe ty množiny závislé jsou. Také lze říci, že pravidlo součtu použijete v případě disjunkce - Kolik existuje různých dvojciferných nebo jednociferných čísel? Spojka nebo nám jasně říká, že budeme potřebovat kombinatorické pravidlo součtu. Ale pozor, ne vždy, když se někde v zadání vyskytuje slůvko nebo jedná se o pravidlo součtu ;-).

Naproti tomu kombinatorické pravidlo součinu se používá v případě konjunkce, tedy když máme v zadání něco ve smyslu a zároveň.

Kvůli stručnějšímu zápisu kombinací bylo zavedeno kombinační číslo, které zapisujeme podobně jako zlomek, akorát bez zlomkové čáry a v závorkách. Ze začátku se vám to bude strašně plést a budete tam tu zlomkovou čáru instinktivně psát, věřte mi ;-). Takovéto kombinační číslo čteme „n nad k“:

Jinak je to stejné, jako zápis K(k, n). Následují nějaké vzorce pro kombinační čísla:

#1 Vaše dítě si na Vánoce namalovalo celkem šest dárků: nový počítač, mp3 přehrávač, fichtl, skok padákem, osobní setkání s Anetou Langerovou a kýbl pudingu. Vy jste se ale s partnerem rozhodli, že mu dáte pouze dva dárky, přitom jste se ale zatím nestačili dohodnout jaké. Pouze jste pro sichr vyřadili skok padákem. Z kolikati různých dvojic dárků můžete vybírat?

Jedná se o velmi jednoduchý příklad na kombinace, výsledek je prosté kombinační číslo pět (celkový počet dárků, ze kterých jsme vybírali) nad dvěma (počet, který jsme chtěli získat):

#2 Máte skupinu padesáti lidí - polovina muži a polovina ženy. Kolik existuje různých trojic, pokaď nesmí být složeny pouze z jednoho pohlaví (tj. v trojici se nesmí vyskytnout tři muži nebo tři ženy).

To už je trošičku složitější kombinace. Pokud vyloučíme jednopohlavní trojici lidí, zbydou nám pouze dvě možnosti, jak může být trojice složena - dva muži a jedna žena nebo jeden muž a dvě ženy, přičemž počet kombinací první skupiny (dva muži a jedna žena) bude stejný, jako počet kombinací druhé skupiny. Stačí nám tedy vypočítat počet kombinací první skupiny a ten následně vynásobit dvěma. Teď už je to opět hračka. Určíme počet kombinací různých dvojic mužů, což je dvacet pět nad dvěma a vynásobíme to počtem kombinací jedné ženy (to dělá dvacet pět, viz předchozí seznam kombinačních čísel, konkrétně hned to první). Tento výsledek již jen vynásobíme dvěma a máme konečný výsledek.

#3 Ve třídě je celkem deset dětí a zrovna mají tělocvik. Pan učitel ovšem dostal od pana ředitele pověření vzít čtyři kluky jako buky a přestěhovat nějaké skříně z prvního patra do druhého. Kolik má pan učitel možností, pokud přihlédneme k tomu, že malý Horáček nechce stěhovat skříně s malým Boháčkem, protože minule si díky něho skřípl prst?

Nejprve spočítáme kombinace, kdy se v té čtveřici nebude vyskytovat ani Tonda Boháčků, ale také ani Matěj Horáčků. To je jednoduchá kombinace osm nad čtyřmi (osm je celkový počet dětí, bez Tondy a bez Matěje a čtyři je počet dětí, která pan ředitel chtěl).

Teď spočítáme počet kombinací, když bude přítomen Tonda, ale ne Matěj. Opět vybíráme z osmi dětí (víme, že Tonda už v té čtveřici bude a Matěj tam být nemůže, proto o dva méně, než je celkový počet dětí), ale už vybíráme pouze trojici, protože jedno místo bude vždy obsazeno (Tondou). Takže to máme kombinaci osm nad třemi:

Počet kombinací v případě, kdy bude ve čtveřici přítomen Matěj, ale Tonda ne, bude identický, padesát šest. Nyní máme odchyceny všechny případy, kdy se v dané čtveřici nebude vyskytovat Tonda a zároveň Matěj. Stačí pouze aplikovat kombinatorické pravidlo součtu a sečíst je: 70 + 56 + 56 =182.

Úlohu můžeme také řešit opačnou a v tomto případě i značně jednodušší cestou. Než abychom počítali, v kterých kombinacích se tam ti dva lumpové nevyskytují, spočítáme, kdy se tam vyskytují a odečteme od celkového počtu kombinací. Neboli místo toho abychom zjišťovali, kdy výsledek vyhovuje zadání, spočítáme, kdy zadání nevyhovuje. Takže nyní musíme spočítat, kolik různých čtveřic bychom byli schopni udělat, pokud by byl Tonda společně s Matějem. To je jednoduché, dvě místa z čtveřice máme obsazené, takže nám zbývá obsadit různými kombinacemi zbylé dvě. Opět vybíráme z osmi zbylých dětí a vychází nám osm nade dvěma:

Tento počet kombinací odečteme od celkého počtu kombinací, které můžeme dostat, kdybychom nebrali v potaz výmysly těch dvou lumpů. To dělá jednoduché deset nad čtyřmi:

Nyní od sebe tyto dva dílčí výsledky odečteme 210 − 28 = 182. Vidíme, že vyšel stejný výsledek jako v předchozích počtech.