Základní kombinatorická pravidla

Řešené příklady

Příklad 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.

Řešení

V tomto případě lze využít obě kombinatorická pravidla.

1) Řešení s využitím kombinatorického pravidla součinu

Na místě desítek může být libovolná z číslic 1, 2, …, 9, máme tedy devět možností pro výběr první číslice. Ke každé z nich existuje devět možností, jak vybrat číslici pro místo jednotek: může zde být číslice 0 a libovolná z číslic 1, 2, …, 9, která je různá od číslice stojící na místě desítek. Celkem lze tedy sestavit 9 · 9 = 81 uvažovaných dvojciferných čísel.

2) Řešení s využitím kombinatorického pravidla součtu

Všechna přirozená dvojciferná čísla lze rozdělit do dvou disjunktních skupin tak, že v první jsou dvojciferná čísla s různými číslicemi a ve druhé dvojciferná čísla se stejnými číslicemi.
Počet všech dvojciferných čísel je 90, počet dvojciferných čísel se stejnými číslicemi je 9 (jsou to čísla 11, 22, …, 99). Označíme-li hledaný počet dvojciferných čísel s různými číslicemi x, pak platí:
x + 9 = 90.
Odtud dostáváme, že je x = 81.

Příklad 2

Z místa A do místa B vedou čtyři turistické cesty, z místa B do 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.

Řešení

Nejprve určíme, kolika způsoby lze vybrat trasu z A do C: ke každému ze čtyř způsobů, jak dojít z A do B, existují tři způsoby, jak dojít z B do C. Trasu z A do C lze tedy vybrat 4 · 3, tj. dvanácti způsoby.

Nyní jde o to, kolika způsoby lze vybrat zpáteční trasu z C do A tak, aby v ní byla použita právě jedna cesta z těch, po kterých jsme už šli z A do C. Máme tedy dvě možnosti:

1. Po stejné cestě se budeme vracet z C do B. Potom z B do A půjdeme jinou cestou, než kterou jsme šli z A do B. V tomto případě lze vybrat zpáteční trasu z C do A třemi způsoby.
   
2. Z C do B půjdeme jinou cestou, než kterou jsme přišli, a z B do A půjdeme po stejné cestě, jako z A do B. V tomto případě lze vybrat zpáteční trasu z C do A dvěma způsoby.
   

Protože obě uvedené možnosti se navzájem vylučují a jiné nejsou, dostáváme (podle kombinatorického pravidla součtu), že celkový počet tras z C do A, které splňují dané podmínky, je roven pěti.
Ke každé z dvanácti tras z A do C existuje tedy pět tras z C do A, které splňují požadovanou podmínku. Pomocí kombinatorického pravidla součinu získáme výsledek úlohy: počet všech způsobů, kterými lze vybrat trasu z A do C a zpět tak, že z daných cest je právě jedna použita dvakrát, je 12 · 5 = 60.

Podobné úlohy

Určete počet způsobů, jimiž lze vybrat trasu
a) z A do C a zpět; [výsledek: 4 · 3 · 3 · 4 = 144]
b) z A do C a zpět tak, že z těchto sedmi cest není žádná použita dvakrát; [výsledek: 4 · 3 · 2 · 3 = 72]
c) z A do C a zpět tak, že z těchto sedmi cest jsou právě dvě použity dvakrát. [výsledek: 4 · 3 · 1 · 1 = 12]