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 $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)!}$ $+ \; x^2-16x=28$  riešenie

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$.

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. 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.
• Nákup predstavuje partície, v ktorých záleží na poradí. 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_r}\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.

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 si tabuľu 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$. Otvorte tabuľu.
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$.

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 4,5,6,7,8,9.

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

1. $\binom{x+1}{2}+\binom{x}{2}=4\binom{n}{n}$ $+ \; x^2-16x=28$
2. $\frac{(x+6)!}{(x+4)!} +x^2-16x=28$

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?

Ukáž riešenie

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

Ukáž riešenie

Ú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 $M_n$ sa nazýva $r$-variácia s opakovaním množiny $M_n$ . Počet všetkých $r$-variácií s opakovaním množiny $M_n$ budeme označovať symbolom $V'(n,r)$.

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

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

Veta. Pre počet všetkých $r$-variácií s opakovaním množiny $M_n$ platí vzťah
$V'(n,r)=n^r$
Dôkaz vety.
Dôkaz je výhodné urobiť pomocou matematickej indukcie. Pre $r=1,2$ je tvrdenie pravdivé, presvedčte sa o tom. Predpokladajme, že tvrdenie platí pre $r-1$. Teda
$V'(n,r-1)=n^{r-1}$
Všetky usporiadané $r$-tice s opakovaním množiny $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 $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
$V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r$.

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$.

Ukážka.
Ak máme napr. 3 žlté kocky, 1 modré kocka a 1 červená kocka a chceme ich poukladať do radu, jedná sa o permutácie s opakovaním z troch prvkov, kde prvý prvok sa opakuje 3x, druhý 1xa tretí 1x.

1. $n = 3$ (žltá, modrá, červená kocka)
2. $k_1 = 3, k_2 = 1, k_3 = 1$
3. $k = k_1 + k_2 + k_3 = 3 + 1 + 1 = 5$.
Skúste vypísať všetky permutácie, ktoré vyhovujú zadaniu.

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!}$

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

Riešenie.
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$

Cvičenie.
Nájdite všetky možnosti, ako môže na 3 rovnakých hracích kockách padnúť súčet 11. (na poradí kociek nezáleží)

Riešenie.
Pozrite si kurz "Elementárna matematika 6" stránke Tu, časť Permutácie s opakovaním; Odporúčame; odkaz: programy. Program si stiahnite a extrahujte. Potom vyberte časť 9. Vypíšte všetky možnosti pomocou tohto programu. Pozrite si nasledujúci obrázok.
S touto úlohou úzko súvisí úloha z pravdepodobnosti:

1. "Aká je pravdepodobnosť, že na troch hracích kockách padne súčet rovný číslu 11. Pozrite si riešenie tejto úlohy z pravdepodobnosti na stránke "Príklady.eu.", časť pravdepodobnosť, príklad 4. Tu. Spustite interaktívny program pre výpočet pravdepodobnosti Tu.
2. Riešte čiastkové úlohy "Vypíšte všetky možnosti pre prípad, že na kockách bude súčet 1+4+6 a súčet 1+5+5. Spustite si interaktívny program Tu.

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$. (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}$