Kombinatorika
Partície
Kombinácie s opakovaním
Nech
je množina
kategórií (druhov, prvkov). Vytvorme
-tice z týchto
prvkov, v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Zrejme môže nastať aj prípad
.
![M_n= \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace M_n= \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace](https://lms.umb.sk/filter/tex/pix.php/d9d947f95ff9cf84a0b1430f4158fefe.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![r \geq n r \geq n](https://lms.umb.sk/filter/tex/pix.php/52f6cde3da6de7b06908318264b1cae7.png)
Definícia.
-kombinácie s opakovaním definujeme ako
-tice prvkov z
druhov
, v ktorých nezáleží na poradí ale prvky (druhy) sa môžu opakovať. Počet všetkých
-kombinácií s opakovaním z
prvkov budeme označovať symbolom
.
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![\lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_n}\rbrace](https://lms.umb.sk/filter/tex/pix.php/204e4df231657fe9b3b3cdf99fca6029.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![C'(n,r) C'(n,r)](https://lms.umb.sk/filter/tex/pix.php/574567130812694066e1f134cf41ff91.png)
Príklad.
V obchode predávajú tri druhy cukru: kryštálový
, práškový
a hnedý
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}
alebo 3 kilogramový nákup môže byť {2 kg práškového cukru, 1 kg hnedého cukru}
.
Všetky nákupy dvoch kilogramov budú predstavovať 2-kombinácie s opakovaním z troch druhov cukru -
. Všetky nákupy troch kilogramov budú predstavovať 3-kombinácie s opakovaním z troch druhov cukru -
.
Pokúste sa vymenovať všetky možné nákupy. Pri nákupe
V obchode predávajú tri druhy cukru: kryštálový
![k k](https://lms.umb.sk/filter/tex/pix.php/365c0b3ff8a6fa58b7ae709949b55608.png)
![p p](https://lms.umb.sk/filter/tex/pix.php/74d37d601e20578216a4981034dde4bc.png)
![h h](https://lms.umb.sk/filter/tex/pix.php/deef1d5639228d46566d18b2b61131be.png)
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 \equiv \lbrace{p,k}\rbrace = \lbrace{k,p}\rbrace](https://lms.umb.sk/filter/tex/pix.php/66a1a1ecc46e7f6b94bd8b99ed35d7ab.png)
![\equiv \lbrace{p,p,h}\rbrace = \lbrace{p,h,p}\rbrace \equiv \lbrace{p,p,h}\rbrace = \lbrace{p,h,p}\rbrace](https://lms.umb.sk/filter/tex/pix.php/338231a9a30bcefde34294862cf0457c.png)
Všetky nákupy dvoch kilogramov budú predstavovať 2-kombinácie s opakovaním z troch druhov cukru -
![C'(3,2) C'(3,2)](https://lms.umb.sk/filter/tex/pix.php/283dd5a439faf7d2c9a2f2eaad231792.png)
![C'(3,3) C'(3,3)](https://lms.umb.sk/filter/tex/pix.php/4aff63f960c794f4c35da5150cea42a8.png)
Pokúste sa vymenovať všetky možné nákupy. Pri nákupe
Dôkaz.
Nech
označuje počet výskytu prvku
v nejakej
-kombinácií
s opakovaním. Potom zrejme musí platiť rovnosť
.
Napríklad pre nákup
ide o rovnosť
Nech
![x_i x_i](https://lms.umb.sk/filter/tex/pix.php/98113093da156dc52a12acefe8f81694.png)
![a_i \in M_n a_i \in M_n](https://lms.umb.sk/filter/tex/pix.php/4e178ec1eb746e6769c62dac86c88d13.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![a_1 a_2 \cdot \cdot \cdot a_r a_1 a_2 \cdot \cdot \cdot a_r](https://lms.umb.sk/filter/tex/pix.php/ae51fd357e4a86cab340d1f761ab4ad7.png)
![x_1+x_2+ \cdot \cdot \cdot + x_n=r x_1+x_2+ \cdot \cdot \cdot + x_n=r](https://lms.umb.sk/filter/tex/pix.php/25b4457f010b14d39fc6b99ef67677bd.png)
Napríklad pre nákup
![\lbrace{k,p}\rbrace \lbrace{k,p}\rbrace](https://lms.umb.sk/filter/tex/pix.php/1b61f468ac12d5074e24886f6145ab86.png)
![1+1+0=2 1+1+0=2](https://lms.umb.sk/filter/tex/pix.php/1026704de4c4f1f2f2bd1fe4ad589434.png)
-
Ak k obidvom stranám tejto rovnosti pripočítame číslo
, tak po menšej úprave dostaneme rovnosť
-
Na rovnosť
sa môžeme pozerať ako na rozdelenie čísla
na
častí alebo ako na partície (navzájom rôznych aspoň poradím) čísla
na
častí.
- Počet takýchto partícií je rovný číslu
.Tým sme dokázali tvrdenie.
Pre nákup dvoch litrov dostávame.
![y_1+y_2+ \cdot \cdot \cdot + y_n=r+n y_1+y_2+ \cdot \cdot \cdot + y_n=r+n](https://lms.umb.sk/filter/tex/pix.php/ac9dc186772b9972939aded189c29774.png)
kde
![y_i =x_i +1 y_i =x_i +1](https://lms.umb.sk/filter/tex/pix.php/7e743372a1176d178313e982cc427218.png)
![i=1,2, \cdot \cdot \cdot ,n i=1,2, \cdot \cdot \cdot ,n](https://lms.umb.sk/filter/tex/pix.php/5b1a9294333a5ad897ca7429232723d6.png)
Pre nákup
![\lbrace{k,p}\rbrace \lbrace{k,p}\rbrace](https://lms.umb.sk/filter/tex/pix.php/1b61f468ac12d5074e24886f6145ab86.png)
![2+2+1=5 2+2+1=5](https://lms.umb.sk/filter/tex/pix.php/ea9ed1765eaa4db2feed85a96eb47f7b.png)
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ť
fliaš sirupu do
druhov/košov.
Použijeme dva symboly: • - fľaša; ↑-oddeľovač. Potom rozmiestnenia budú predstavovať
-tice, v ktorých sa symbol "•" vyskytuje
-krát (fľaše)
a symbol "↑"
-krát (\\small ( n-1 \) oddelení medzi
košmi).
Rozmiestnenie symbolov predstavuje 2 jahodové sirupy, 0 malinový a 3 pomarančové sirupy alebo (122).
Počet takých
-tíc zodpovedá počtu permutácií zo 7 prvkov s opakovaním, kde sa prvý prvok opakuje/vyskytuje
-krát a druhý
-krát. Tým sme ukázali platnosť vzťahu
=
.
"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 \small k=5](https://lms.umb.sk/filter/tex/pix.php/620862bc8e75f778137f791cd2c209c4.png)
![\small n=3 \small n=3](https://lms.umb.sk/filter/tex/pix.php/2248b4c741aa1b7f8bcd834f61393e81.png)
Použijeme dva symboly: • - fľaša; ↑-oddeľovač. Potom rozmiestnenia budú predstavovať
![\small (k+n−1) \small (k+n−1)](https://lms.umb.sk/filter/tex/pix.php/b9938eec074cf1bed5c831d336bb75c0.png)
![\small k \small k](https://lms.umb.sk/filter/tex/pix.php/4bea3db022ed38793b51b96adf34f11f.png)
![\small (n-1) \small (n-1)](https://lms.umb.sk/filter/tex/pix.php/089a291ada7e37b889b51c93667dd8a4.png)
![\small n \small n](https://lms.umb.sk/filter/tex/pix.php/a1f8cbf7dfb29c046ac9a098bb0e53a2.png)
Rozmiestnenie symbolov predstavuje 2 jahodové sirupy, 0 malinový a 3 pomarančové sirupy alebo (122).
Počet takých
![\small (k+n−1) \small (k+n−1)](https://lms.umb.sk/filter/tex/pix.php/b9938eec074cf1bed5c831d336bb75c0.png)
![\small 5 \small 5](https://lms.umb.sk/filter/tex/pix.php/581b0698e266ba12e9f6511fbb84fdd8.png)
![\small (3-1) \small (3-1)](https://lms.umb.sk/filter/tex/pix.php/8f9006b6f5e0ce6b48b0be091380522c.png)
![\small P'(5,2)= \frac{ (5+(3-1))!}{5!2! } \small P'(5,2)= \frac{ (5+(3-1))!}{5!2! }](https://lms.umb.sk/filter/tex/pix.php/6154137db6d1c46dd63535da8bdea172.png)
![\small C'(5+2,2)=21 \small C'(5+2,2)=21](https://lms.umb.sk/filter/tex/pix.php/b4d8ddbe6760abd9eb3f0b7450fc5dc2.png)