Kombinatorika

Prvky sa neopakujú Prvky sa môžu opakovať

Nezáleží na poradí prvkov Kombinácie bez opakovania Kombinácie s opakovaním

Záleží na poradí prvkov Variácie bez opakovania Variácie s opakovaním

Ak $n$ je prirodzene číslo, symbolom $\small  M_n$ označujeme akúkoľvek $n$- prvkovú množinu. V ďalšom spravidla budeme predpokladať, že prvkami množiny $M_n$ sú čísla $1,2, \cdot \cdot \cdot ,n$ (niekedy to zase budú písmená $a_1,a_2, \cdot \cdot \cdot ,a_n$.

Každá podmnožina $\small  M_r$ množiny $\small  M_n$ sa nazýva kombinácia množiny $\small  M_n$. Ak $\small  M_r$ pozostáva z $r$ prvkov, tak ju
nazývame $r$-kombináciou.

Pri tvorení kombinácií nezáleží na poradí prvkov! Napríklad trojice 123 a 321 predstavujú tú istú kombináciu. Prvky v kombinácii obyčajne usporadúvame v tom poradí ako v základnej množine $M_n$.

Počet všetkých $r-$ kombinácií množiny $\small  M_n$ budeme označovať $\small  C(n,r)$ alebo  $\binom{n}{r}$ a nazývame kombinačným číslom alebo tiež binomickým koeficientom. Zovšeobecnením niektorých vyššie uvedených úvah dostaneme nasledujúce tvrdenie.

Nájdite všetky kombinácie množiny $\small  M_5= \lbrace{1,2,3,4,5}\rbrace$.

Riešenie.

1. Zrejme, každá množina má jedinú $0 -$ kombináciu (je ňou prázdna množina ∅).
2. Podľa definície $1 -$ kombinácie sú všetky jednoprvkové podmnožiny množiny $\small  M_5$. Sú to množiny

Nájdite všetky kombinácie množiny $\small  M_5= \lbrace{1,2,3,4,5}\rbrace$.

Riešenie.

1. Zrejme, každá množina má jedinú $0 -$ kombináciu (je ňou prázdna množina ∅).
2. Podľa definície $\small  1 -$ kombinácie sú všetky jednoprvkové podmnožiny množiny $\small  M_5$. Sú to množiny: $\small  \lbrace{1}\rbrace, \lbrace{2}\rbrace, \lbrace{3}\rbrace, \lbrace{4}\rbrace, \lbrace{5}\rbrace$. Pre kombinácie nepoužívame tento množinový zápis, ale ich píšeme jednoducho: $\small  1,2,3,4,5$. Ich počet je 5.
3. $\small  2 -$ kombinácie utvoríme tak, že ku každej $\small  1 -$ kombinácii a pripojíme vpravo po jednom všetky prvky, ktoré sa v množine $\small  M_5$ nachádzajú vpravo od $a$. Postup tvorby Tu. Ich počet je 10.
4. Obdobne získame všetky $\small  3 -$ kombinácie. Ku každej $\small  2 -$ kombinácii $ab$ pripojíme po jednom každý prvok, ktorý leží v $\small  M_5$ vpravo od $b$ (ak taký prvok existuje) . Dostaneme tieto $\small  3 -$ kombinácie: $\small  123, 124, 125, 134, 135, 145, 234, 235, 245, 345$. Ich počet je 10. 
5. Podobne postupujeme pri tvorbe $\small  4 -$ kombinácií. Ich počet je 5 a sú to $\small  1234, 1235, 1245, 1345, 2345$. 
6. Existuje len  jedna $\small  5 -$ kombinácia $\small  12345$.
7. Zrejme, množina $\small  M_5$ nemá nijakú $\small  6 -$ kombináciu.

Kombinácie $\small  K$ a $\small  L$ množiny $\small  M_n$ sa nazývajú navzájom doplnkové ak platí: $\small  K ∩ L = ∅$ a $\small  K \cup L=M_n$ .

Veta: Počet $r -$ kombinácií množiny $\small  M_n$ sa rovná počtu jej $(n-r)-$ kombinácií: $\small  C(n, r)=C(n, n - r)$ .

Dôkaz tvrdenia:     Zrejme zobrazenie  $\phi$ je bijekcia, preto množiny $\small  A(r)$ a $\small  A(n-r)$ majú rovnaký počet prvkov. Tým je dôkaz ukončený.

Príklad.
Pri výťahu, do ktorého môžu nastúpiť najviac tri osoby, stojí 5 osôb. Označme je $a,b,c,d,e$. Zostavte všetky trojice osôb, ktoré môžu nastúpiť do výťahu.
Riešenie:
Otvorte si zadanie Tu.

Tvrdenie.
Nech $x$ je pevný prvok množiny $\small  M_n$ a nech $r \geq 1$. Počet $r -$ kombinácií množiny $\small  M_n$, ktoré 
$\ast$ prvok $x$ obsahujú sa rovná $\small  C(n-1,r-1)$
$\ast$ prvok $x$ neobsahujú sa rovná   $\small  C(n-1,r)$

Dôkaz.                                   

Dôsledok.
Ak $1 \leq r \leq n$, tak platí    $\small  C(n,r )=C(n-1,r-1 )+C(n-1,r )$.

Poznámka.
Rovnosť uvedená v dôsledku je vlastne rekurentným vzťahom. Počet $r$-kombinácií $n$-prvkovej množiny je vyjadrený pomocou počtu kombinácií $(n-1)$-prvkovej množiny. Stačí začať s 1-prvkovou množinou, pre ktorú platí:
$\small  C(1,0 )+C(1,1 )= 1+1=2\stackrel{dosledok}{=}C(2,1)$
a postupne určiť počet kombinácií vyššieho rádu. Toto nás privádza k myšlienke pokúsiť sa o explicitné vyjadrenie kombinačných čísel $\small  C(n,r)$.

Ukázali sme, že platí $\small  \binom {n} {r} = \binom {n-1} {r-1} + \binom {n-1} {r}$ pre $1 \leq r \leq n$.

Pre 1-prvkovú množinu zrejme platí:
$\small  \binom {1} {0} + \binom {1} {1} = 1+1=2\stackrel{dosledok}{=} \binom {2} {1}$
opäť použijeme tvrdenie uvedené v dôsledku teraz pre 2-prvkovú množinu a dostaneme:
$\small  \binom {2} {0} + \binom {2} {1} = 1+2=3\stackrel{dosledok}{=} \binom {3} {1}$
a zároveň pre 2-prvkovú množinu tiež platí:
$\small  \binom {2} {1} + \binom {2} {2} = 2+1=3\stackrel{dosledok}{=} \binom {3} {2}$.
Takto by sme mohli postupovať pre väčšie hodnoty $n$. Napríklad už poznáme hodnoty
$\small  \binom {3} {0} = \binom {3} {3} =1; \binom {3} {1} = \binom {3} {2} =3$
preto ľahko spočítame hodnoty pre $n=4$. Ak tieto výpočty budeme zapisovať do trojuholníkovej schémy, tak dostaneme známy Pascalov trojuholník pre kombinačné čísla.
          

1. Čísla na "odvesnách" Pascalovho trojuholníka sú zrejme rovné 1.
2. Každé číslo vo vnútri Pascalovho trojuholníka sa rovná súčtu dvoch čísel, ktoré sa nachádzajú nad ním vpravo a vľavo.
3. Čísla v $n$-tom riadku možno určiť pomocou vzťahu $\small  \binom {n} {r} = \binom {n-1} {r-1} + \binom {n-1} {r}$.

Symbolom $n!$ označujeme súčin prvých $n$ prirodzených čísel. Nazývame ho faktoriál čísla $n$.

Tvrdenie. Pre kombinačné číslo platí: $\small   \binom {n} {r} = \frac{n!}{(n-r)!\; r!}$

Riešené úlohy.

Úloha 1: V priestore máme 7 rovín, z ktorých sú tri navzájom rovnobežné a štyri prechádzajú jednou priamkou. Koľko priesečníc vytvoria?
Úloha 2: Skúšajúci má pripravených 20 príkladov z aritmetiky a 30 z geometrie. Na písomku chce dať:

• Variant A: 3 aritmetické a 2 geometrické príklady
• Variant B: 1 aritmetický a 2 geometrické príklady

Koľko má možností zostavenia rôznych zadaní?

Predpokladáme, že študentom sú známe vzorce pre mocniny dvojčlena $(a+b)^n$ ak $n=2$ resp. pre $n=3$. Pre umocňovanie s vyšším exponentom odvodíme vzorce pomocou tzv. binomickej vety, ktorú teraz dokážeme.

Binomická veta
Nech $x,y$ sú ľubovoľné reálne čísla a nech $n$ je prirodzené číslo, potom
$(a+b)^n = {n \choose 0}a^n b^0 + {n \choose 1}a^{n-1}b^1 + {n \choose 2}a^{n-2}b^2 + \cdots + {n \choose n-1}a^1 b^{n-1} + {n \choose n}a^0 b^n,$ 

Pre $n=2$ resp. $n=3$ dostaneme známe vzorce:
$(a+b)^2= \binom {2} {0} a^2 b^0 +\binom {2} {1} a^1 b^1+\binom {2} {2} a^0 b^2=a^2+2ab+b^2$
$(a+b)^3= \binom {3} {0} a^3 b^0 +\binom {3} {1} a^2 b^1+\binom {3} {2} a^1 b^2+\binom {3} {3} a^0 b^3 = a^3+3a^2b+3ab^2+ b^3$

 Dôkaz vety.
Pri dôkaze binomickej vety vychádzame z toho, že v súčine
$(a+b)(a+b) \cdot \cdot \cdot (a+b)$
člen
$a^{n-k} b^k$
dostaneme tak, že z dvojčlenov $(a+b)$ vyberieme $(n-k)$-krát reálne číslo $a$ a potom $k$-krát reálne číslo $b$. To je možné práve
$C(n,n-k)=C(n,k)$
spôsobmi, čím je dôkaz ukončený. Dôkaz binomickej vety môžeme urobiť aj pomocou úplnej matematickej indukcie.

Poznámky.

1. V binomickej vete sa objavujú kombinačné čísla. Preto ich niekedy nazývame binomické koeficienty.
2. Ak v binomickej vete položíme $a=1,b=1$ dostaneme identitu
   $\sum_{k=0}^{n}{ \binom {n} {k} =2^n}$.
3. Počet všetkých kombinácií (podmnožín) množiny $M_n$ sa rovná $2^n$.
4. Inú identitu dostaneme, ak v binomickej vete kladieme $a = -1,b = 1$
   $\sum_{k=0}^{n}{ (-1)^k\binom {n} {k} =0}$.

Príklad. Využitím binomickej vety vypočítajte $1,2^4$.

Definícia.
Nech $M_n$ označujeme akúkoľvek $n$-prvkovú množinu. Permutáciou množiny $\small  M_n$ nazývame jej bijektívne zobrazenie na seba.

Napríklad zobrazenie $\small   f: Z_4\rightarrow Z_4$ dané predpisom:
$\small   f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1$
je bijekcia množiny $\small   Z_4=\left\{1, 2, 3, 4\right\}$ na seba. Takúto permutáciu budeme symbolicky zapisovať pomocou matice
$\small   \left(\begin{matrix}1\\2\ \\\end{matrix}\begin{matrix}2\\3\\\end{matrix}\begin{matrix}3\\\ 4\ \\\end{matrix}\begin{matrix}4\\1\\\end{matrix}\right)$
alebo jednoducho ako postupnosť
$\small   \mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1}$.

Príklad.
Nájdite všetky permutácie ľubovoľnej štvorprvkovej množiny $\small   M_4=\left\{a,b,c,d\right\}$.
Riešenie.
Nech $\small   f: M_4\rightarrow M_4$ je bijekcia. Potom obraz prvku a môže nadobúdať štyri rôzne hodnoty:
$\small  f\left(a\right)=a,\ f\left(a\right)=b,\ f\left(a\right)=c,\ f\left(a\right)=d$.
Ak $\small   f\left(a\right)=a$, tak obraz prvku $\small   b$ môže nadobúdať tri rôzne hodnoty
$\small   f\left(b\right)=b,\ f\left(b\right)=c,\ f\left(b\right)=d$
Ak už $\small   \ f\left(b\right)=b$, tak obraz prvku $\small   c$ môže nadobúdať dve rôzne hodnoty atď. Schematicky to môžeme znázorniť nasledovne

Pre $\small   f\left(a\right)=a$ sme dostali permutácie $\small   abcd, abdc, acbd, acdb,adcb,adbc$. Podobne budeme postupovať pre $\small   f\left(a\right)=b, f\left(a\right)=c, f\left(a\right)=d$. Všetky permutácie prehľadne zapíšeme pomocou nasledujúcej tabuľky.

Na základe postupu použitého v predchádzajúcom príklade môžeme dokázať tvrdenie uvedené vo vete 9, v ktorej je uvedený vzorec pre určenie počtu všetkých permutácii ľubovoľnej množiny $\small   M_n$.

Tvrdenie. 
Pre počet permutácií $\small   P\left(M_n\right)$ množiny $\small   M_n$ platí vzťah $\small   P(M_n)=n!$
Dôkaz tohto tvrdenia môžeme ľahko urobiť ak využijeme kombinatorické pravidlo súčinu. 

Kombinatorické pravidlo súčinu
Nech $\small  A_1,A_2,\ldots,A_n$ sú množiny majúce po rade $\small  a_1,a_2,\ldots,a_n$ prvkov. Potom počet usporiadaných $\small  n$-tíc, ktorých prvý prvok je z množiny $\small  A_1$, druhý z množiny $\small  A_2$ a $n$-tý z množiny $\small  A_n$ je rovný súčinu $\small  a_1a_2\ldots a_n$.

Príklad 1.
V košíku je 12 jabĺk a 10 hrušiek. Peter si má z neho vybrať buď jablko, alebo hrušku tak, aby Viera, ktorá si po ňom vyberie jedno jablko a jednu hrušku, mala čo najväčšiu možnosť výberu. Určte, čo si má vybrať Peter.
Riešenie.
Peter má pri výbere dve možnosti. Buď si vyberie jablko, alebo hrušku. Otvorte si tabuľu Tu.

Príklad 2.
Karol má červenú, modrú, žltú a zelenú kravatu. Ďalej má červenú, modrú a zelenú košeľu. Koľkými spôsobmi si môže obliecť oboje, aby nemal košeľu a kravatu rovnakej farby?
Riešenie.
Najskôr spočítajte koľko možností je nevhodných - rovnakej farby kravata aj košeľa. Potom použite kombinatorické pravidlo súčinu. Otvorte si tabuľu Tu.

Príklad 3.
Koľko rôznych usporiadaných dvojíc čísel môžeme dostať, keď hodíme dvakrát kockou s jedným až šiestimi okami na jednotlivých stenách?
Riešenie.
V prvom hode môže padnúť jedno zo šiestich čísel. To znamená, že máme 6 možností (6 rôznych hodnôt na vrchnej strane kocky).
Ku každej hodnote môže v druhom hode opäť padnúť jedno zo šiestich čísel, tj opäť 6 možností.
Počet rôznych dvojíc je teda 6 x 6 = 36." Tabuľa

Príklad 4.
Určite počet všetkých trojciferných prirodzených čísel,
a) v ktorých dekadickom zápise sa každá číslica vyskytuje najviac raz;
b) v ktorých dekadickom zápise sa nejaká číslica vyskytuje aspoň dvakrát
Riešenie.
    a) možnosti pre 
       -  prvú číslicu: 1 až 9 → 9 možností;
       -  druhú číslicu: 0 až 9, ale bez tej číslice, ktorá bola vybraná pre prvú číslicu → 10 − 1 = 9 možností;
       -  tretiu číslicu: 0 až 9, ale bez číslic, ktoré boli vybrané pre prvú a druhú číslicu → 10 − 2 = 8 možností.
      Podľa kombinatorického pravidla súčinu je teda celkom 9 ⋅ 9 ⋅ 8 = 648 takýchto čísel.

   b) Všetkých trojciferných čísel je 900 (čísla 100 až 999), z toho čísel, v ktorých dekadickom zápise sa každá číslica vyskytuje najviac raz, je 648 – viď prípad a). Zostáva teda 900-648 čísel, v ktorých dekadickom zápise sa nejaká číslica opakuje aspoň dvakrát."

Definícia.
$r$-členná usporiadaná skupina z $n$ prvkov taká, že každý prvok sa v nej vyskytuje najviac jedenkrát sa nazýva
variácia $r$ triedy z $n$ prvkov.
Počet všetkých $r$-variácií z $n$ prvkov označujeme symbolom $\small  V(n,r)$.

Tvrdenie.
Pre počet všetkých $r$-variácií množiny $\small   M_n$ platí vzťah 
$\small   V(n,r) \large{ = \frac{n!}{(n-r)!}}$

Z prvkov množiny $\small  M_n$ je možné vytvoriť skupiny po $r$ prvkov najvoľnejšie tak, že na každé miesto v tejto skupine umiestnime ľubovoľný prvok množiny $\small  M_n$ . Takto vzniknutým skupinám budeme hovoriť variácie s opakovaním. V závere predchádzajúcej kapitoly sme v rámci cvičenia vytvárali takéto skupiny - farebné zostavy. Farby sa mohli opakovať a zároveň záležalo na poradí.

Definícia.
Usporiadaná $r$-tica prvkov množiny $\small M_n$ sa nazýva $r$-variácia s opakovaním množiny $\small M_n$ . Počet všetkých $r$-variácií s opakovaním množiny $\small M_n$ budeme označovať symbolom $\small V'(n,r)$.

Príklad.
Utvorte všetky 3-variácie s opakovaním množiny $\small M_2=\left\{1,\ 2\right\}$.
Riešenie.
Postupne vytvárajme $1,\; 2 ,\; 3$-variácie s opakovaním množiny $\small M_2$ .

• $1$-variácie s opakovaním množiny $\small M_2$ sú dve: $1,\; 2$. Ich počet je $\small V'(2,1)=2=2^1$ .
• $2$-variácie s opakovaním množiny $\small M_2$ sú štyri: $11, \;12, \;21, \;22$. Ich počet je $\small V'(2,2)=4=2^2$
• $3$-variácii s opakovaním množiny $\small M_2$ je osem:$111,\; 112,\; 121,\; 122,\; 211,\; 212,\; 221,\; 222$. Pre ich počet platí:$\small V'(2,3)=8=2^3$ .

Veta.
Pre počet všetkých $r$-variácií s opakovaním množiny $\small M_n$ platí vzťah $\small V'(n,r)=n^r$.

Dôkaz.
Použitím matematickej indukcie. Pre $r=1,2$ je tvrdenie pravdivé, presvedčte sa o tom dosadením do vzťahu $\small V'(n,r)=n^r$. Predpokladajme, že tvrdenie platí pre $r-1$. Teda 
$\small V'(n,r-1)=n^{r-1}$
Všetky usporiadané $r$-tice s opakovaním množiny $\small M_n$ možno vytvoriť z$(r-1)$-tíc tak, že ku každej dodáme na koniec po jednom každý prvok množiny $\small M_n$ . Preto z každej $(r-1)$-tice získame $n$ rôznych $r$-tíc. Využitím indukčného predpokladu dostaneme
$\small V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r$.

Urobte dôkaz využitím kombinačného pravidla súčinu.

Definícia.
Permutácia s opakovaním z $n$ prvkov je usporiadaná $k$-tica zostavená z týchto $n$ prvkov taká, že každý prvok sa v nej vyskytuje aspoň raz.

Vzťah medzi $k$ a $n$ je nasledujúci:
Prirodzené číslo $n$ udáva počet rôznych prvkov. Jednotlivé prvky sa môžu opakovať. Je zvykom označovať

• počet opakovaní prvého prvku $k_1$
• počet opakovaní druhého prvku $k_2$
• a tak ďalej, až
• počet opakovaní posledného prvku $k_n$

Prirodzené číslo $k$ označuje počet všetkých prvkov, ktorých rôzne poradie skúmame, preto platí $k = k_1 + k_2 + ... + k_n$.

Príklad.
Tri modré kocky a 2 červené kocky ukladáme do stĺpcov. Zrejme záleží na poradí, pričom modrá kocka sa opakuje 3-krát a červená kocka sa opakuje 2-krát. Jedná sa o permutácie s opakovaním z dvoch prvkov/kategórií, kde prvý prvok sa opakuje 3x, druhý 2x.

1. $n$ počet všetkých kociek: 3 modré + 2 červené kocky
2. $k_1 = 3, k_2 = 2$
3. $n = 5 = k_1 + k_2 = 3 + 2$.

Skúste vypísať všetky permutácie, ktoré vyhovujú zadaniu. Poukladajte najskôr červené (dva) štvorčeky do zvislého radu, ktorý má 5 políčok.

Dostaneme 10 rôznych uložení 3 modrých a dvoch červených kociek.

Tvrdenie.
Počet permutácií s opakovaním z $n$ prvkov, v ktorých sa jednotlivé prvky opakujú $\small k_1,k_2, \cdot \cdot \cdot ,k_n$-krát, je rovný číslu 
$\small  P'(k_1,k_2, \cdot \cdot \cdot ,k_n)=$ $\frac{ (k_1+k_2+ \cdot \cdot \cdot +k_n)!}{k_1!k_2! \cdot \cdot \cdot k_n!}$

Dôkaz.
Podobne ako v predchádzajúcom príklade určíme, koľkými spôsobmi by bolo možné prvky/štvorčeky zoradiť. Celkom je prvkov $\small k_1+k_2+...+k_n$, počet všetkých ich zoradení (permutácií) je preto 
$\small P(k_1+k_2+...+k_n)=( k_1+k_2+...+k_n)!$.
Pretože prvky nie sú všetky navzájom rôzne, budú sa niektoré v poradí opakovať:
     Prvý prvok sa bude opakovať $\small k_1!$.
     ...
    Pre každý prvok $\small i$-tý je počet opakovaní rovný $\small k_i!$. Výsledný počet poradí všetkých pasteliek je preto
$\small P'(k_1,k_2, \cdot \cdot \cdot ,k_n)=$ $\frac{ (k_1+k_2+ \cdot \cdot \cdot +k_n)!}{k_1!k_2! \cdot \cdot \cdot k_n!}$

Určte, koľkými spôsobmi je možné poukladať do radu 2 modré a 2 červené kocky.

Pri riešení využite priložený applet

1. Použijeme vzorec pre počet permutácií z $n$ prvkov, v ktorých sa jednotlivé prvky opakujú $k_1,k_2,...,k_n$-krát. Platí
   $\small P'(k_1,k_2,...,k_n)=\large{ \frac{(k_1+k_2+...+k_n)!}{k_1!k_2!...k_n!}}$.
2. Po dosadení do vzorca pre počet permutácií z 2 prvkov s opakovaním platí
   $\small k_1=k_2=2 \; \& \; P'(2,2)=\large{ \frac{(2+2)!}{2!2!} = \frac{24}{4} =6}$

Príklad 1: Koľko trojciferných čísel môžeme vytvoriť z číslic $\small 1,2,3,4,5$, ak sa žiadna číslica neopakuje?

Príklad 2: Koľko rôznych jedno až štvorciferných čísel môžeme vytvoriť z cifier $\small 0, 1, 2, 3$?

Príklad 3: K vyhotoveniu vlajky, ktorá má byť zložená z troch rôznofarebných vodorovných pruhov, sú k dispozícii látky farby modrej, červenej, zelenej, bielej a žltej.

1. Určte počet vlajok, ktoré možno z látok týchto 5 farieb zostaviť.
2. Koľko ich má v strede modrý pruh?
3. Koľko ich má (kdekoľvek) biely pruh?
4. Koľko ich nemá uprostred červený pruh?

Vytváranie farebnej zostavy/vlajky pomocou appletu. Zvoľte farbu a priraďte ju niektorému štvorčeku mriežky.

Príklad 4: Vytvorte všetky zostavy, ktoré sú zložené z 3 štvorčekov siete. Použite len 3 farby - modrú, červenú a žltú.

Príklad 5: Určite, koľkými spôsobmi sa v šesťmiestnej lavici môže posadiť šesť chlapcov, ak

1. dvaja chcú sedieť vedľa seba;
2. dvaja chcú sedieť vedľa seba a tretí chcú sedieť na kraji.

Riešenie.

1. Dvaja chcú sedieť vedľa seba:
   Označme týchto dvoch chlapcov ako "blok" (napr. A a B). Tento blok môžeme umiestniť na 5 rôznych miest: (1-2), (2-3), ..., (5-6).
   V rámci bloku môžu byť usporiadaní 2 spôsobmi (AB alebo BA).
   Zostávajúcich 4 chlapcov môžeme usporiadať vo zvyšných 4 miestach ako 4! spôsobmi.
   Výpočet:
   Počet spôsobov = 5 × 2 × 4! = 5 × 2 × 24 = 240
2. Dvaja chcú sedieť vedľa seba a tretí chce sedieť na kraji:
   Nech chcú dvaja sedieť spolu (označme ich ako A a B) a tretí (C) chce sedieť na jednom z krajov (miesto 1 alebo 6).
   Postup:
   • C môže sedieť na 2 miestach (1 alebo 6).
   • Po zafixovaní C ostáva 5 miest, do ktorých chceme umiestniť blok AB vedľa seba.
   • Pre dané miesto C musíme spočítať, na koľko spôsobov vieme umiestniť blok AB bez kolízie s C, a zvyšných 3 chlapcov rozmiestniť do voľných miest.
   Riešme najprv pre C na mieste 1:
   • Voľné miesta: 2,3,4,5,6
   • Možné pozície bloku AB: (2-3), (3-4), (4-5), (5-6) → 4 pozície
   • AB v bloku: 2 usporiadania
   • Ostávajú 3 chlapci → 3! = 6 spôsobov
   • Počet kombinácií pre C na kraji = 4 × 2 × 6 = 48
   To isté platí pre C na mieste 6:
   
   • Voľné miesta: 1,2,3,4,5
   • Možné pozície bloku AB: (1-2), (2-3), (3-4), (4-5)
   • Rovnaký počet kombinácií: 4 × 2 × 6 = 48
   Spolu: 48 + 48 = 96
3. Riešené príklay - TeX

Teória partícií predstavuje jednu z najpozoruhodnejších častí klasickej kombinatoriky. V tomto odseku ukážeme len niekoľko zaujímavých výsledkov.

Partícia prirodzeného čísla $n$ sa nazýva vyjadrenie čísla $n$ v tvare súčtu nenulových prirodzených čísel 
$n=a_1+a_2+ \cdot \cdot \cdot +a_r$.

Obyčajne sa pri štúdiu partícií rozlišujú dva prípady. Partície, v ktorých 

1. záleží na poradí sčítancov $a_1,a_2, \cdot \cdot \cdot ,a_r$, napríklad partície $2+3 ,\; \;3+2$ čísla $6$ budeme považovať za rôzne
2. nezáleží na poradí sčítancov $a_1,a_2, \cdot \cdot \cdot ,a_r$, napríklad partície $1+2+3 ,\; \;3+1+2$ budeme považovať totožné

Budeme skúmať len prvý prípad. Dve partície líšiace sa len poradím sčítancov považujeme za rôzne. Označme počet všetkých takýchto partícií čísla $n$ pozostávajúcich z presne $r$ sčítancov $(r \leq n)$ symbolom
$\small  P(n,r)$.
V ďalšom sa budeme snažiť určiť číslo $\small  P(n,r)$.

Nakreslime na priamke vedľa seba $n$ bodov. Medzi nimi máme $(n-1)$ medzier a zvoľme z nich $(r-1)$ medzier. Táto voľba sa dá zrejme uskutočniť
$\small  C(n-1,r-1)$
spôsobmi. Vložme do nich zvislé čiarky. Napr.: Rozdeliť číslo 6 na 4 časti znamená zvoliť 3 medzery z 5.

Tým sa pôvodných $n$ bodov rozdelí na $r$ častí, pričom rôznym voľbám $(r-1)$ medzier zodpovedajú rôzne rozdelenia (aspoň čo do poradia ), čiže partícií čísla $n$ na $r$ častí. Dokázali sme vlastne vetu o počte partícií.

Veta o počte partícií.
Počet partícií (navzájom rôznych aspoň poradím) čísla $n$ na $r$ častí sa rovná
$\small  P(n,r)=C(n-1,r-1)$

Príklad. Rozklad čísla $\small  6$ na $\small  3$ nenulových sčítancov. Vypíšte všetky rozklady.
Riešenie. Číslo $\small  6$ má $\small  P(6,3)=C(6-1,3-1)=C(5,2)=10$ partícií z troch sčítancov. Sú to partície:
$\small  1 + 2 + 3, \; \;2 + 1 + 3,\; \; 1 + 3 + 2,\; \; 3 + 1 + 2,\; \; 2 + 3 + 1,\; \;3 + 2 + 1$
$\small  1 + 1 + 4, \; \; 1 + 4 + 1, \; \; 4 + 1 + 1, \; \; 2 + 2 + 2$.  Otvorte si applet Tu.

Teraz už ľahko určíme počet všetkých rôznych (aspoň) poradím partícií čísla $n$.

Ak si to číslo označíme symbolom $\small  P(n)$, tak zrejme platí
$\small  P(n)=P(n,1)+P(n,2)+ \cdot \cdot \cdot +P(n,n)$.
Použitím vety a identity
$\sum_{k=0}^{n}{ \binom {n} {k} =2n}$
potom dostávame
$\small  P(n) =2n-1$.

Úloha.
Koľkými spôsobmi môžeme urobiť nákup, ktorý pozostáva zo 5 litrov mlieka, ak v obchode majú tri druhy mlieka -nízkotučné, polotučné a plnotučné. V nákupe musia byť zastúpené všetky druhy mlieka. Podmienka: nákup musí obsahovať z každého druhu aspoň jeden liter mlieka. Vypíšte všetky možnosti nákupu.
Návod.

• Označme si nákup ako usporiadanú trojicu prirodzených čísel $(n,p,t)$, kde jednotlivé čísla predstavujú koľko litrov sme nakúpili z daného druhu mlieka.
• Napríklad trojica $\small  (1,1,2)$ predstavuje nákup 1 litra nízkotučného mlieka a 1 litre polotučného a 2 litre plnotučného mlieka, preto nespĺňa podmienku nákupu.
• Trojica $\small  (1,2,2)$ predstavuje nákup 1 litra nízkotučného mlieka a 2 litre polotučného a 2 litre plnotučného mlieka, preto spĺňa podmienku nákupu.
• Trojica $\small  (3,2,0)$ nepredstavuje nákup, keďže neobsahuje plnotučné mlieko.
• Nákup zrejme predstavuje partície - rozklad čísla 5 na tri nenulové sčítance. Vymenovaním všetkých partícií zistíme, že ich je práve 6.
• Vypíšte všetky 6 partície. Otvorte tabuľu Tu.

Zrejme pri tomto nákupe nezáleží na poradí a zároveň platí, že neobsahujú nulový prvok (každý druh mlieka musí byť zastúpený).
Tieto podmienky spĺňa zadanie našej úlohy. Sú to teda partície z 5 prvkov a 3 triedy. Pre počet všetkých platí
$\small  P(5,3)=C(5-1,3-1)=C(4,2)=6$.

Nech $\small{M_n}= \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace$ je množina $n$ kategórií (druhov, prvkov). Vytvorme $r$-tice z prvkov týchto kategórií, v ktorých nezáleží na poradí ale prvky (prvky zo zvoleného druhu) sa môžu opakovať. Zrejme môže nastať aj prípad $r \geq n$.
Ukážka
K dispozícii máme dostatočný počet farebných štítkov: modré $m$, červené $č$, žlté $ž$ a zelené $z$, teda máme  $\small n=4$ druhy. Vypíšte niektoré možnosti výberu troch štítkov, teda $\small r=3$. Vo výbere sa môžu vyskytovať  štítky rovnakej farby. Avšak nemusí byť každá farba zastúpená vo výbere. Využite nasledujúci applet.

Definícia.
$r$-kombinácie s opakovaním definujeme ako $r$-tice prvkov z $n$ druhov $\small   \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace$, v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Počet všetkých $r$-kombinácií s opakovaním z $n$ prvkov budeme označovať symbolom $\small  C'(n,r)$.

Kombinácia s opakovaním $\small  a_1 a_2 \cdot \cdot \cdot a_r$ bude ľubovoľná (neusporiadaná) $r$-tica prvkov z množiny $\small{M_n}= \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace$.

• Výber $r$-tica predpokladá, že prvkov každého druhu $\small   a_i \in M_n$ je dostatočne veľa, teda aspoň $r$.
• Pri určovaní počtu všetkých $r$-kombinácií s opakovaním z $n$ prvkov budeme využívať výsledky, ktoré sme odvodili pri partíciách a pri skúmaní vlastností permutácií s opakovaním.

Príklad.
V obchode predávajú tri druhy cukru: kryštálový $k$, práškový $p$ a hnedý $h$ v kilogramovom balení, teda $n=3$ . Vypíšte všetky možnosti pri nákupe 2 resp. 3 kilogramov cukru, teda $r=2$ resp. $r=3$. V nákupe sa môže opakovať ten istý druh cukru avšak nemusí byť každý druh cukru zastúpený v nákupe.

Riešenie.
Uvedieme nejaké možné nákupy, napríklad 2 kilogramový nákup môže byť {1 kg práškového cukru, 1 kg kryštálového cukru} $\equiv \lbrace{p,k}\rbrace = \lbrace{k,p}\rbrace$ alebo 3 kilogramový nákup môže byť {2 kg práškového cukru, 1 kg hnedého cukru} $\equiv \lbrace{p,p,h}\rbrace = \lbrace{p,h,p}\rbrace$.
Všetky nákupy dvoch kilogramov budú predstavovať 2-kombinácie s opakovaním z troch druhov cukru - $\small   C'(3,2)$. Všetky nákupy troch kilogramov budú predstavovať 3-kombinácie s opakovaním z troch druhov cukru - $\small   C'(3,3)$.
Pokúste sa vymenovať všetky možné nákupy. Pri nákupe

1. dvoch kilogramov máme 6 možností ... vypíšte ich.  Obr. Tu.
2. troch kilogramov dostaneme 10 možností... výpočet Tu.

Veta.
Pre počet $r$-kombinácií s opakovaním z $n$ druhov platí
$\small   C'(n,r)=C(n+r-1,n-1)$.

Dôkaz.
Nech $\small   x_i$ označuje počet výskytu prvku $\small   a_i \in M_n$ v nejakej $r$-kombinácií $\small   a_1 a_2 \cdot \cdot \cdot a_r$ s opakovaním. Potom zrejme musí platiť rovnosť
     [1] $x_1+x_2+ \cdot \cdot \cdot + x_n=r$.             [Napríklad pre nákup $\small  \lbrace{k,p}\rbrace$ ide o rovnosť $\small   1+1+0=2$.]
Ak k obidvom stranám rovnosti [1] pripočítame číslo $n$, tak po úprave dostaneme rovnosť
     [2] $y_1+y_2+ \cdot \cdot \cdot + y_n=r+n$       [Pre nákup $\small  \lbrace{k,p}\rbrace$ ide o rovnosť $\small   2+2+1=5$.]
kde $y_i =x_i +1$ pre $i=1,2, \cdot \cdot \cdot ,n$.  
Na rovnosť $\small  y_1+y_2+ \cdot \cdot \cdot + y_n=r+n$ sa môžeme pozerať ako na rozdelenie čísla $r+n$ na $n$ častí alebo ako na partície (navzájom rôznych aspoň poradím) čísla $r+n$ na $n$ častí.
Počet takýchto partícií je rovný číslu
     [3]$\small   P(n+r,n)=C(n+r-1,n-1)$. Tým sme dokázali tvrdenie. Na ilustráciu dôkazu použite applet:
Pre nákup štyroch kg cukru dostávame $\small   C(4+3-1,3-1)=15$ Vypíšte všetky 4-kombinácie..

Iný spôsob určovania počtu kombinácií s opakovaním budeme prezentovať na úlohe:
"V obchode majú tri druhy sirupu: jahodový, malinový a pomarančový. Určte počet všetkých možností nákupu piatich fliaš sirupu v obchode."

Úlohu vyriešime tak, že najskôr navrhneme spôsob, ako rozmiestniť $\small r=5$ fliaš sirupu do $\small n=3$ druhov/košov. Použijeme dva symboly: • fľaša; ↑ oddeľovač.

• Ak vložíme jeden oddeľovač medzi fľaše, tak to bude znamenať, že sme fľaše rozdelili na dve podmnožiny resp. že sme ich umistnili do dvoch rôznych košov.
• Ak umiestnime dva oddeľovače medzi fľaše, tak to bude znamenať, že sme fľaše rozdelili na tri podmnožiny (môže nastať aj prípad prázdnej podmnožiny) resp. že sme ich umistnili do troch rôznych košov.

Vo všeobecnosti rozmiestnenia budú predstavovať $\small (r+n−1)$-tice, v ktorých sa

1. (počet prvkov kombinácie - fľaše) symbol "•" sa vyskytuje $\small r$-krát
2. (počet oddeľovačov = počet druhov zmenšený o 1) symbol "↑" sa vyskytuje $\small n-1$-krát. 

Pri rozmiestnení záleží na poradí, preto sú to permutácie dvoch prvkov (fľaše + oddeľovače) s opakovaním. V našom príklade bude počet takých $\small (5+3-1)$-tíc zodpovedať počtu permutácií zo 7 prvkov s opakovaním, kde sa prvý prvok opakuje/vyskytuje $\small 5$-krát a druhý $\small (3-1)$-krát.  
$\small P'(5,2)=\large \frac{ (5+(3-1))!}{5!2! }$=$\small , C'(5+2,2)=21$.

Cvičenie 1.
Vyriešte týmto spôsobom predchádzajúcu úlohu o nákupe cukru.

Cvičenie 2.
Vyriešte obidvoma spôsobmi úlohu o počte farebných štítkov.

 
Vľavo je použitý 1. spôsob pomocou partícií a vpravo 2. spôsob popmocou permutáciií.

1. Vyžitím binomickej vety vypočítajte $1,01^6$.
2. Určte desiaty člen binomického rozvoja výrazu $(2x^3-\frac{\sqrt{2}}{x} )^{12}$
3. "V obchode majú dva druhy kompótu: ananásový a hruškový. Určte počet všetkých možností nákupu 5 balení kompótu v tomto obchode." Otvorte tabuľu Tu.
   Zistite, či riešením nasledujúcej úlohy dostaneme rovnaký výsledok?
   "V obchode majú 5 druhov múky v kilogramovom balení: hladkú, polohrubú, hrubú, špeciálnu hladkú a bezlepkovú. Určte počet všetkých možností nákupu 2 kg múky v tomto obchode."  Otvorte tabuľu Tu.
4. Kombinačné čísla $C'(n,k) = C(n+k-1,n-1)$ môžeme ľahko určiť z tabuľky
   Otvorte tabuľku Tu
5. Určte počet všetkých trojuholníkov, z ktorých žiadne dva nie sú zhodné a každá ich strana má jednu z veľkostí daných číslami 5, 6, 7, 8, 9, 10. [Rieš = 53: Zrejme pre trojice 448,449,459 neexistuje trojuholník - trojuholníková nerovnosť; máme 6 druhov strán a vytvárame trojice].

Nech $M= \lbrace{x_1,x_2,..., x_n}\rbrace$ je množina objektov a $a_1,a_2, ... , a_k$ sú nejaké vlastnosti. Označme symbolom

• $N$ počet všetkých objektov, teda$N=n )$
• $N(a_r)$ počet všetkých objektov, ktoré majú vlastnosť $a_r; (1 \leq r \leq k )$
• $N(a_ra_s)$ počet tých objektov, ktoré majú súčasne vlastnosti $a_r,a_s; (1 \leq r$
• $N(a_ra_sa_t)$počet tých objektov, ktoré majú súčasne tri vlastnosti atď.
• Konečne, znakom $N(0)$ označme počet tých objektov, ktoré nemajú ani jednu z daných vlastností.

Príklad.
Písomnú prácu z matematiky písalo 35 študentov. Písomka obsahovala tri úlohy A, B, C. Vieme, že

1. Úlohu A vyriešilo 22 študentov, úlohu B vyriešilo 26 študentov, úlohu C vyriešilo 23 študentov.
2. Úlohu A aj úlohu B vyriešilo 16 študentov, úlohu A aj úlohu C vyriešilo 14 študentov, úlohu B aj úlohu C vyriešilo 17 študentov.
3. Všetky úlohy vyriešilo 10 študentov.

Zistite koľko študentov nevyriešilo ani jednu úlohu?

Riešenie.
Typické stredoškolské riešenie využíva grafickú schému - Vennov diagram, pomocou ktorého sa graficky vyjadruje príslušnosť prvkov k množine. V našom prípade to bude Vennov diagram pre tri množiny.

V diagrame postupne zapisujeme hodnoty

• 10
• 6 = 16 - 10,   4 = 14 - 10,   7 = 17 – 10
• 2 = 22 – (16 + 14) + 10,   3 = 26 – (16 + 17) + 10,   2 = 23 – (14 + 17) + 10
• 1 = 35 - (22 + 26 + 23) + (16 + 14 + 17) – 10 = 35 – 71 + 47

Všimnime si, že znamienka pri zátvorkách (vrátane posledného sčítanca sa striedajú. Môžeme ich určiť pomocou mocniny $\left(-1\right)^k; k=1,2,\ldots$.

V tejto časti budeme používať symboliku z predchádzajúcej kapitoly. Napríklad $N$ označuje počet všetkých objektov skúmanej množiny.

Tvrdenie
V kombinatorike princíp zapojenia a vypojenia alebo princíp exklúzie a inklúzie hovorí, že ak $A_1, ..., A_n$ sú konečné množiny, tak
$N(0)=N- \sum{N(a_i)} + \sum{N(a_ra_s)} - \sum{N(a_ra_sa_t)} + \cdot \cdot \cdot(-1)^{n} \sum{N(a_ra \cdot \cdot \cdot a_n)}$

Dôkaz tvrdenia.

1. Objekt, ktorý nemá ani jednu z vlastností $a_r$ prispieva jednotkou k číslu $N(0)$ aj k číslu $N$, ale vo zvyšných sčítancoch na pravej strane sa nevyskytuje.
2. Ak nejaký objekt má $m$ vlastností, kde $1 \leq m \leq k$, potom prispieva
• jednotkou k číslu N
• $m$ jednotkami k sume $\sum_{r=1}^{k}N\left(a_r\right)$ (lebo prispieva jednotkou k $m$ sčítancom)
• $\binom {m} {2}$ jednotkami k sume $\sum_{1 \leq r \leq s}^{k}N\left(a_ra_s\right)$. (Z $m$ vlastností daného objektu možno vybrať $\binom {m} {2}$dvojíc, preto objekt prispieva k tejto sume $\binom {m} {2}$ jednotkami), atď.
3. Teda objekt s $m>1$ vlastnosťami prispieva k pravej strane rovnosti hodnotou
   $1-m+\binom{m}{2}-\binom{m}{3}+\ldots+\left(-1\right)^{k+1}\binom{m}{k}$
4. Podľa binomickej vety vieme, že táto hodnota (striedavé sčítanie a odčítanie kombinačných čísel $\sum_{i=0}^{n}{{-1}^i\binom{m}{i}=0})$ je rovná nule.
5. Preto celkový príspevok objektu s aspoň jednou vlastnosťou k obidvom stranám rovnosti je rovný nule.

Problém šatniarky.
Pri vstupe do klubu si každý z piatich pánov odloží klobúk do šatne. Pri odchode šatniarka vydá náhodne každému pánovi jeden klobúk bez toho, že by skontrolovala, či je to správny klobúk. Aké sú šance, že žiaden z pánov nedostane vlastný klobúk?

1. Ide o permutácie klobúkov. Šatniarka priraďuje klobúky pánom. Jedno priradenie klobúkov pánom je permutácia.
2.  Keď permutácia má pevný bod, tak to znamená, že niektorý klobúk bol daný správne svojmu pánovi.
3. Pravdepodobnosť bude predstavovať podiel počtu permutácií bez pevného bodu k počtu všetkých permutácií.
4. Derangement (deranžmán) permutácia bez pevných bodov, v ktorej nikto nedostane svoj pôvodný prvok.
5. Čitateľ bude rovný počtu všetkých permutácií bez pevného bodu (počet všetkých deranžmánov).
6. Na permutácie s aspoň jedným pevným bodom sa uplatňuje princíp inklúzie a exklúzie.

1. Riešenie pomocou princípu zapojenia a vypojenia
Aplikovaním princípu zapojenia a vypojenia dostaneme:

1. $\small  N(0)=\normalsize{5!- \binom {5} {1}(5-1)! + \binom {5} {2} (5-2)!- \binom {5} {3}(5-3)! + \binom {5} {4}(5-4)!-\binom {5} {5}(5-5)!}$
2. $\small  N(0)=\normalsize{5!\left(1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}+ \frac{1}{4!} - \frac{1}{5!}\right)=44}$
3. Teda pravdepodobnosť je $\frac{44}{5!} = \frac{44}{120} = \frac{11}{30}$.

2. Riešenie pomocou cyklového rozkladu permutácie
Bez pevného bodu znamená, že v cyklovom rozklade permutácie sa nesmie vyskytnúť 1-cyklus. Pri piatich prvkoch teda prichádzajú do úvahy iba dva typy rozkladu:

1. jeden 5-cyklus,
2. jeden 2-cyklus a jeden 3-cyklus.

Spočítajme a) prípad:

• • Počet 5-cyklov na piatich prvkoch je $\small  (5-1)! = 4! = 24$. Pozrite si zdôvodnenie Tu.

Spočítajme b) prípad:

• • Pri rozklade na 2-cyklus a 3-cyklus najprv vyberieme dvojicu prvkov, ktoré vytvoria 2-cyklus: $\small  \binom 5 2 = 10$.
  • Zostávajúce tri prvky musia vytvoriť 3-cyklus. Počet 3-cyklov na troch prvkoch je $\small  (3-1)! = 2$.
  • Takýchto permutácií je teda $\small  \binom 5 2 \cdot 2 = 10 \cdot 2 = 20$.

Spolu dostaneme počet permutácií bez pevného bodu $\small  24 + 20 = 44$. Pravdepodobnosť je preto
$\frac{44}{5!} = \frac{44}{120} = \frac{11}{30}$.

Poznámka: Tento spôsob je výhodný tým, že sa nemusí používať princíp zapojenia a vypojenia; stačí vychádzať z cyklového rozkladu permutácie.

3. Riešenie pomocou rekurentného vzorca pre počet deranžmánov
Označme $\small  D_n$ počet permutácií $\small  n$ prvkov bez pevného bodu. Pre deranžmány platí rekurentný vzťah
$\small  D_n=(n-1)(D_{n-1}+D_{n-2}).$
Zdôvodnenie vychádza z princípu zapojenia a vypojenia. Vysvetlenie pre náš prípad:

1. Sledujme, kam sa dostane klobúk pána číslo 1. Nemôže zostať u pána 1, preto môže ísť k niektorému zo zvyšných $\small 4$ pánov.
2. Predpokladajme, že klobúk 1 dostane pán $\small k$.
3. Teraz nastanú dve možnosti:
   • buď klobúk pána $\small k$ dostane pán 1; potom sa dvojica $\small (1,k)$ uzavrela do 2-cyklu a zvyšné $\small 3$ klobúky sa musia rozdať bez pevného bodu, teda počtom $\small D_3$,
   • alebo klobúk pána $\small k$ nedostane pán 1; potom po vhodnom zlúčení situácie dostaneme počet možností $\small D_4$.
4. Preto $\small  D_5=4(D_4+D_3)$. Teraz už len dopočítame menšie hodnoty:

1. • $\small  D_1=0$ — jeden pán vždy dostane svoj klobúk.
   • $\small  D_2=1$ — jediná možnosť je výmena klobúkov.
   • $\small  D_3=2$.
   • $\small  D_4=3(D_3+D_2)=3(2+1)=9$.
   • $\small  D_5=4(D_4+D_3)=4(9+2)=44$.
2. Teda opäť dostávame pravdepodobnosť $\small  \frac{D_5}{5!}=\frac{44}{120}=\frac{11}{30}$.

4. Riešenie pomocou známeho vzorca pre deranžmány
Počet permutácií $\small n$ prvkov bez pevného bodu sa označuje $\small  !n$ a platí vzorec $\small  !n=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\right).$ Pre $\small n=5$ dostaneme:

1. $\small  !5=5!\left(1-1+\frac12-\frac16+\frac1{24}-\frac1{120}\right)$
2. $\small  !5=120\left(0+\frac12-\frac16+\frac1{24}-\frac1{120}\right)=44$
3. Pravdepodobnosť teda je $\small  \frac{!5}{5!}=\frac{44}{120}=\frac{11}{30}$.

Tento postup je najkratší  ale študenti musia poznať pojem deranžmán a základné vzorce súvisiace s týmto pojmom.
A tie sú ekvivalentné princípu zapojenia a vypojenia.

Záver.
Nech už použijeme princíp zapojenia a vypojenia, cyklový rozklad permutácie, rekurentný vzťah pre deranžmány alebo priamo známy vzorec pre $!n$, vo všetkých prípadoch dostaneme ten istý výsledok: $\small  P(\text{nikto nedostane svoj klobúk})=\frac{11}{30}.$

Poznámky.

1. Permutácia je deranžmán práve vtedy, keď nemá žiadny cyklus dĺžky 1.
2. Počet deranžmánov z 𝑛 prvkov sa označuje: !𝑛
   $\small  !n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right)$
3. „!𝑛 čítame ako deranžmán z n.“  alebo „Je to tzv. subfaktoriál.“

Cvičenie.
Riešte úlohy: Otvorte si zadania Tu.

Pri riešení využívajte AI asistenta " Kombinatorika – sprievodca riešením úloh.

Kombinatorika patrí medzi tie časti matematiky, pri ktorých študent často neurobí chybu vo výpočte, ale už skôr pri rozpoznaní typu úlohy. Potrebuje sa správne rozhodnúť, či záleží na poradí, či sa prvky môžu opakovať a aký typ výberu má použiť. Práve tu môže byť AI asistent užitočný: pomáha pomenovať typ úlohy, rozložiť riešenie na menšie kroky, skontrolovať postup a pripraviť podobný príklad na precvičenie.

Odporúčanie.
AI asistenta je vhodné používať ako pomocníka pri porozumení a precvičovaní, nie ako náhradu vlastného rozmýšľania. Najväčší úžitok má vtedy, keď študent najprv sám skúsi rozpoznať typ úlohy a až potom požiada o nápovedu, kontrolu alebo vysvetlenie. Pozrite si príspevok " Seminár: práca s AI asistentom".

Praktické pravidlá.

1. AI asistent navrhuje jednoduché vysvetlenie krok po kroku.
2. Najskôr formou dialógu určí typ kombinatorickej úlohy.
3. Bez výslovného požiadania celý výsledok nenapíšte.
4. AI asistent ponúkne aj podobnú (ľahšiu resp. náročnejšiu) úlohu.
5. Po vyriešení úlohy môžete AI požiadať o zápis výsledku v rôznych formátoch (TeX, PDF, ...).
6. AI asistent sa riadi inštrukciami - promptom.

Prompt 1 – určenie typu úlohy.

Skopírujte a použite napríklad tento prompt:

Prompt 2 – pomoc pri riešení bez prezradenia výsledku.

Tento prompt je vhodný vtedy, keď chcete nápovedu, ale nie hotové riešenie:

Prompt 3 – kontrola vlastného riešenia.

Tento prompt je vhodný po samostatnom riešení:

Prompt 4 – podobný príklad na precvičenie.

Tento prompt pomáha pri upevňovaní postupu:

Tri otázky, ktoré sa oplatí položiť AI asistentovi.

Pri kombinatorike veľmi pomáha, keď AI asistentovi položíte práve tieto otázky:

1. Záleží v tejto úlohe na poradí?
2. Môžu sa prvky opakovať?
3. Prečo tu používame práve tento vzorec?

Poznámka pre študenta.
Ak AI asistent odpovie príliš zložito, môžete dopísať napríklad:

• Vysvetli to ešte jednoduchšie.
• Ukáž mi iba prvý krok.
• Daj mi podobný, ale ľahší príklad.
• Nepíš hneď celý výsledok.

Záver.
Pri učení kombinatoriky môže byť AI asistent dobrým partnerom vtedy, keď študentovi pomáha pomenovať typ úlohy, rozčleniť riešenie na menšie kroky a premýšľať nad tým, prečo je zvolený postup správny. Skutočný prínos však vzniká až vtedy, keď AI podporuje vlastné porozumenie, a nie iba rýchle získanie výsledku.