====== AP2, IN2 Elementární kombinatorika ======
(variace, kombinace a permutace)

===== Vypracovanie =====

==== Variácie ====
Nech **//S//** je konečná množina. Variácie definujeme ako usporiadané (t.j záleží na poradí prvkov) výbery prvkov množiny **//S//**. Rozlišujeme ich podľa toho, či sa prvky z **//S//** v týchto výberoch môžu alebo nemôžu opakovať.
<box 95% round blue|Variácie>Počet variácií **k**-tej triedy z **n** prvkov je:
  *bez opakovania <math>V_{k}(n) = \frac{n!}{(n-k)!}</math>
  *s opakovaním <math>n^{k}</math>
</box>
Variácie s opakovaním **k**-tej triedy z **n** prvkov jsou uspořádané k-tice vybrané z **n** prvků. Môžeme je chápať aj ako množinu všetkých zobrazení **k**-prvkovej množiny **//X//** (**//X//** je ľubovoľná množina obsahujúca k prvkov) do **n**-prvkovej množiny **//S//**. Variácie bez opakovania sú teda všetky prosté zobrazenia <math>X \rightarrow S</math>.
<box 95% round green|Variácie bez opakovania>**Zadanie:** Na turnaj nastúpilo 16 mužstiev. Koľko je možností obsadenia prvých 3 priečok?
**Riešenie:** Záleží na poradí mužstiev, ide teda o variácie 3. triedy zo 16 prvkov: <math>V_{3}(16) = \frac{16!}{(16-3)!} = 16\cdot 15\cdot 14 </math>
</box>
<box 95% round green|Variácie s opakovaním>**Zadanie:** Koľkými spôsobmi môžeme zakódovať zámok na bicykel, ak je kód trojmiestny?
**Riešenie:** Prvé číslo môžeme vyberať z číslic 0, 1, ..., 9, druhé a tretie tak isto. Takže variácie 3-tej triedy z 10 prvkov a môžu sa opakovať: <math>V'_{3}(10) = 10^{3} = 1000 </math>
</box>
==== Permutácie ====
Permutácia **//n//** prvkov je skupina všetkých **//n//** prvkov, ktoré sú usporiadané v nějakém fixním poradí, tzn. výber prvkov závisí na poradí. Je to vlastně **speciální případ variace bez opakování n-té třídy z n prvků**. Rozlišujeme permutácie bez opakovania a s opakovaním. Permutáciu môžeme chápať aj ako bijektívne zobrazenie <math>S \rightarrow S</math> (S je konečná množina).
<box 95% round blue|Permutácie bez opakování>Počet všetkých permutácií **n** prvkovej množiny vypočítame:
  *ak sa prvky v množine neopakujú: 
<math>P(n) = V_{n}(n) = \frac{n!}{(n-n)!} = n!</math>
(permutácie **n** prvkovej množiny bez opakovania sú vlastne variácie **n**-tej triedy z **n** prvkov)
</box>
<box 95% round green|Príklad na permutácie bez opakovania>**Zadanie:** Koľkými spôsobmi sa dajú postaviť do rady 4 Angličani, 5 Francúzi a 3 Turci, ak osoby tej istej národnosti musia stáť vedľa seba?
**Riešenie:** Máme 3 skupiny (počet permutácií skupín - **3!**) a v rámci každej skupiny chceme rôzne zoradiť ľudí tej istej národnosti - permutácie bez opakovania:
<math>3! \cdot 4! \cdot 5! \cdot 3!  </math>
</box>
<box 95% round blue|Permutace s opakováním>Pokud se prvky ve výběru mohou opakovat, pak počet permutací s opakováním je určen jako
<math>P(n_1,n_2,...,n_k) = \frac{(n_1+n_2+...+n_k)!}{n_1!\cdot n_2!\cdot ... \cdot n_k!} = \frac{n!}{n_1!\cdot n_2!\cdot ... \cdot n_k!}</math> 
-- přičemž mezi vybranými prvky je **k** skupin, které mají postupně <math>n_{1},n_{2},...,n_{k}</math> stejných prvků. Musí přitom platit <math>n = \sum_{i=1}^{k} n_{i}</math>. ((prevzato z http://cs.wikipedia.org/wiki/Permutace))
</box>
<box 95% round green|Príklad na permutácie s opakovaním>**Zadanie:** Určte počet všetkých anagramov, ktoré sa dajú zostaviť z písmen slova ABRAKADABRA.
**Riešenie:** Jedná sa o permutácie s opakovaním, pretože niektoré písmená sa vyskytujú v slove viac ako 1x. Písmeno A sa vyskytuje 5x, R 2x, K 1x, B 2x, D 1x, výsledný počet anagramov teda je:
<math>\frac{(5+2+1+2+1)!}{5! \cdot 2! \cdot 1! \cdot 2! \cdot 1!}</math>
</box>

=== Grupa permutácií ===
<box 95% round blue|Grupa permutácií>Nech **X** je množina. Ak množinu všetkých permutácií na množině X označíme **S(X)** a <math>\circ</math> operáciu skladania zobrazenia, <math>(S(X),\circ)</math> je nekomutatívna grupa.
Neformálny dôkaz: <math>\circ</math> je operácia na **S(X)**, je asociatívna, neutrálny prvok je identická permutace a keďže permutácia je bijektívne zobrazenie, vždy existuje inverzný prvok (zobrazenie).
</box>
Permutácie môžeme zapísať rôznymi spôsobmi:
  * **tabuľkou**, kde v hornom riadku je vstupná hodnota funkcie a v dolnom riadku výsledná hodnota: <math>f = \begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\
 3 & 1 & 5 & 2 & 4 &6\end{pmatrix}</math>

  * ako **zloženie cyklov a transpozíc** (cyklov dĺžky 2): <math>f = (1,3,5,4,2) = (1,3) \circ (3,5,4,2) = (1,3) \circ (3,5) \circ (5,4) \circ (4,2) </math> (identickú permutáciu v rozklade neuvádzame)
<box 95% round blue|Veta 1.1>Každá permutácia množiny <math>\{1,...,n\}</math>, kde <math>n > 1</math> je súčin transpozíc. Identická permutace je súčin <math>(i,j)\circ(i,j)</math>, kde **i,j** sú ľubovoľné navzájom rôzne prvky z <math>\{1,...,n\}</math>.
</box>
=== Vlastnosti permutácií ===
Permutácia je **sudá (lichá)**, ak sa dá rozložiť na **sudý (lichý)** počet transpozíc. Permutácia uvedená vyššie je teda sudá. Rozklad na transpozície nie je určený jednoznačne (napr. permutácia <math>(1,2,3) = (1,2)\circ(2,3)</math>, ale aj <math>(1,2,3) = (1,3)\circ(1,2)</math>), jednoznačne je určená len **parita** permutácie.

**Parita** <math>p(f)=1</math> ak permutácia **f** je sudá, ak je permutácia **f** lichá, <math>p(f)=-1</math>.

<note>Cyklus <math>(r,r),\ r \in X</math> nie? je transpozícia, pretože sa jedná o cyklus dĺžky 1. Pri určovaní parity sa teda nebere do úvahy. Z toho bezprostredne vyplýva, že identická permutace je sudá - dá sa rozložiť na 0 transpozícií. Vo všeobecnosti platí:
cyklus dĺžky //n// sa dá rozložiť na //n-1// transpozíc</note>

Každý prvok <math>r \in X</math>, pre ktorý platí <math>f(r) = r,\ f \in S(X)</math>, se nazývá **samodružným prvkom** (v rozklade na transpozície ho neuvádzame, jedná sa o transpozíciu? **(r,r)**). Ak je každý prvok permutace samodružný, hovoríme o identickej permutácii.

Ak máme permutáciu <math>f,\ f^{k}</math> značí permutáciu, ktorá vznikne //k//-násobným zložením permutácie <math>f</math>, tj. <math> \ f^1 = f</math>, <math>f^k = f \circ f^{k-1}</math>. 

**Rád permutácie** je nejmenšie prirodzené číslo **k** také, pre ktoré platí <math> \ f^k = I</math>, tj. po //k// zloženiach vznikne identická permutácia.
=== Inverzná permutácia ===
K permutácii 
<math>f = \begin{pmatrix}a_1 & a_2 & ... & a_n \\
 b_1 & b_2 & ... & b_n\end{pmatrix}</math>

je možné vytvoriť **inverznú permutáciu**:

<math>f^{-1} = \begin{pmatrix}b_1 & b_2 & ... & b_n \\
 a_1 & a_2 & ... & a_n\end{pmatrix}</math>

Zložením permutácie **f** a k nej inverznej permutácii **f<sup>-1</sup>** získame identickú permutáciu.

=== Skladanie permutací ===
Majme na množine **X** dve permutácie:

<math>f_1 = \begin{pmatrix}a_1 & a_2 & ... & a_n \\
 b_1 & b_2 & ... & b_n\end{pmatrix}</math>

<math>f_2 = \begin{pmatrix}b_1 & b_2 & ... & b_n \\
 c_1 & c_2 & ... & c_n\end{pmatrix}</math>

**Zložením permutácií** <math>f_1, f_2</math> je permutácia

<math>f = f_2 \circ f_1 = \begin{pmatrix}a_1 & a_2 & ... & a_n \\
 c_1 & c_2 & ... & c_n\end{pmatrix}</math>

Operácia zloženia permutácií nie je komutatívna, ak má množina **X** aspoň 3 prvky.

==== Kombinácie ====
Nech **S** je konečná množina. Kombinácie sú neusporiadané výbery prvkov (t.j. nezáleží na ich poradí) množiny **S**. Opäť rozlišujeme kombinácie s opakovaním a bez opakovania. Každá kombinácia **k**-tej triedy bez opakování určuje **k!** variácií, preto môžeme vzorec na výpočet kombinácií odvodiť zo vzorcu na výpočet variácií. 
Pro kombinace s opakováním se vzorec odvodí metodou přepážek a kuliček.
<box 95% round blue|Kombinácie>Počet kombinácií **k**-tej triedy z **n** prvkov (<math>k \leq n</math>) sa rovná:
  * bez opakovania <math>C_k(n) = {n \choose k} = \frac{n!}{(n-k)!\cdot k!}</math>

  * s opakovaním <math>C'_k(n) = {n+k-1 \choose k}</math>
</box>

Čísla <math>{n \choose k}</math> sa nazývajú //kombinačné čísla//. Platia pre ne nasledujúce vzťahy:
  * <math>{n \choose k} = {n \choose n-k}</math>

  * <math>\sum_{k=0}^n {n \choose k} = 2^n</math>

  * <math>{n+1 \choose k} = {n \choose k} + {n \choose k-1}</math>

  * <math>{n \choose 0} = 1</math>

  * <math>{n \choose n} = 1</math>

Tretí vzťah súvisí s //Pascalovým trojuholníkom//, ktorý je geometrickou reprezentáciou binomických koeficientov:
{{:home:inf:pascaltriangle.png|Pascalov trojuholník}}
V 2.riadku Pascalovho trojuholníka (číslujeme od 0) sú čísla <math>{2 \choose 0},\ {2 \choose 1}</math> a <math>{2 \choose 2}</math>, sčítaním <math>{2 \choose 1}</math> a<math>{2 \choose 2}</math> dostaneme číslo pod nimi <math>{3 \choose 2} = 3</math>. Pascalov trojuholník vyjadruje koeficienty v binomickom rozvoji podľa binomickej vety:
<box 95% round blue|Binomická veta>Pre ľubovoľné <math>x,y \in C</math> a <math>n \geq 0</math> platí:
<math>(x+y)^n = \sum_{k=0}^n {n \choose k}\cdot x^{n-k}\cdot y^k</math></box>
**n**-tý riadok v Pascalovom trojuholníku určuje koeficienty binomického rozvoja <math>(x+y)^n</math>, teda napr. pre <math>n=3</math>:
<math>(x+y)^3 = x^3 + 3x^2 y + 3xy^2 + y^3</math>
<box 95% round green|Príklad na kombinácie>**Zadanie:** Koľkými spôsobmi sa dajú vybrať z čísel 1, 2, 3,..,29, 30 tri čísla tak, aby ich súčet bol sudý?
**Riešenie:** Súčet 3 čísel je sudý, ak sčítancami sú 2 liché a jedno sudé alebo 3 sudé čísla. V uvedenej číselnej rade je 15 sudých a 15 lichých čísel. Výsledný počet teda je:
<math>{15 \choose 2}\cdot {15 \choose 1} + {15 \choose 3} </math></box>
<box 95% round green|Kombinácie s opakovaním>**Zadanie:** V cukrárni sa podávajú 4 druhy zákuskov :
venček, veterník, laskonky a doboška. Koľkými spôsobmi sa dá kúpit 7 zákuskov?
**Riešenie:** Kombinácie 7-mej triedy, vyberáme zo 4 prvkov, ktoré sa môžu opakovať: <math>C'_7(4) = {4+7-1 \choose 7}</math></box>
<box 95% round green|Kombinácie bez opakovania>**Zadanie:** Na vecierku sa stretne 5 priatelov. Každý si podá
ruku so všetkými ostatnými. Kolko bolo medzi týmito priateľmi podaní rúk?
**Riešenie:** 2-členné kombinácie z 5 prvkov bez opakovania: <math>C_2(5) = {5 \choose 2} = \frac{5!}{(5-2)!\cdot 2!} = 10 </math></box>

==== Princípy použiteľné pri riešení kombinatorických úloh ====

=== Princíp súčtu ===
   * <math> A = A_1 \cup A_2 \cup \ldots \cup A_k </math>
   * používa sa tam, kde sa rôzne varianty spočítavajú, navzájom sa neovplyvňujú

<box 95% round green|Príklad na princíp súčtu>**Zadanie:** V triede je 30 žiakov. Koľko môžeme vytvoriť rôznych dvoj- alebo trojčlenných skupiniek?
**Riešenie:** Vypočítame, koľko môžeme vytvoriť dvojčlenných skupiniek (tých je <math>{30 \choose 2}</math>) a trojčlenných (<math>{30 \choose 3}</math>) a tieto čísla potom iba spočítame. Výsledok je <math>{30 \choose 2} + {30 \choose 3}</math>.
</box>

=== Princíp súčinu ===
  * <math> A = A_1 \times A_2 \times \ldots \times A_k </math>
  * používa sa tam, kde výsledok je súčin jednotlivých variánt, kde varianty spolu úzko súvisia
  * platí: <math>|A| = |A_1| \cdot |A_2| \cdot \ldots \cdot |A_k|</math>

<box 95% round green|Príklad na princíp súčinu>**Zadanie:** V triede je 30 žiakov, z toho 18 chlapcov a 12 dievčat. Koľko rôznych päťčlenných skupiniek takých, že 2 členovia skupinky budú chlapci a 3 dievčatá, môžeme vytvoriť?
**Riešenie:** Vyberáme 2 chlapcov z 18 (takže <math>{18 \choose 2}</math>) a 3 dievčatá z 12 (<math>{12 \choose 3}</math>). Avšak dvojčlenná skupinka chlapcov môže vytvoriť päťčlennú skupinku s ktoroukoľvek možnou trojčlennou skupinkou dievčat, takže tieto dva kombinačné výbery musíme vynásobiť. Výsledok teda bude <math>{18 \choose 2} \times {12 \choose 3}</math>. 
</box>

<note>Ak si nechcete pamätať alebo vymýšľať 2 nové príklady, posledný príklad na kombinácie v sebe spája princíp súčtu, aj princíp súčinu.</note>

=== Princíp inklúzie a exklúzie ===
  * popisuje spôsob ako môžeme zistiť počet prvkov zjednotenia dvoch alebo viacerých množín

<box 95% round green|Príklad na princíp inklúzie a exklúzie>**Zadanie:** 
{{:home:inf:sets_abc.png?200|Množiny A, B, C s neprázdným spoločným prienikom}}
Aký je počet prvkov zjednotenia množín A, B a C?
**Riešenie:**
<math>|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|</math>
</box>

<box 95% round green|Všeobecný vzorec princípu inklúzie a exklúzie ((prevzaté z: [[http://sk.wikipedia.org/wiki/Princ%C3%ADp_zapojenia_a_vypojenia|Princíp zapojenia a vypojenia - SK Wikipédia]]))>
<math>
\left|\bigcup_{i=1}^n A_i\right|=\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,i<j}\left|A_i\cap A_j\right|+\sum_{i,j,k\,:\,i< j< k}\left|A_i\cap A_j\cap A_k\right|-\ \cdots
</math>

<math>
\cdots\ +(-1)^{(n-1)} \left|A_1\cap\cdots\cap A_n\right| =\\ \sum_{k=1}^n\sum_{1\leq i_1<\ldots <i_k\leq n}(-1)^{k+1}|A_{i_1}\cap\cdots\cap A_{i_k}|
</math>
</box>


===== Predmety =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3082;kod=MB005|FI:MB005]] Základy matematiky (podzim 2005), Mgr. Ondřej Klíma, Ph.D.
  * [[https://is.muni.cz/auth/predmety/predmet.pl?studium=175195;fakulta=1433;obdobi=3523;kod=MB008|FI:MB008]] Algebra I (podzim 2006), doc. RNDr. Libor Polák, CSc.
===== Použitá literatúra =====
  * [[http://www.math.muni.cz/~klima/ZakladyM/zakladym-fi-07.html|Učebné materiály k MB005]]
  * [[http://cs.wikipedia.org/wiki/Permutace|Permutace]], Wikipedia
  * [[http://sk.wikipedia.org/wiki/Princ%C3%ADp_zapojenia_a_vypojenia|Princíp zapojenia a vypojenia]], SK Wikipédia
  * Jiří Rosický: Algebra, ISBN 80-210-2964-1, Brno 2005
===== Vypracoval =====
Dušan Katona, ICQ: 426 081 873, snad do 30.5
hotovo: <99%>
môžete kluďne niečo doplniť alebo opraviť

Otázku si přečetl pan RNDr. Jan Bouda a rámcově prošel mimo části "Princípy použiteľné pri riešení kombinatorických úloh", která byla dodána do otázky až po kontrole. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen **rámcová**, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

~~DISCUSSION~~