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_r}\rbrace \lbrace{a_1,a_2, \cdot \cdot \cdot ,a_r}\rbrace](https://lms.umb.sk/filter/tex/pix.php/e5500ade18bb8b20f2663cdcf060b3fd.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
- dvoch kilogramov máme 6 možností ... vypíšte ich. Otvorte si tabuľu Tu.
- troch kilogramov dostaneme 10 možností... vypíšte ich
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)