V této sekci si vyřešíme pár dalších úloh. Některé můžou vyžadovat důmyslnější kombinatorickou interpretaci problému nebo zapojení vícero principů najednou. Nejdříve bychom však chtěli upozornit, že pro kombinatorické úlohy (a zvláště ty „složitější“) je běžné, že existuje více správných formulací a postupů, jak je řešit. Na některých příkladech si to ukážeme. To je na těchto úlohách zábavné, ale někdy může být i trochu záludné. Nenechte se tedy ihned odradit, pokud se výraz ve Vašem řešení liší od toho v učebnici, na přednášce, u spolužáka… Všechny můžou být správné zároveň (pokud dávají stejnou hodnotu). Důležité je dobře porozumět problému a důsledně si promyslet vhodnou interpretaci, a nehrnout se do neuváženého „dosazování do vzorečků“, například na základě podobnosti. Na závěr je možné i ověřit shodu řešení zapsaných různými výrazy jejich přímým vyčíslením.
Vraťme se k Příkladu 12.1.
Čtyři kamarádi se zastavili u stánku se zmrzlinou, ve kterém nabízejí zmrzlinu šesti příchutí.
Před stánkem jsou stolky po dvou. Kolika různými způsoby se můžou kamarádi usadit? (Neřešíme polohu stolu nebo pozici u stolu, jenom kdo s kým sedí.)
Kolika různými způsoby si můžou každý vybrat jeden kopeček zmrzliny tak, aby alespoň dva měli stejnou příchuť?
V prvním momentě by nás mohlo napadnout udělat kombinace $2$ ze $4$, tím vybereme jednu dvojici a druhá zbyde. Tento postup ale zavádí jisté pořadí na dvojicích – jedna dvojice je „vybraná“ a druhá „zbývající“. Tedy, pokud se kamarádi jmenují Anna, Ben, Cyril, Dana, uvedeným postupem rozlišujeme (započítáváme jako dvě různé možnosti) to, zda jsme vybrali A,B a zbývá C,D, a nebo zda jsme vybrali C,D a zbývá A,B. To ale nechceme! Můžeme to napravit tak, že kombinace $2$ ze $4$ vydělíme $2$ a dostaneme tedy ${4\choose 2}.\frac{1}{2}=\frac{6}{2}=3$. Další možná interpretace je, že výběr uděláme vzhledem na jednoho z kamarádů. Vybereme pouze, s kým bude sedět Anna, což jsou $3$ možnosti, a zbytek je tím daný. Odpověď tedy je, že se můžou usadit $3$ různými způsoby.
Postup 1: Při výběru jednoho kopečku zmrzliny každým z kamarádů můžou nastat právě dvě navzájem různé situace: buď má každý jinou příchuť (případ c.) a nebo mají alespoň dva stejnou příchuť (současný případ h.). Podle sčítacího principu je tedy počet všech možných výběrů roven součtu počtu možností v těchto dvou různých situacích (symbolicky, „b. = c. + h.“). K výpočtu použijeme předchozí výsledky a dostaneme, že možností výběrů jednoho kopečku zmrzliny každým z kamarádů tak, aby alespoň dva měli stejnou příchuť je
Podle Poznámky 12.6 šlo vlastně o využití doplňkového principu.
Postup 2: Ukážeme si taky, jak by se příklad počítal „přímo“, rozborem možností. Kdy je splněna podmínka, že mají alespoň dva kamarádi stejnou příchuť zmrzliny? Buď mají stejnou právě dva, právě tři, a nebo všichni čtyři kamarádi. První možnost může navíc nastat dvěma různými způsoby – buď mají zbylí dva kamarádi taky navzájem stejnou příchuť, ale různou od prvních dvou, a nebo mají různou příchuť od všech ostatních. Všechny vyjmenované jsou navzájem různé situace. Pro spočtení celkového výsledku tedy můžeme, podle sčítacího principu, spočítat možnosti v jednotlivých situacích a pak je sečíst.
Začneme od poslední možnosti, protože je nejjednodušší.
Čtyři mají stejnou příchuť: Stačí vybrat onu příchuť, tedy kombinace $1$ ze $6$, což je ${6\choose 1}=6$.
Tři mají stejnou příchuť: Tento proces má tři nezávislé fáze – vybere jednoho z kamarádů, který bude mít jinou příchuť než ostatní (kombinace $1$ ze $4$, tedy ${4\choose 1}=4$ možnosti), tomu vybereme příchuť (kombinace $1$ ze $6$, tedy ${6\choose 1}=6$ možností) a zbylé trojici kamarádů vybereme jednu jinou příchuť (kombinace $1$ ze $5$, tedy ${5\choose 1}=5$ možností). Podle násobícího principu se počty možností v jednotlivých fázích navzájem vynásobí, tedy $4\cdot 6\cdot 5=120$.
Dva stejnou a dva různou: Vybereme dvojici, která bude mít stejnou příchuť (kombinace $2$ ze $4$, tedy ${4\choose 2}=\frac{4!}{2!2!}=6$ možností). Poté vybereme tři různé příchutě, přičemž záleží na pořadí, protože první bude pro dvojici, druhá pro jednoho jednotlivce, třetí pro druhého (variace $3$ ze $6$, tedy $\frac{6!}{(6-3)!}=6\cdot 5\cdot 4=120$ možností). Na závěr výsledky vynásobíme podle násobícího principu: $6\cdot 120=720$.
Dva a dva stejnou: Z úlohy g. už víme, že způsoby, jak kamarády rozdělit do dvou dvojic jsou celkem $3$. V druhé fázi dvojicím vybereme zmrzlinu. První příchuť bude pro dvojici, ve které se nachází Anna, druhá pro druhou dvojici (variace $2$ ze $6$, tedy $\frac{6!}{(6-2)!}=6\cdot 5=30$ možností). Podle násobícího principu dostáváme celkem $3\cdot 30=90$ možností.
Podle sčítacího principu dostaneme opět, že odpověď na otázku h. je
Na této úloze jsme si názorně ukázali, že může existovat více správných postupů řešení (a uvedeny dva ještě nejsou všechny možné). Vidíme ale taky, že se můžou výrazně lišit ve své složitosti.
Zmrzliny jsme už asi všichni přejedeni, ukážeme si tedy pár jiných příkladů.
Osm přátel se vydává na výlet autem. Pouze čtyři z nich mají řidičský průkaz. Pronajmou si dvě stejná auta, každé se čtyřmi sedadly. Kolika různými způsoby lze přátele rozdělit do aut, pokud v každém autě musí být někdo s řidičským průkazem, ale nerozlišujeme, kdo sedí na kterém sedadle ani kdo řídí?
Postup 1: Jediná nepřijatelná situace je, pokud by všichni řidiči seděli v jednom autě. Protože jsou řidiči právě čtyři, existuje jediná taková možnost. Podle sčítacího principu spočteme všechna možná rozdělení a odečteme tuto jednu nevyhovující možnost. Tvoříme tedy dvě čtveřice z osmi. Výběr jedné čtveřice odpovídá kombinacím $4$ z $8$. Ale proto, že na čtveřicích neexistuje žádné pořadí (nezáleží na tom, která byla „vybraná“ a která „zbývající“), podělíme kombinační číslo dvěma za dvě různá uspořádání. Dostaneme tedy, že všech rozdělení osmi přátel do dvou aut po čtyři, je
Nakonec, všech takových rozdělení, při kterých je v každém autě alespoň jeden řidič je
Postup 2: Řidiči můžou být do dvou aut rozděleni buď na $1$ a $3$ a nebo $2$ a $2$. V prvním případě máme $4$ (kombinace $1$ ze $4$) možnosti výběru samostatného řidiče a k němu $4$ (kombinace $3$ ze $4$) možnosti výběru posádky. To jsou nezávislé fáze procesu, tedy podle násobícího principu $4\cdot 4=16$ možností pro první případ. V druhém případě nejdřív rozdělíme řidiče do dvou dvojic, k čemuž máme $3$ možnosti (vysvětlení je podáno v Příkladě 12.4 g.). V druhé fázi pak vybereme posádku pro jednu dvojici řidičů, řekněme tu ve které je nejmladší řidič, čímž bude dána i posádka pro druhou dvojici řidičů. K tomu máme ${4\choose 2}=6$ možností. Pro druhý případ tedy opět podle násobícího principu dostáváme $3\cdot 6=18$ možností. Podle sčítacího principu tedy celkem opět dospějeme k výsledku
Pět dětí, Anna, Ben, Cyril, Dan a Ema, se skládají na koupi míče v ceně 25 korun.
Kolika různými způsoby se můžou složit, pokud přispívají v celých korunách a výše příspěvků nemusí být vyrovnaná (některé děti dokonce nemusí přispět vůbec)?
Co když nyní přidáme podmínku, že každé dítě musí přispět alespoň jednou korunou?
Zkuste si rozmyslet, jak bychom podobnou úvahou vyřešili úlohu například s podmínkou, že Anna přispěje přesně $5$ korun a Ben přispěje alespoň $3$ koruny, zatímco ostatní přispějí libovolně do celkové sumy $25$ korun.
Vybíráme 25 objektů (korun) z pěti kategorií: od Anny, od Bena, od Cyrila, od Dana a od Emy. Přitom ve výběru nezáleží na pořadí z jedné kategorie můžeme (dokonce někde i musíme) vybrat více objektů. Jde tedy o kombinace 25 z 5 s opakováním. Podrobně, každou možnost můžeme reprezentovat (vzájemně jednoznačně identifikovat s) posloupností symbolů $|$ a $\bullet$, kde $|$ oddělují příspěvky jednotlivých dětí a každý výskyt $\bullet$ představuje jednu korunu.
Každá taková posloupnost bude obsahovat symbol $|$ právě čtyřikrát a symbol $\bullet$ právě pětadvacetkrát. Například, posloupnost
odpovídá tomu, že Anna přispěla $6$ korunami, Ben $4$, Cyril $7$, Dan $0$ a Ema $8$ korunami.
Počet všech možných příspěvků tedy odpovídá počtu všech možných posloupností $|$ a $\bullet$ celkové délky $29$, ve kterých jsou právě $4$ symboly $|$ a $25$ symbolů $\bullet$. Výběrem pozic pro $\bullet$ (kombinace $25$ z $29$) dostaneme, že takových posloupností je
Mohli bychom použít sčítací princip a od celkového počtu odečíst všechny možnosti, kdy alespoň jedno dítě nepřispěje vůbec (můžete si vyzkoušet samostatně). Jednodušší je ale uvažovat následovně – každé dítě určitě přispěje alespoň jednou korunou, rozdělit tedy potřebujeme už jenom zbývajících $20$ korun, a to můžeme již udělat libovolně. Na těchto $20$ korun aplikujeme stejný postup jako v případě a. a dostaneme, že všech možností, kdy každé dítě přispěje alespoň jednou korunou je