Zmiešané úlohy a Pascalov trojuholník

Vieš už päť nástrojov: pravidlo súčinu, permutácie, variácie bez opakovania, variácie s opakovaním a kombinácie. Pri skutočnej úlohe nikto nenapíše, ktorý z nich použiť. Táto lekcia ti dá postup, ako to rozpoznať, a ukáže dve rozšírenia navyše.

Tri otázky na rozpoznanie typu

Pri každej úlohe si polož tieto otázky v tomto poradí:

1. Vyberám všetky prvky a len ich usporadúvam? Ak áno, ide o permutácie: $P(n) = n!$.
2. Záleží na poradí vybraných prvkov? Ak nie, ide o kombinácie: $\binom{n}{k}$.
3. Ak záleží, môžu sa prvky opakovať? Ak áno, $V'(k, n) = n^k$. Ak nie, $V(k, n) = \dfrac{n!}{(n-k)!}$.

Ak sa úloha skladá z viacerých samostatných častí, použi pravidlá z 1. lekcie: časti po sebe sa násobia, alternatívy sa sčítajú.

Permutácie s opakovaním (anagramy)

Koľko rôznych „slov“ (aj nezmyselných) vznikne preusporiadaním písmen slova MAMA? Nie je to $4! = 24$, lebo písmená sa opakujú: keď vymeníš dve M, slovo sa nezmení.

V $4! = 24$ usporiadaniach sa každé slovo objaví $2! \cdot 2! = 4$-krát (poradie dvoch M a poradie dvoch A). Preto

Všeobecne: ak z $n$ prvkov je $n_1$ rovnakých jedného druhu, $n_2$ rovnakých druhého druhu a tak ďalej, tak počet rôznych usporiadaní je

Pascalov trojuholník

Kombinačné čísla sa dajú usporiadať do trojuholníka. Riadok číslo $n$ (začína sa od 0) obsahuje čísla $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$:

Každé číslo (okrem jednotiek na okrajoch) je súčet dvoch čísel nad ním. Napríklad $\binom{6}{2} = \binom{5}{1} + \binom{5}{2} = 5 + 10 = 15$. Vo všeobecnosti $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

Riadok je súmerný (to je vlastnosť $\binom{n}{k} = \binom{n}{n-k}$) a súčet čísel v riadku $n$ je $2^n$. Má to aj význam: $\binom{n}{k}$ je počet $k$-prvkových podmnožín $n$-prvkovej množiny, takže súčet je počet všetkých podmnožín, vrátane prázdnej. Pre $n = 4$ je to $1 + 4 + 6 + 4 + 1 = 16 = 2^4$.

Hra: priraď úlohu k výsledku — najprv sa spýtaj tri otázky: všetky? poradie? opakovanie?

Zapamätaj si

• Tri otázky: vyberám všetky? záleží na poradí? môžu sa prvky opakovať?
• $P(n) = n!$; $V(k, n) = \dfrac{n!}{(n-k)!}$; $V'(k, n) = n^k$; $C(k, n) = \binom{n}{k}$.
• Anagramy: $P'(n_1, \dots, n_r) = \dfrac{n!}{n_1!\,\dots\,n_r!}$, deliš faktoriálom počtu každého opakujúceho sa prvku.
• Pascalov trojuholník: číslo = súčet dvoch nad ním, súčet riadku $n$ je $2^n$.
• Viac častí po sebe násobíš, alternatívy sčítaš.