Kombinatorika
Partície
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.
Obyčajne sa pri štúdiu partícií rozlišujú dva prípady. Partície, v ktorých
pozostávajúcich z presne
sčítancov
symbolom
.
V ďalšom sa budeme snažiť určiť číslo
.
- záleží na poradí sčítancov
, napríklad partície
čísla
budeme považovať za rôzne
- nezáleží na poradí sčítancov
, napríklad partície
budeme považovať totožné
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![(r \leq n) (r \leq n)](https://lms.umb.sk/filter/tex/pix.php/ec3d3bebeb5fbf7c7dbcfeb6b25ae37b.png)
![P(n,r) P(n,r)](https://lms.umb.sk/filter/tex/pix.php/467c19fe7b5e14b7d6445668e917ba29.png)
V ďalšom sa budeme snažiť určiť číslo
![P(n,r) P(n,r)](https://lms.umb.sk/filter/tex/pix.php/467c19fe7b5e14b7d6445668e917ba29.png)
Nakreslime na priamke vedľa seba
bodov. Medzi nimi máme
medzier a zvoľme z nich
medzier. Táto voľba sa dá zrejme uskutočniť
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
bodov rozdelí na
častí, pričom rôznym voľbám
medzier zodpovedajú rôzne rozdelenia (aspoň čo do poradia ), čiže partícií čísla
na
častí. Dokázali sme vlastne vetu o počte partícií.
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![(n-1) (n-1)](https://lms.umb.sk/filter/tex/pix.php/410f5a188f581c6f767d90da11b142b8.png)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/6b81f7af5482940d29b22671a83ea194.png)
![C(n-1,r-1) C(n-1,r-1)](https://lms.umb.sk/filter/tex/pix.php/03bd0d8dd9a0365242ea9fb6fb922ebd.png)
spôsobmi. Vložme do nich zvislé čiarky. Napr.: Rozdeliť číslo 6 na 4 časti znamená zvoliť 3 medzery z 5.
![](https://lms.umb.sk/pluginfile.php/387410/mod_book/chapter/9109/Particie.png)
Tým sa pôvodných
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/6b81f7af5482940d29b22671a83ea194.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/5059a07a66618dd8b856fc0ffb31975a.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
Príklad. Rozklad čísla
na
nenulových sčítancov. Vypíšte všetky rozklady.
Riešenie. Číslo
má
partícií z troch sčítancov. Sú to partície:
. Otvorte si applet Tu
![6 6](https://lms.umb.sk/filter/tex/pix.php/8b958c492e4176ee946c8ffaeeabdc93.png)
![3 3](https://lms.umb.sk/filter/tex/pix.php/4047386ab7115fcd58f871a285084df2.png)
Riešenie. Číslo
![6 6](https://lms.umb.sk/filter/tex/pix.php/76213509ad1ee655ad3f1bc515e34fb6.png)
![P(6,3)=C(6-1,3-1)=C(5,2)=10 P(6,3)=C(6-1,3-1)=C(5,2)=10](https://lms.umb.sk/filter/tex/pix.php/4eb97e3753d1520f1e9cd310372e06f8.png)
![1 + 2 + 3, \; \;2 + 1 + 3,\; \; 1 + 3 + 2,\; \; 3 + 1 + 2,\; \; 2 + 3 + 1,\; \;3 + 2 + 1 1 + 2 + 3, \; \;2 + 1 + 3,\; \; 1 + 3 + 2,\; \; 3 + 1 + 2,\; \; 2 + 3 + 1,\; \;3 + 2 + 1](https://lms.umb.sk/filter/tex/pix.php/f2ec7683eb805234be1437171b171a25.png)
![1 + 1 + 4, \; \; 1 + 4 + 1, \; \; 4 + 1 + 1, \; \; 2 + 2 + 2 1 + 1 + 4, \; \; 1 + 4 + 1, \; \; 4 + 1 + 1, \; \; 2 + 2 + 2](https://lms.umb.sk/filter/tex/pix.php/7b8c80f47fbd5e500382a87ee6f9c0e7.png)
Teraz už ľahko určíme počet všetkých rôznych (aspoň) poradím partícií čísla
. Ak si to číslo označíme symbolom
, tak zrejme platí
.
Použitím vety a identity
potom dostávame
.
![n n](https://lms.umb.sk/filter/tex/pix.php/6fa45c22bd311a4aa532cffb668d86a0.png)
![P(n) P(n)](https://lms.umb.sk/filter/tex/pix.php/73ae71050f5654cb7c80e72b45cd7190.png)
![P(n)=P(n,1)+P(n,2)+ \cdot \cdot \cdot +P(n,n) P(n)=P(n,1)+P(n,2)+ \cdot \cdot \cdot +P(n,n)](https://lms.umb.sk/filter/tex/pix.php/c897270a957cc952d6bd5cf85536bcbe.png)
Použitím vety a identity
![\sum_{k=0}^{n}{ \binom {n} {k} =2n} \sum_{k=0}^{n}{ \binom {n} {k} =2n}](https://lms.umb.sk/filter/tex/pix.php/e4b4d1f3a0692580048ab24a04ca1a9b.png)
potom dostávame
![P(n) =2n-1 P(n) =2n-1](https://lms.umb.sk/filter/tex/pix.php/dcefd5ce813f482856f42bff5342490b.png)
Partície úzko súvisia s kombináciami s opakovaním. Pokúsme sa vyriešiť nasledujúcu úlohu - nakupovanie v obchode, ktorá predstavuje kombinácie s opakovaním.
Ú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. Podmienka: nákup musí obsahovať z každého druhu aspoň jeden liter mlieka. Vypíšte všetky možnosti nákupu.
Návod.
Návod.
- Označme si nákup ako usporiadanú trojicu prirodzených čísel
, kde jednotlivé čísla predstavujú koľko litrov sme nakúpili z daného druhu mlieka.
- Napríklad trojica
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
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.
- Trojica
nepredstavuje nákup, keďže neobsahuje plnotučné mlieko.
- Nákup zrejme predstavuje partície - rozklad čísla 5 na tri nenulové sčítance. 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.
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 P(5,3)=C(5-1,3-1)=C(4,2)=6](https://lms.umb.sk/filter/tex/pix.php/7f1a664b2a87d82dad90a23d98f18bab.png)