🎲 Kombinatorika

Šatník a závody

O čem to je

Kolik různých oblečení vytvoříš ze 3 triček a 2 kalhot? Kolik je možných PIN kódů? Jaká je šance trefit Sportku? Kombinatorika je umění počítat možnosti, aniž bys je musel všechny vypsat.

Potřebuje ji pravděpodobnost, bezpečnost hesel, plánování rozvrhů i genetika.

Nové pojmy

Pravidlo součinuKdyž první volbu uděláš m způsoby a ke každé druhou n způsoby, je všech možností m · n.3 trička · 2 kalhoty = 6 oblečení.

Ověř si to na tečkách: řádky jsou trička, sloupce kalhoty. Každá tečka je jedno oblečení. Přidej čtvrté tričko – kolik oblečení přibude?

Faktoriál n!Součin n · (n − 1) · … · 2 · 1. Udává, kolika způsoby seřadíš n různých věcí. Dohodou 0! = 1.4! = 4 · 3 · 2 · 1 = 24; 5! = 120.
Kolika způsoby seřadíš 4 knihy na poličku?
Na první místo 4 možnosti, na druhé zbydou 3, pak 2, pak 1. 4 · 3 · 2 · 1 = 24.

Závody: záleží na pořadí

Z 5 běžců rozdáváš zlatou a stříbrnou medaili. Zlato může dostat 5 lidí, stříbro pak už jen 4. Celkem 5 · 4 = 20 možností. Petr zlato a Jana stříbro je jiný výsledek než naopak.

VariaceVýběr k věcí z n, kde záleží na pořadí, nic se neopakuje. V(n, k) = n · (n − 1) · … (k činitelů).Předseda a místopředseda z 5 lidí: 5 · 4 = 20.

Tým: na pořadí nezáleží

Teď z 5 lidí vybíráš dvojici do týmu. Petr + Jana = Jana + Petr – je to tentýž tým. Z 20 „medailových“ dvojic tedy počítáš každou dvakrát: 20 : 2 = 10.

Kombinace C(n, k)Výběr k věcí z n, kde nezáleží na pořadí. C(n, k) = V(n, k) / k! – vydělíš počtem pořadí, ve kterých jde stejnou skupinu seřadit. Čte se „n nad k“.C(5, 2) = 20 / 2 = 10.

Roztřiď situace: záleží na pořadí (variace), nebo ne (kombinace)?

Kolik podání rukou proběhne mezi 6 lidmi?
Podání je dvojice, pořadí nehraje roli: C(6, 2) = 6 · 5 / 2 = 15.
✗Podání rukou mezi 6 lidmi: 6 · 5 = 30.
✓C(6, 2) = 15

Když Adam podá ruku Báře, Bára ji podá Adamovi – to je jedno podání. Součin 6 · 5 počítá každé dvakrát.

Když se prvky smějí opakovat (PIN 0–9, čtyři místa), na každé místo je 10 možností: 10 · 10 · 10 · 10 = 10 000.

Pravidlo součinu: m · n. Seřazení n věcí: n!. Výběr, kde záleží na pořadí: variace. Kde nezáleží: kombinace C(n, k) = V(n, k)/k!.

Vzorce a rozhodování

O čem to je

U každé kombinatorické úlohy si polož dvě otázky: Záleží na pořadí? Mohou se prvky opakovat? Podle odpovědí vybereš vzorec. Celá kombinatorika je vlastně tahle rozhodovací tabulka.

Pomocí ní spočítáš počet hesel, výsledků losování nebo rozvržení lidí do skupin.

Nové pojmy

Faktoriáln! = n · (n − 1) · … · 1, 0! = 1.5! = 120.
PermutaceSeřazení všech n prvků. Počet P(n) = n!.Seřazení 4 knih: 24.
VariaceUspořádaný výběr k prvků z n bez opakování: V(n, k) = n! / (n − k)!.V(5, 3) = 5 · 4 · 3 = 60.
KombinaceNeuspořádaný výběr k prvků z n bez opakování: C(n, k) = n! / (k! · (n − k)!).C(10, 3) = 10 · 9 · 8 / 6 = 120.

Rozhodovací tabulka

Záleží na pořadíNezáleží na pořadí
bez opakovánívariace V(n, k) = n!/(n − k)!kombinace C(n, k) = n!/(k!(n − k)!)
s opakovánímvariace s opakováním nᵏ(na SŠ méně časté)
všechny prvkypermutace n!—
Zjisti, z kolika prvků vybíráš (n) a kolik (k).
Prohoď dva vybrané prvky. Je to jiný výsledek? → záleží na pořadí.
Smí se prvek použít víckrát? → s opakováním.
Vyber vzorec z tabulky a dosaď.

Řešené úlohy

Kolik trojciferných čísel sestavíš z číslic 1–5 bez opakování?
Záleží na pořadí (123 ≠ 321), bez opakování: V(5, 3) = 5 · 4 · 3 = 60.
Kolik je čtyřmístných PIN kódů z číslic 0–9?
Záleží na pořadí, číslice se opakovat smějí: 10⁴ = 10 000.
Tah Sportky (6 čísel ze 49): variace, nebo kombinace?
Na pořadí vytažení nezáleží, výhra závisí jen na tom, která čísla padla → kombinace C(49, 6).

Pravidlo součinu na tečkách: 4 předkrmy × 5 hlavních jídel = 20 menu. Nastav to a spočítej tečky.

Užitečné vlastnosti

  • C(n, k) = C(n, n − k): vybrat 2 ze 5, kdo pojedou, je totéž jako vybrat 3, kdo zůstanou.
  • Permutace s opakováním: slovo z písmen A, A, B, B: 4! / (2! · 2!) = 24 / 4 = 6 (prohození stejných písmen nic nemění).
  • 0! = 1, aby vzorce fungovaly i pro k = 0 nebo k = n.
✗Z 5 lidí vybírám předsedu a místopředsedu: C(5, 2) = 10.
✓V(5, 2) = 20

Funkce jsou různé – Petr předseda a Jana místopředsedkyně je jiný výsledek než naopak. Záleží na pořadí, takže variace.

Záleží na pořadí → variace (n!/(n − k)!), s opakováním nᵏ. Nezáleží → kombinace C(n, k) = n!/(k!(n − k)!). Seřazení všech → n!.
🌀Geometrická posloupnost a řady🔺Binomická věta