Kombinatorika
Permutácie a variácie
Permutácie s opakovaním
Definícia.
Permutácie s opakovaním z
prvkov je usporiadaná
-tica zostavená z týchto prvkov tak, že každý sa v nej vyskytuje aspoň raz.
Permutácie s opakovaním z
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![k k](https://lms.umb.sk/filter/tex/pix.php/365c0b3ff8a6fa58b7ae709949b55608.png)
Vzťah medzi
a
je nasledujúci:
Prirodzené číslo
udáva počet rôznych prvkov.
Jednotlivé prvky sa môžu opakovať. Je zvykom označovať
označuje počet všetkých prvkov, ktorých rôzne poradie skúmame, preto platí
.
![k k](https://lms.umb.sk/filter/tex/pix.php/365c0b3ff8a6fa58b7ae709949b55608.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
Prirodzené číslo
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![k k](https://lms.umb.sk/filter/tex/pix.php/365c0b3ff8a6fa58b7ae709949b55608.png)
![k = k_1 + k_2 + ... + k_n k = k_1 + k_2 + ... + k_n](https://lms.umb.sk/filter/tex/pix.php/49940cf54f9de13ebc1b3ec4f1f4e568.png)
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.
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.
Dostaneme 15 rôznych uložení 3 modrých a dvoch červených kociek.
Tvrdenie.
Počet permutácií s opakovaním z
, v ktorých sa jednotlivé prvky opakujú
-krát, je rovný číslu
Počet permutácií s opakovaním z
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![k_1,k_2, \cdot \cdot \cdot ,k_n k_1,k_2, \cdot \cdot \cdot ,k_n](https://lms.umb.sk/filter/tex/pix.php/45b409c480b47b109d07ec8c626f8441.png)
![P'(k_1,k_2, \cdot \cdot \cdot ,k_n)= P'(k_1,k_2, \cdot \cdot \cdot ,k_n)=](https://lms.umb.sk/filter/tex/pix.php/6e34607c615095ad8aa45fdba3ae2bbd.png)
![\frac{ (k_1+k_2+ \cdot \cdot \cdot +k_n)!}{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!}](https://lms.umb.sk/filter/tex/pix.php/b600771093b40de037d652ee9eb5480d.png)
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
, počet všetkých ich zoradení (permutácií) je preto
.
Pretože prvky nie sú všetky navzájom rôzne, budú sa niektoré v poradí opakovať:
Prvý prvok sa bude opakovať
.
...
Pre každý prvok
-tý je počet opakovaní rovný
. Výsledný počet poradí všetkých pasteliek je preto
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 k_1+k_2+...+k_n](https://lms.umb.sk/filter/tex/pix.php/423b15bdfca9f2528cd54c28e50279a4.png)
![\small P(k_1+k_2+...+k_n)=( k_1+k_2+...+k_n)! \small P(k_1+k_2+...+k_n)=( k_1+k_2+...+k_n)!](https://lms.umb.sk/filter/tex/pix.php/419f669b49175ef3a8381e8846623857.png)
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! \small k_1!](https://lms.umb.sk/filter/tex/pix.php/5a083f4b812a7e3a3f6c9464d00892f7.png)
...
Pre každý prvok
![i i](https://lms.umb.sk/filter/tex/pix.php/72f8ab13f56f855e098e0ea6e73251c1.png)
![\small k_i! \small k_i!](https://lms.umb.sk/filter/tex/pix.php/be2ffa88e188d252bd90c2107a4052c3.png)
![\small P'(k_1,k_2, \cdot \cdot \cdot ,k_n)= \small P'(k_1,k_2, \cdot \cdot \cdot ,k_n)=](https://lms.umb.sk/filter/tex/pix.php/d88e013e4c737433f31f512eca863ad4.png)
![\frac{ (k_1+k_2+ \cdot \cdot \cdot +k_n)!}{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!}](https://lms.umb.sk/filter/tex/pix.php/b600771093b40de037d652ee9eb5480d.png)