Základné pravidlá počítania
Celá kombinatorika stojí na dvoch jednoduchých pravidlách. Pravidlo súčtu spočítava navzájom sa vylučujúce možnosti, pravidlo súčinu spája postupné nezávislé voľby.
Pravidlo súčtu
Ak môžeme úlohu spraviť spôsobom A (m možností) alebo spôsobom B (n možností) a tieto sa vylučujú (disjunktné), spolu je m + n možností.
Pravidlo súčinu
Ak úloha má dva postupné kroky — prvý s m voľbami, druhý (nezávisle) s n voľbami — celkový počet je m · n.
Slovíčko „alebo" spravidla vedie na súčet, slovíčko „a potom" na súčin. Príklad: jedálny lístok má 3 polievky a 4 hlavné jedlá. Obed = polievka a potom hlavné jedlo, teda 3 · 4 = 12 rôznych obedov. Ak by sme si však vyberali iba jedno jedlo (polievku alebo hlavné), je možností 3 + 4 = 7.
Pravidlo súčtu platí len pre disjunktné možnosti — keď sa žiadna možnosť nepočíta dvakrát. Ak sa prekrývajú, museli by sme prienik odpočítať (k tomu sa dostaneme pri inklúzii a exklúzii).
Vyber správnu odpoveď.
Variácie a permutácie
Keď záleží na poradí, hovoríme o usporiadanom výbere. Permutácie usporiadajú všetky prvky, variácie vyberú a usporiadajú len niektoré.
Permutácie
Počet usporiadaní všetkých n prvkov je P(n) = n!. Napr. 3! = 6 poradí troch kníh na poličke.
Variácie bez opakovania
Vyberáme a usporiadame k z n rôznych prvkov: V(n,k) = n!/(n−k)!. Žiadny prvok sa neopakuje.
Variácie s opakovaním
Každú z k pozícií vyberáme z n prvkov nezávisle, opakovanie dovolené: V′(n,k) = nᵏ.
Faktoriál n! = n · (n−1) · … · 2 · 1, pričom dohodou 0! = 1. Príklad variácií: koľkými spôsobmi obsadíme zlatú a striebornú medailu medzi 5 bežcami? Poradie rozlišuje miesta, opakovanie nie je možné, teda V(5,2) = 5·4 = 20. Keby šlo o dvojciferný kód z cifier 1–5 s povoleným opakovaním, dostali by sme 5² = 25.
Variácia bez opakovania je len „odrezaný" faktoriál: V(n,k) = n·(n−1)·…·(n−k+1) — presne k klesajúcich činiteľov. Permutácia je špeciálny prípad V(n,n) = n!.
Krokuj odvodenie počtu variácií pravidlom súčinu. Klikaj.
Vyber správnu odpoveď.
Kombinácie a binomická veta
Keď na poradí nezáleží, vyberáme kombináciu. Kombinačné číslo C(n,k) počíta k-prvkové podmnožiny n-prvkovej množiny.
Kombinačné číslo
C(n,k) = n!/(k!(n−k)!). Delíme cez k!, lebo každú k-ticu sme vo variáciách napočítali k!-krát (raz za každé poradie).
Pascalov trojuholník
C(n,k) = C(n−1,k−1) + C(n−1,k). Každé číslo je súčtom dvoch nad ním. Okraje sú C(n,0) = C(n,n) = 1.
Príklad: koľko dvojíc vyberieme z 5 ľudí na podanie rúk? Poradie netreba, takže C(5,2) = 5!/(2!·3!) = 120/12 = 10. Podobne C(6,2) = 720/(2·24) = 15. Symetria C(n,k) = C(n,n−k) hovorí, že vybrať k prvkov je to isté ako rozhodnúť, ktoré n−k necháme tak.
(a+b)ⁿ = ∑k=0n C(n,k) aⁿ⁻ᵏ bᵏ. Koeficienty sú práve čísla z n-tého riadku Pascalovho trojuholníka. Napr. (a+b)² = a² + 2ab + b² a (a+b)³ = a³ + 3a²b + 3ab² + b³.
| riadok n | koeficienty C(n,k) | súčet = 2ⁿ |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 1 | 2 |
| 2 | 1 2 1 | 4 |
| 3 | 1 3 3 1 | 8 |
| 4 | 1 4 6 4 1 | 16 |
Klikni a over si výsledok.
Vyber správnu odpoveď.
Počet zobrazení a podmnožín
Dva klasické výsledky, ktoré vyplynú priamo z pravidla súčinu: počet zobrazení medzi konečnými množinami a počet všetkých podmnožín.
Počet zobrazení
Zobrazenie z k-prvkovej množiny do n-prvkovej priradí každému z k vzorov jeden z n obrazov — nezávisle. Preto je takých zobrazení nᵏ.
Počet podmnožín
Podmnožinu n-prvkovej množiny určíme tak, že o každom prvku rozhodneme „je / nie je" — 2 možnosti na prvok. Preto je podmnožín 2ⁿ.
Príklad: množina {a, b, c} má 2³ = 8 podmnožín (vrátane prázdnej ∅ a celej množiny). A zobrazení z 3-prvkovej množiny do 2-prvkovej je tiež 2³ = 8 — každý z 3 vzorov má 2 možné obrazy.
Počet podmnožín vieme aj sčítať podľa veľkosti: ∑k=0n C(n,k) = 2ⁿ. To je presne binomická veta pre a = b = 1: (1+1)ⁿ = 2ⁿ. Pre {a,b,c}: 1 + 3 + 3 + 1 = 8.
Vyber správnu odpoveď.
Princíp inklúzie a exklúzie
Keď sa možnosti prekrývajú, samotné pravidlo súčtu by prienik napočítalo dvakrát. Princíp inklúzie a exklúzie to opraví — pripočítaj jednotlivé, odpočítaj prieniky.
Dve množiny
|A∪B| = |A| + |B| − |A∩B|. Prvky spoločné obom množinám by sme inak započítali dvojmo, preto prienik raz odpočítame.
Tri množiny
|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. Striedavo pripočítaj a odpočítaj.
Klasická úloha: koľko čísel od 1 do 100 je deliteľných 2 alebo 3? Nech A = deliteľné 2, B = deliteľné 3. Potom A∩B = deliteľné 6. Dosadíme |A| = ⌊100/2⌋ = 50, |B| = ⌊100/3⌋ = 33, |A∩B| = ⌊100/6⌋ = 16.
Číslo ako 6, 12, 18 … je deliteľné 2 aj 3 naraz. Bez odpočítania |A∩B| by sme každé z nich započítali dvakrát a výsledok by bol nadhodnotený.
Krokuj výpočet pomocou inklúzie a exklúzie. Klikaj.
Vyber správnu odpoveď.
Záverečný kvíz
Desať otázok cez celú kombinatoriku — od pravidiel počítania po inklúziu a exklúziu.
Otestuj sa cez celú tému.