Kombinatorika

Predkladaný text vychádza z práce$^ {1)}$ významného slovenského matematika prof. RNDr. Štefana Známa, DrSc. Nami upravený učebný text rozširuje poznatky z kombinatoriky na stredných školách. Celý text vo formáte WORD si môžete stiahnuť Tu.

Kombinatorika je obor matematiky, ktorý sa zaoberá skupinami prvkov množín s definovanou vnútornou štruktúrou.

Uveďte príklady skupín prvkov, ktoré budú reprezentovať každú zo štyroch základných tried.

Pri určovaní počtu skupín prvkov množín bežne využívame kombinatorické pravidlo súčinu a súčtu. Viac v práci [Farská, 2007]²⁾ Tu.

Ak $n$ je prirodzene číslo, symbolom $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 $M_r$ množiny $M_n$ sa nazýva kombinácia množiny $M_n$. Ak $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 $M_n$ budeme označovať $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 $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 $M_5$. Sú to množiny: $\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: $1,2,3,4,5$. Ich počet je 5.
3. $2 -$ kombinácie utvoríme tak, že ku každej $1 -$ kombinácii a pripojíme vpravo po jednom všetky prvky, ktoré sa v množine $M_5$ nachádzajú vpravo od $a$. Postup tvorby Tu. Ich počet je 10.
4. Obdobne získame všetky $3 -$ kombinácie. Ku každej $2 -$ kombinácii $ab$ pripojíme po jednom každý prvok, ktorý leží v $M_5$ vpravo od $b$ (ak taký prvok existuje) . Dostaneme tieto $3 -$ kombinácie: $123, 124, 125, 134, 135, 145, 234, 235, 245, 345$. Ich počet je 10. 
5. Podobne postupujeme pri tvorbe $4 -$ kombinácií. Ich počet je 5 a sú to $1234, 1235, 1245, 1345, 2345$. 
6. Existuje len  jedna $5 -$ kombinácia $12345$.
7. Zrejme, množina $M_5$ nemá nijakú $6 -$ kombináciu.

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

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

Dôkaz tvrdenia:

Označme $A(r)$ resp. $A(n-r)$ množinu všetkých $r-$ kombinácií resp. $(n-r)-$ kombinácií množiny $M_n$.
    Skonštruujme zobrazenie $\phi : A(r) \rightarrow A(n-r)$ nasledovne:
    ak $K \in A(r)$, tak jeho obrazom $\phi (K)$  bude doplnková kombinácia ku $K$.

    Zrejme zobrazenie  $\phi$ je bijekcia, preto množiny $A(r)$ a $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 $M_n$ a nech $r \geq 1$. Počet $r -$ kombinácií množiny $M_n$, ktoré
$\ast$ prvok $x$ obsahujú sa rovná $C(n-1,r-1)$
$\ast$ prvok $x$ neobsahujú sa rovná   $C(n-1,r)$

Dôkaz tvrdenia:

1. Odstráňme prvok $x$ zo všetkých $r -$ kombinácií (ktoré ho obsahujú)
• Dostaneme práve všetky $(r-1) -$ kombinácie množiny $M_{n-1}= M_n - \lbrace{x}\rbrace$
• Ich počet je  rovný $C(n-1,r-1)$.
2. Ak nejaká ( r - \) kombinácia množiny $M_n$ neobsahuje prvok $x$, je vlastne $r -$ kombináciou množiny $M_{n-1}$
• Ich počet týchto je $C(n-1,r)$.

                                  

Dôsledok: Ak $1 \leq r \leq n$, tak platí    $C(n,r )=C(n-1,r-1 )+C(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í: $\binom {n} {r} = \frac{n!}{(n-r)!\; r!}$

Pre prípustné hodnoty $\small n$ zjednodušte výrazy:

1. $\frac{n!(n+1)!}{(n-1)!(n+2)!}$ riešenie
2. $\frac{(n+2)!}{n!} -\frac{2(n+1)!}{(n-1)!}+ \frac{n!}{(n-2)!}$

Riešte rovnicu v obore celých čísel

1. $\frac{(x+6)!}{(x+4)!}$ $\small + \; x^2-16x=28$ riešenie
Ďalšie rovnice Tu

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 $M_n$ nazývame jej bijektívne zobrazenie na seba.

Napríklad zobrazenie $f: Z_4\rightarrow Z_4$ dané predpisom:
$f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1$
je bijekcia množiny $Z_4=\left\{1, 2, 3, 4\right\}$ na seba. Takúto permutáciu budeme symbolicky zapisovať pomocou matice
$\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ť
$\mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1}$.

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

Pre $f\left(a\right)=a$ sme dostali permutácie $abcd, abdc, acbd, acdb,adcb,adbc$. Podobne budeme postupovať pre $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 $M_n$.

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

Kombinatorické pravidlo súčinu
Nech $A_1,A_2,\ldots,A_n$ sú množiny majúce po rade $a_1,a_2,\ldots,a_n$ prvkov. Potom počet usporiadaných $n$-tíc, ktorých prvý prvok je z množiny $A_1$, druhý z množiny $A_2$ a $n$-tý z množiny $A_n$ je rovný súčinu $a_1a_2\ldots a_n$.
Dôkaz prenechávame na čitateľa. Odporúčame použiť matematickú indukciu vzhľadom na počet množín $A_i$.

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.

Cvičenie 1..

Cvičenie 2..

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 $V(n,r)$.

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

Úloha 1. 
Koľko trojciferných čísel môžeme vytvoriť z číslic $1,2,3,4,5$, ak sa žiadna číslica neopakuje?

Riešenie
Výsledok: V(5,3) = 60

Úloha 2. 
Koľko rôznych jedno až štvorciferných čísel môžeme vytvoriť z cifier 0, 1, 2, 3?

Riešenie
Keby medzi ciframi nebola nula, tak počet všetkých jedno až štvorciferných čísel by bol súčet čísel
       V(4,1)+V(4,2)+V(4,3)+V(4,3) = 4 + 12 + 24 + 24 = 64.
Pre počet všetkých jedno až štvorciferných čísel začínajúcich nulou bude zrejme platiť
       V(3,1)+V(3,2)+V(3,3) = 1 + 3 + 6 + 6 =16.
Pre počet všetkých jedno až štvorciferných čísel z cifier 0, 1, 2, 3 je rovný
       64 - 16

Úloha 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?

    Riešenie o/span>

Cvičenie. Vytvorte všetky zostavy, ktoré sú zložené z 3 štvorčekov siete. Použite len 2 farby - modrú a žltú.

Z prvkov množiny $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 $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. 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ácie s opakovaním z $n$ prvkov je usporiadaná $k$-tica zostavená z týchto prvkov tak, že každý 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 radu. Zrejme záleží na poradí, pričom modrá kocka sa opakuje 4.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 15 rôznych uložení 3 modrých a dvoch červených kociek.

Tvrdenie.
Počet permutácií s opakovaním z $n$, v ktorých sa jednotlivé prvky opakujú $k_1,k_2, \cdot \cdot \cdot ,k_n$-krát, je rovný číslu
$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 $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 $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í $P'(k_1,k_2,...,k_n)= \frac{(k_1+k_2+...+k_n)!}{k_1!k_2!...k_n!}$.
2. Po dosadení do vzorca pro počet permutácií z 2 prvkov s opakovaním $k_1=k_2=2: \; P'(2,2)= \frac{(2+2)!}{2!2!} = \frac{24}{4} =6$

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 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é

Začneme prvým prípadom. 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
$P(n,r)$.
V ďalšom sa budeme snažiť určiť číslo $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ť
$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á
$P(n,r)=C(n-1,r-1)$

Príklad. Rozklad čísla $6$ na $3$ nenulových sčítancov. Vypíšte všetky rozklady.
Riešenie. Číslo $6$ má $P(6,3)=C(6-1,3-1)=C(5,2)=10$ partícií z troch sčítancov. Sú to partície:
$1 + 2 + 3, \; \;2 + 1 + 3,\; \; 1 + 3 + 2,\; \; 3 + 1 + 2,\; \; 2 + 3 + 1,\; \;3 + 2 + 1$
$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 $P(n)$, tak zrejme platí
$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
$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 $(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 $(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 $(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í
$P(5,3)=C(5-1,3-1)=C(4,2)=6$.

Nech $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 týchto $n$ prvkov, v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Zrejme môže nastať aj prípad $r \geq n$.

Definícia.
$r$-kombinácie s opakovaním definujeme ako $r$-tice prvkov z $n$ druhov $\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 $C'(n,r)$.

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

• Výber $r$-tica predpokladá, že prvkov každého druhu $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í. Vypíšte všetky možnosti pri nákupe 2 resp. 3 kilogramov cukru. V nákupe sa môže opakovať ten istý druh cukru.
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 - $C'(3,2)$. Všetky nákupy troch kilogramov budú predstavovať 3-kombinácie s opakovaním z troch druhov cukru - $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.Otvorte tabuľu Tu. Obr. Tu
2. troch kilogramov dostaneme 10 možností... vypíšte ich

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

Dôkaz.
Nech $x_i$ označuje počet výskytu prvku $a_i \in M_n$ v nejakej $r$-kombinácií $a_1 a_2 \cdot \cdot \cdot a_r$ s opakovaním. Potom zrejme musí platiť rovnosť
$x_1+x_2+ \cdot \cdot \cdot + x_n=r$.
Napríklad pre nákup $\lbrace{k,p}\rbrace$ ide o rovnosť $1+1+0=2$

1. Ak k obidvom stranám tejto rovnosti pripočítame číslo $n$, tak po menšej úprave dostaneme rovnosť
$y_1+y_2+ \cdot \cdot \cdot + y_n=r+n$,
kde $y_i =x_i +1$ pre $i=1,2, \cdot \cdot \cdot ,n$.
Pre nákup $\lbrace{k,p}\rbrace$ ide o rovnosť $2+2+1=5$.
2. Na rovnosť $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í.
3. Počet takýchto partícií je rovný číslu $P(n+r,n)=C(n+r-1,n-1)$.Tým sme dokázali tvrdenie.
   Pre nákup dvoch litrov dostávame $C(5-1,3-1)=6$.

Na úlohy (pozrite tiež predchádzajúci príklad) typu:
"V obchode majú tri druhy sirupu: jahodový, malinový a pomarančový. Určite počet všetkých možností nákupu piatich fliaš sirupu v obchode."
sa môžeme pozerať aj ako na permutácie s opakovaním. Úlohu vyriešime tak, že určíme počet spôsobov, ako rozmiestniť $\small k=5$ fliaš sirupu do $\small n=3$ druhov/košov.

Použijeme dva symboly: • - fľaša; ↑-oddeľovač. Potom rozmiestnenia budú predstavovať $\small (k+n−1)$-tice, v ktorých sa symbol "•" vyskytuje $\small k$-krát (fľaše) a symbol "↑" $\small (n-1)$-krát (\\small ( n-1 \) oddelení medzi $\small n$ košmi).
Počet takých $\small (k+n−1)$-tíc zodpovedá 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. Tým sme ukázali platnosť vzťahu
$\small P'(5,2)= \frac{ (5+(3-1))!}{5!2! }$=$\small C'(5+2,2)=21$.

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. Pravdepodobnosť bude predstavovať podiel počtu permutácií bez pevného bodu k počtu všetkých permutácií.
2. Ide o permutácie klobúkov. Šatniarka priraďuje klobúky pánom. 
3. Jedno priradenie klobúkov pánom je permutácia. Predstavme si, že páni sú očíslovaní a klobúky tiež. 
4. Keď permutácia má pevný bod, tak to znamená, že niektorý klobúk bol daný správne svojmu pánovi.
5. Čitateľ bude rovný počtu všetkých permutácií $5!=120$ mínus počet permutácií s aspoň jedným pevným bodom - to musíme spočítať.
6. Na permutácie s aspoň jedným pevným bodom sa uplatňuje princíp inklúzie a exklúzie.

Aplikovaním princípu zapojenia a vypojenia (tvrdenie v predchádzajúcej kapitole) dostaneme:

1. $N(0)=5!- \binom {5} {1}(5-1)! + \binom {5} {2} (5-2)!- \cdot \cdot \cdot +(-1)^5 \binom {5} {5}$
2. $N(0)=5!(1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}+ \frac{1}{4!} - \frac{1}{5!})=44$
3. Po úprave dostaneme, že pravdepodobnosť je rovná $\frac{44}{5!} = \frac{44}{120} = \frac{11}{30}$