Kombinatorika
Site: | Virtuálna Univerzita Mateja Bela |
Course: | Kombinatorika |
Book: | Kombinatorika |
Printed by: | Guest user |
Date: | Wednesday, 3 July 2024, 11:42 AM |
Úvod
Predkladaný text vychádza z práce
významného slovenského matematika prof. RNDr. Štefana Známa, DrSc. Nami upravený učebný text rozširuje poznatky z kombinatoriky na stredných školách. Celý text vo formáte WORD si môžete stiahnuť Tu.
![^ {1)} ^ {1)}](https://lms.umb.sk/filter/tex/pix.php/8f61c9d9ac675c84c11e702c84f56f2d.png)
Kombinatorika je obor matematiky, ktorý sa zaoberá skupinami prvkov množín s definovanou vnútornou štruktúrou.
Skupiny prvkov vo všeobecnosti rozdelíme do štyroch základných tried
Prvky sa neopakujú
Prvky sa môžu opakovať
|
Nezáleží na poradí prvkov
Kombinácie bez opakovania
Kombinácie s opakovaním
|
Záleží na poradí prvkov
Variácie bez opakovania
Variácie s opakovaním
|
Poradie: V prípade, že záleží na poradí prvkov, hovoríme o usporiadaných skupinách - variáciách. Ak na poradí nezáleží, hovoríme o neusporiadaných skupinách - kombináciách.
Opakovanie: V prípade, že každý prvok sa vyskytuje najviac jedenkrát hovoríme o skupinách bez opakovania. Ak sa môže ľubovoľný prvok vyskytnúť viac krát, hovoríme o skupinách s opakovaním.
Opakovanie: V prípade, že každý prvok sa vyskytuje najviac jedenkrát hovoríme o skupinách bez opakovania. Ak sa môže ľubovoľný prvok vyskytnúť viac krát, hovoríme o skupinách s opakovaním.
Uveďte príklady skupín prvkov, ktoré budú reprezentovať každú zo štyroch základných tried.
Pri určovaní počtu skupín prvkov množín bežne využívame kombinatorické pravidlo súčinu a súčtu. Viac v práci [Farská, 2007]2) Tu.
________________________________________________________________________________________
1) Znám, Š.: Kombinatorika a teória grafov. Vysokoškolský učebný text, UK Bratislava, 1978
2) Farská, J.: Výuka kombinatoriky na střední škole s využitím webových stránek. Diplomová práce, MFF UK Praha (2007). Dostupné Tu.
2) Stodolová, K.: Klasické kombinatorické úlohy. Diplomová práce, MFF UK Praha (2012). Dostupné Tu
1) Znám, Š.: Kombinatorika a teória grafov. Vysokoškolský učebný text, UK Bratislava, 1978
2) Farská, J.: Výuka kombinatoriky na střední škole s využitím webových stránek. Diplomová práce, MFF UK Praha (2007). Dostupné Tu.
2) Stodolová, K.: Klasické kombinatorické úlohy. Diplomová práce, MFF UK Praha (2012). Dostupné Tu
Kombinácie bez opakovania
Ak
je prirodzene číslo, symbolom
označujeme akúkoľvek
-
prvkovú množinu. V ďalšom spravidla budeme predpokladať, že prvkami množiny
sú čísla
(niekedy
to zase budú písmená
.
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![1,2, \cdot \cdot \cdot ,n 1,2, \cdot \cdot \cdot ,n](https://lms.umb.sk/filter/tex/pix.php/833dc3f9574b1c4b4eef1921e9691aa2.png)
![a_1,a_2, \cdot \cdot \cdot ,a_n a_1,a_2, \cdot \cdot \cdot ,a_n](https://lms.umb.sk/filter/tex/pix.php/4461cfbbbfd45cf8f1b7f5048d04ca94.png)
Každá podmnožina
množiny
sa nazýva kombinácia množiny
. Ak
pozostáva z
prvkov, tak ju
nazývame
-kombináciou.
![M_r M_r](https://lms.umb.sk/filter/tex/pix.php/e4b386cb824db949b21ca93538ef59a3.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![M_r M_r](https://lms.umb.sk/filter/tex/pix.php/e4b386cb824db949b21ca93538ef59a3.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
nazývame
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
Pri tvorení kombinácií nezáleží na poradí prvkov! Napríklad trojice 123 a 321 predstavujú tú istú kombináciu. Prvky v kombinácii obyčajne usporadúvame v tom poradí ako v základnej množine
.
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Príklad kombinácií
Riešenie.
-
Zrejme, každá množina má jedinú
kombináciu (je ňou prázdna množina ∅).
-
Podľa definície
kombinácie sú všetky jednoprvkové podmnožiny množiny
. Sú to množiny:
. Pre kombinácie nepoužívame tento množinový zápis, ale ich píšeme jednoducho:
. Ich počet je 5.
-
kombinácie utvoríme tak, že ku každej
kombinácii a pripojíme vpravo po jednom všetky prvky, ktoré sa v množine
nachádzajú vpravo od
. Postup tvorby Tu. Ich počet je 10.
-
Obdobne získame všetky
kombinácie. Ku každej
kombinácii
pripojíme po jednom každý prvok, ktorý leží v
vpravo od
(ak taký prvok existuje) . Dostaneme tieto
kombinácie:
. Ich počet je 10.
-
Podobne postupujeme pri tvorbe
kombinácií. Ich počet je 5 a sú to
.
-
Existuje len jedna
kombinácia
.
-
Zrejme, množina
nemá nijakú
kombináciu.
Doplnková kombinácia
Dôkaz tvrdenia:
je bijekcia, preto množiny
a
majú
rovnaký počet prvkov. Tým je dôkaz ukončený.
![\phi \phi](https://lms.umb.sk/filter/tex/pix.php/b7b4dfbdf87ce82e3e51787a140cea2b.png)
![A(r) A(r)](https://lms.umb.sk/filter/tex/pix.php/7b9b78c154efbe8b79b6f7e7954a4b50.png)
![A(n-r) A(n-r)](https://lms.umb.sk/filter/tex/pix.php/b5cee282ab683e5e7d2295bd3ad55d82.png)
Príklad.
Pri výťahu, do ktorého môžu nastúpiť najviac tri osoby, stojí 5 osôb. Označme je
. Zostavte všetky trojice osôb, ktoré môžu nastúpiť do výťahu.
Riešenie:
Otvorte si zadanie Tu
Pri výťahu, do ktorého môžu nastúpiť najviac tri osoby, stojí 5 osôb. Označme je
![a,b,c,d,e a,b,c,d,e](https://lms.umb.sk/filter/tex/pix.php/d40f7a3bb56ab62d18d0cf54d0f0ee2d.png)
Riešenie:
Pevný prvok - počet kombinácií
Tvrdenie. Nech
je pevný prvok množiny
a nech
. Počet
kombinácií množiny
, ktoré
prvok
obsahujú sa rovná
prvok
neobsahujú sa rovná
![x x](https://lms.umb.sk/filter/tex/pix.php/6722c218a6f30869ef6886dc4b050a37.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![r \geq 1 r \geq 1](https://lms.umb.sk/filter/tex/pix.php/6b1f9a28d21bf40a7235445bf9449489.png)
![r - r -](https://lms.umb.sk/filter/tex/pix.php/d7c33c81f3094b9030bf21846f7ae75b.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![\ast \ast](https://lms.umb.sk/filter/tex/pix.php/74e76240bbf2c71780dcb4f86d7ac65d.png)
![x x](https://lms.umb.sk/filter/tex/pix.php/6722c218a6f30869ef6886dc4b050a37.png)
![C(n-1,r-1) C(n-1,r-1)](https://lms.umb.sk/filter/tex/pix.php/03bd0d8dd9a0365242ea9fb6fb922ebd.png)
![\ast \ast](https://lms.umb.sk/filter/tex/pix.php/74e76240bbf2c71780dcb4f86d7ac65d.png)
![x x](https://lms.umb.sk/filter/tex/pix.php/6722c218a6f30869ef6886dc4b050a37.png)
![C(n-1,r) C(n-1,r)](https://lms.umb.sk/filter/tex/pix.php/7c94b0d156140a2a3c0e3da457c5c646.png)
Dôkaz tvrdenia:
![](https://lms.umb.sk/pluginfile.php/387410/mod_book/chapter/9105/Kombinacie1%20%282%29.png)
Poznámka.
Rovnosť uvedená v dôsledku je vlastne rekurentným vzťahom. Počet
-kombinácií
-prvkovej množiny je vyjadrený pomocou počtu kombinácií
-prvkovej množiny. Stačí začať s 1-prvkovou množinou, pre ktorú platí:
a postupne určiť počet kombinácií vyššieho rádu. Toto nás privádza k myšlienke pokúsiť sa o explicitné vyjadrenie kombinačných čísel
.
Rovnosť uvedená v dôsledku je vlastne rekurentným vzťahom. Počet
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![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)
![C(1,0 )+C(1,1 )= 1+1=2\stackrel{dosledok}{=}C(2,1) C(1,0 )+C(1,1 )= 1+1=2\stackrel{dosledok}{=}C(2,1)](https://lms.umb.sk/filter/tex/pix.php/458bf6c3e8ae23a1257e8a957c0a8484.png)
a postupne určiť počet kombinácií vyššieho rádu. Toto nás privádza k myšlienke pokúsiť sa o explicitné vyjadrenie kombinačných čísel
![C(n,r) C(n,r)](https://lms.umb.sk/filter/tex/pix.php/cd46c47da4210f433490ef6731c851d3.png)
Pascalov trojuholník
Pre 1-prvkovú množinu zrejme platí:
opäť použijeme tvrdenie uvedené v dôsledku teraz pre 2-prvkovú množinu a dostaneme:
a zároveň pre 2-prvkovú množinu tiež platí:
.
Takto by sme mohli postupovať pre väčšie hodnoty
. Napríklad už poznáme hodnoty
preto ľahko spočítame hodnoty pre
. Ak tieto výpočty budeme zapisovať do trojuholníkovej schémy, tak dostaneme známy Pascalov trojuholník pre kombinačné čísla.
![\binom {1} {0} + \binom {1} {1} = 1+1=2\stackrel{dosledok}{=} \binom {2} {1} \binom {1} {0} + \binom {1} {1} = 1+1=2\stackrel{dosledok}{=} \binom {2} {1}](https://lms.umb.sk/filter/tex/pix.php/48a1653df788baea3c666e4a89268a74.png)
opäť použijeme tvrdenie uvedené v dôsledku teraz pre 2-prvkovú množinu a dostaneme:
![\binom {2} {0} + \binom {2} {1} = 1+2=3\stackrel{dosledok}{=} \binom {3} {1} \binom {2} {0} + \binom {2} {1} = 1+2=3\stackrel{dosledok}{=} \binom {3} {1}](https://lms.umb.sk/filter/tex/pix.php/daecdfecb16a0d12b6204e53cf8445fd.png)
a zároveň pre 2-prvkovú množinu tiež platí:
![\binom {2} {1} + \binom {2} {2} = 2+1=3\stackrel{dosledok}{=} \binom {3} {2} \binom {2} {1} + \binom {2} {2} = 2+1=3\stackrel{dosledok}{=} \binom {3} {2}](https://lms.umb.sk/filter/tex/pix.php/127e0a571bb9bcfe0f0231d7f0e60eeb.png)
Takto by sme mohli postupovať pre väčšie hodnoty
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![\binom {3} {0} = \binom {3} {3} =1; \binom {3} {1} = \binom {3} {2} =3 \binom {3} {0} = \binom {3} {3} =1; \binom {3} {1} = \binom {3} {2} =3](https://lms.umb.sk/filter/tex/pix.php/11f0c267bba0dd06ae5a4ac9d5ce216d.png)
preto ľahko spočítame hodnoty pre
![n=4 n=4](https://lms.umb.sk/filter/tex/pix.php/b99d8e7a87aaaa955bde521ee45ea470.png)
Kombinačné číslo
Teda
je prirodzené číslo, ktoré skrátene nazývame
- faktoriál. Symbol
definitoricky bude predstavovať číslo rovné
.
V nasledujúcom texte budeme pre kombinačné číslo používať označenie
![n!=1. 2 ...(n-1).n n!=1. 2 ...(n-1).n](https://lms.umb.sk/filter/tex/pix.php/986ec8d3e3e90f7404e103f08eecbc19.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![0! 0!](https://lms.umb.sk/filter/tex/pix.php/e931ca5498a0108813712dbdf57338c8.png)
![1 1](https://lms.umb.sk/filter/tex/pix.php/35c0804c862a635e2fe8371dc43e25d0.png)
V nasledujúcom texte budeme pre kombinačné číslo používať označenie
![C (n,r) = \binom {n} {r} C (n,r) = \binom {n} {r}](https://lms.umb.sk/filter/tex/pix.php/6ac58f6810b6c5403e4ab133c92c9431.png)
Dôkaz.
Všimnite si zaujímavý fakt:
je celé číslo pre ľubovoľné
a
,
.
-
Pre
pravdivosť tvrdenia je zrejmá.
- Predpokladajme, že platí
. Budeme dokazovať indukciou vzhľadom na číslo
.
- Overenie pravdivosti tvrdenia v prípade
prenechávame na čitateľa.
- Predpokladajme (indukčný predpoklad), že tvrdenie platí pre
.
Dokážeme, že platí aj pre.
-
Na základe predchádzajúceho dôsledku platí rovnosť:
na základe indukčného predpokladu môžeme rovnosť ďalej upraviť: applet Tu
Všimnite si zaujímavý fakt:
![\frac{n!}{(n-r)!\; r!} \frac{n!}{(n-r)!\; r!}](https://lms.umb.sk/filter/tex/pix.php/de22595406751b23ad090e1e60753ec9.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)
![1 \leq r \leq n 1 \leq r \leq n](https://lms.umb.sk/filter/tex/pix.php/b1e5f122d76bc3e6ee904efaf485140f.png)
Binomická veta
Predpokladáme, že študentom sú známe vzorce pre mocniny dvojčlena
ak
resp. pre
. Pre umocňovanie s vyšším exponentom odvodíme vzorce pomocou tzv. binomickej vety, ktorú teraz dokážeme.
![(a+b)^n (a+b)^n](https://lms.umb.sk/filter/tex/pix.php/bde0bf73f1eaa925535d94a2e20a3ece.png)
![n=2 n=2](https://lms.umb.sk/filter/tex/pix.php/188f5ac1b1ac9c5aa7eec28793155847.png)
![n=3 n=3](https://lms.umb.sk/filter/tex/pix.php/0d06e9adeb7d619dd6a583bd39e4ba33.png)
Dôkaz vety
Pri dôkaze binomickej vety vychádzame z toho, že v súčine
člen
dostaneme tak, že z dvojčlenov
vyberieme
-krát reálne číslo
a potom
-krát reálne číslo
. To je možné práve
spôsobmi, čím je dôkaz ukončený. Dôkaz binomickej vety môžeme urobiť aj pomocou úplnej matematickej indukcie.
Pri dôkaze binomickej vety vychádzame z toho, že v súčine
![(a+b)(a+b) \cdot \cdot \cdot (a+b) (a+b)(a+b) \cdot \cdot \cdot (a+b)](https://lms.umb.sk/filter/tex/pix.php/8f45c0d24a69543d12612199038189ae.png)
člen
![a^{n-k} b^k a^{n-k} b^k](https://lms.umb.sk/filter/tex/pix.php/c473d5c9843e454eb9d6e1071f7851d3.png)
dostaneme tak, že z dvojčlenov
![(a+b) (a+b)](https://lms.umb.sk/filter/tex/pix.php/b4ad4cb2ea55ae8f8d7d77f50ce3f1d2.png)
![(n-k) (n-k)](https://lms.umb.sk/filter/tex/pix.php/dcf60258da5fd8a06e9d9f8890f7f719.png)
![a a](https://lms.umb.sk/filter/tex/pix.php/e49736f09a17efd3daec360132426f43.png)
![k k](https://lms.umb.sk/filter/tex/pix.php/365c0b3ff8a6fa58b7ae709949b55608.png)
![b b](https://lms.umb.sk/filter/tex/pix.php/301d251459701f60c27be3229f1c4122.png)
![C(n,n-k)=C(n,k) C(n,n-k)=C(n,k)](https://lms.umb.sk/filter/tex/pix.php/38ccd541c05cf1d37a13b36b8c55f33a.png)
spôsobmi, čím je dôkaz ukončený. Dôkaz binomickej vety môžeme urobiť aj pomocou úplnej matematickej indukcie.
Poznámky
Permutácie a variácie
Definícia.
Nech
označujeme akúkoľvek
-prvkovú množinu. Permutáciou množiny
nazývame jej bijektívne zobrazenie na seba.
Nech
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Napríklad zobrazenie
dané predpisom:
je bijekcia množiny
na seba. Takúto permutáciu budeme symbolicky zapisovať pomocou matice
alebo jednoducho ako postupnosť
.
![f: Z_4\rightarrow Z_4 f: Z_4\rightarrow Z_4](https://lms.umb.sk/filter/tex/pix.php/55c7a6b7d686890e60321b2315e8dd67.png)
![f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1 f\left(1\right)=2,f\left(2\right)=3,\ f\left(3\right)=4,\ f\left(4\right)=1](https://lms.umb.sk/filter/tex/pix.php/c29ade1cd01335683d87c1dcb68d3deb.png)
je bijekcia množiny
![Z_4=\left\{1, 2, 3, 4\right\} Z_4=\left\{1, 2, 3, 4\right\}](https://lms.umb.sk/filter/tex/pix.php/41ccc1daa27cfe08f7e389c293a77c69.png)
![\left(\begin{matrix}1\\2\ \\\end{matrix}\begin{matrix}2\\3\\\end{matrix}\begin{matrix}3\\\ 4\ \\\end{matrix}\begin{matrix}4\\1\\\end{matrix}\right) \left(\begin{matrix}1\\2\ \\\end{matrix}\begin{matrix}2\\3\\\end{matrix}\begin{matrix}3\\\ 4\ \\\end{matrix}\begin{matrix}4\\1\\\end{matrix}\right)](https://lms.umb.sk/filter/tex/pix.php/a44c6a673749e9d52e26e6eef10c9814.png)
alebo jednoducho ako postupnosť
![\mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1} \mathbf{2}\ \mathbf{3}\ \mathbf{4}\ \mathbf{1}](https://lms.umb.sk/filter/tex/pix.php/b474312f0c529f2f9a7a90f80b80773c.png)
Príklad.
Nájdite všetky permutácie ľubovoľnej štvorprvkovej množiny
.
Riešenie.
Nech
je bijekcia. Potom obraz prvku a môže nadobúdať štyri rôzne hodnoty:
.
Ak
, tak obraz prvku
môže nadobúdať tri rôzne hodnoty
Ak už
, tak obraz prvku
môže nadobúdať dve rôzne hodnoty atď. Schematicky to môžeme znázorniť nasledovne
Pre
sme dostali permutácie
. Podobne budeme postupovať pre
. Všetky permutácie prehľadne zapíšeme pomocou nasledujúcej tabuľky.
![](https://lms.umb.sk/pluginfile.php/387410/mod_book/chapter/9113/Sn%C3%ADmka2.PNG)
Na základe postupu použitého v predchádzajúcom príklade môžeme dokázať tvrdenie uvedené vo vete 9, v ktorej je uvedený vzorec pre určenie počtu všetkých permutácii ľubovoľnej množiny
.
Nájdite všetky permutácie ľubovoľnej štvorprvkovej množiny
![M_4=\left\{a,b,c,d\right\} M_4=\left\{a,b,c,d\right\}](https://lms.umb.sk/filter/tex/pix.php/1ed708fe6cede687180badb7ffd7158d.png)
Riešenie.
Nech
![f: M_4\rightarrow M_4 f: M_4\rightarrow M_4](https://lms.umb.sk/filter/tex/pix.php/6e854f12fb73b415b1f8d93e0fa7e736.png)
![f\left(a\right)=a,\ f\left(a\right)=b,\ f\left(a\right)=c,\ f\left(a\right)=d f\left(a\right)=a,\ f\left(a\right)=b,\ f\left(a\right)=c,\ f\left(a\right)=d](https://lms.umb.sk/filter/tex/pix.php/45412e8735f0e4264f8299bec8fbf82c.png)
Ak
![f\left(a\right)=a f\left(a\right)=a](https://lms.umb.sk/filter/tex/pix.php/fa3490401f8abc9afd6334ff4a815ae8.png)
![b b](https://lms.umb.sk/filter/tex/pix.php/301d251459701f60c27be3229f1c4122.png)
![f\left(b\right)=b,\ f\left(b\right)=c,\ f\left(b\right)=d f\left(b\right)=b,\ f\left(b\right)=c,\ f\left(b\right)=d](https://lms.umb.sk/filter/tex/pix.php/a002d4e597eafa9042265b57f2350083.png)
Ak už
![\ f\left(b\right)=b \ f\left(b\right)=b](https://lms.umb.sk/filter/tex/pix.php/fa778fff68b91cb2c7b0eae4f8e9fa68.png)
![c c](https://lms.umb.sk/filter/tex/pix.php/2b8412805efd6ae2233444f7704e9684.png)
Pre
![f\left(a\right)=a f\left(a\right)=a](https://lms.umb.sk/filter/tex/pix.php/fa3490401f8abc9afd6334ff4a815ae8.png)
![abcd, abdc, acbd, acdb,adcb,adbc abcd, abdc, acbd, acdb,adcb,adbc](https://lms.umb.sk/filter/tex/pix.php/93b3d75cc0c0b26c0bee867d65a859da.png)
![f\left(a\right)=b, f\left(a\right)=c, f\left(a\right)=d f\left(a\right)=b, f\left(a\right)=c, f\left(a\right)=d](https://lms.umb.sk/filter/tex/pix.php/7d86ff426190389b0112796c4a0eb294.png)
Na základe postupu použitého v predchádzajúcom príklade môžeme dokázať tvrdenie uvedené vo vete 9, v ktorej je uvedený vzorec pre určenie počtu všetkých permutácii ľubovoľnej množiny
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Tvrdenie. Pre počet permutácií
množiny
platí vzťah ![P(M_n)=n! P(M_n)=n!](https://lms.umb.sk/filter/tex/pix.php/19737a10b615e3c90dd10c8cefda4ffa.png)
Dôkaz tohto tvrdenia môžeme ľahko urobiť ak využijeme kombinatorické pravidlo súčinu.
![P\left(M_n\right) P\left(M_n\right)](https://lms.umb.sk/filter/tex/pix.php/4df6d11d8e91349f5245d1230c515373.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![P(M_n)=n! P(M_n)=n!](https://lms.umb.sk/filter/tex/pix.php/19737a10b615e3c90dd10c8cefda4ffa.png)
Dôkaz tohto tvrdenia môžeme ľahko urobiť ak využijeme kombinatorické pravidlo súčinu.
Kombinatorické pravidlo súčinu
Kombinatorické pravidlo súčinu
Nech
sú množiny majúce po rade
prvkov. Potom počet usporiadaných
-tíc, ktorých prvý prvok je z množiny
, druhý z množiny
a
-tý z množiny
je rovný súčinu
.
Dôkaz prenechávame na čitateľa. Odporúčame použiť matematickú indukciu vzhľadom na počet množín
.
Nech
![A_1,A_2,\ldots,A_n A_1,A_2,\ldots,A_n](https://lms.umb.sk/filter/tex/pix.php/02ebf109280af61d168f622168468449.png)
![a_1,a_2,\ldots,a_n a_1,a_2,\ldots,a_n](https://lms.umb.sk/filter/tex/pix.php/1af8849942aa72d418478e0ef1d4a183.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![A_1 A_1](https://lms.umb.sk/filter/tex/pix.php/0c0e1a359ea8a473d2fb0278d8647ada.png)
![A_2 A_2](https://lms.umb.sk/filter/tex/pix.php/782eccb65701b1f61af465c533a9f1c6.png)
![n n](https://lms.umb.sk/filter/tex/pix.php/bfbdd7d089006253c9a32f7c78c15270.png)
![A_n A_n](https://lms.umb.sk/filter/tex/pix.php/2c9ffbabaf0e78f5d63201defff97c84.png)
![a_1a_2\ldots a_n a_1a_2\ldots a_n](https://lms.umb.sk/filter/tex/pix.php/f8ef2759f4d1a0116eaadac868bf00c5.png)
Dôkaz prenechávame na čitateľa. Odporúčame použiť matematickú indukciu vzhľadom na počet množín
![A_i A_i](https://lms.umb.sk/filter/tex/pix.php/3eba73fc575e61ec55e0a641fa07425e.png)
Príklad 1.
V košíku je 12 jabĺk a 10 hrušiek. Peter si má z neho vybrať buď jablko, alebo hrušku tak, aby Viera, ktorá si po ňom vyberie jedno jablko a jednu hrušku, mala čo najväčšiu možnosť výberu. Určte, čo si má vybrať Peter.
Riešenie.
Peter má pri výbere dve možnosti. Buď si vyberie jablko, alebo hrušku. Otvorte si tabuľu Tu.
V košíku je 12 jabĺk a 10 hrušiek. Peter si má z neho vybrať buď jablko, alebo hrušku tak, aby Viera, ktorá si po ňom vyberie jedno jablko a jednu hrušku, mala čo najväčšiu možnosť výberu. Určte, čo si má vybrať Peter.
Riešenie.
Peter má pri výbere dve možnosti. Buď si vyberie jablko, alebo hrušku. Otvorte si tabuľu Tu.
Príklad 2.
Karol má červenú, modrú, žltú a zelenú kravatu. Ďalej má červenú, modrú a zelenú košeľu. Koľkými spôsobmi si môže obliecť oboje, aby nemal košeľu a kravatu rovnakej farby?
Riešenie.
Najskôr spočítajte koľko možností je nevhodných - rovnakej farby kravata aj košeľa. Potom použite kombinatorické pravidlo súčinu. Otvorte si tabuľu Tu.
Karol má červenú, modrú, žltú a zelenú kravatu. Ďalej má červenú, modrú a zelenú košeľu. Koľkými spôsobmi si môže obliecť oboje, aby nemal košeľu a kravatu rovnakej farby?
Riešenie.
Najskôr spočítajte koľko možností je nevhodných - rovnakej farby kravata aj košeľa. Potom použite kombinatorické pravidlo súčinu. Otvorte si tabuľu Tu.
Cvičenie 1..
Koľko rôznych usporiadaných dvojíc čísel môžeme dostať, keď hodíme dvakrát kockou s jedným až šiestimi okami na jednotlivých stenách?
Riešenie
V prvom hode môže padnúť jedno zo šiestich čísel. To znamená, že máme 6 možností (6 rôznych hodnôt na vrchnej strane kocky).
Ku každej hodnote môže v druhom hode opäť padnúť jedno zo šiestich čísel, tj opäť 6 možností.
Počet rôznych dvojíc je teda 6 x 6 = 36." Tabuľa
Riešenie
V prvom hode môže padnúť jedno zo šiestich čísel. To znamená, že máme 6 možností (6 rôznych hodnôt na vrchnej strane kocky).
Ku každej hodnote môže v druhom hode opäť padnúť jedno zo šiestich čísel, tj opäť 6 možností.
Počet rôznych dvojíc je teda 6 x 6 = 36." Tabuľa
Cvičenie 2..
Určite počet všetkých trojciferných prirodzených čísel,
a) v ktorých dekadickom zápise sa každá číslica vyskytuje najviac raz;
b) v ktorých dekadickom zápise sa nejaká číslica vyskytuje aspoň dvakrát
Riešenie
a)
- možnosti pre prvú číslicu: 1 až 9 → 9 možností;
- možnosti pre druhú číslicu: 0 až 9, ale bez tej číslice, ktorá bola vybraná pre prvú číslicu → 10 − 1 = 9 možností;
- možnosti pre tretiu číslicu: 0 až 9, ale bez číslic, ktoré boli vybrané pre prvú a druhú číslicu → 10 − 2 = 8 možností.
Podľa kombinatorického pravidla súčinu je teda celkom 9 ⋅ 9 ⋅ 8 = 648 takýchto čísel.
b)
Všetkých trojciferných čísel je 900 (čísla 100 až 999), z toho čísel, v ktorých dekadickom zápise sa každá číslica vyskytuje najviac raz, je 648 – viď prípad a). Zostáva teda 900-648 čísel, v ktorých dekadickom zápise sa nejaká číslica opakuje aspoň dvakrát."
a) v ktorých dekadickom zápise sa každá číslica vyskytuje najviac raz;
b) v ktorých dekadickom zápise sa nejaká číslica vyskytuje aspoň dvakrát
Riešenie
a)
- možnosti pre prvú číslicu: 1 až 9 → 9 možností;
- možnosti pre druhú číslicu: 0 až 9, ale bez tej číslice, ktorá bola vybraná pre prvú číslicu → 10 − 1 = 9 možností;
- možnosti pre tretiu číslicu: 0 až 9, ale bez číslic, ktoré boli vybrané pre prvú a druhú číslicu → 10 − 2 = 8 možností.
Podľa kombinatorického pravidla súčinu je teda celkom 9 ⋅ 9 ⋅ 8 = 648 takýchto čísel.
b)
Všetkých trojciferných čísel je 900 (čísla 100 až 999), z toho čísel, v ktorých dekadickom zápise sa každá číslica vyskytuje najviac raz, je 648 – viď prípad a). Zostáva teda 900-648 čísel, v ktorých dekadickom zápise sa nejaká číslica opakuje aspoň dvakrát."
Úlohy
Úloha 1.
Koľko trojciferných čísel môžeme vytvoriť z číslic
, ak sa žiadna číslica neopakuje?
Riešenie
Výsledok: V(5,3) = 60
Koľko trojciferných čísel môžeme vytvoriť z číslic
![1,2,3,4,5 1,2,3,4,5](https://lms.umb.sk/filter/tex/pix.php/afe805e5a3c3ec7fa05645a6a2a6e607.png)
Riešenie
Výsledok: V(5,3) = 60
Úloha 2.
Koľko rôznych jedno až štvorciferných čísel môžeme vytvoriť z cifier 0, 1, 2, 3?
Riešenie
Keby medzi ciframi nebola nula, tak počet všetkých jedno až štvorciferných čísel by bol súčet čísel
V(4,1)+V(4,2)+V(4,3)+V(4,3) = 4 + 12 + 24 + 24 = 64.
Pre počet všetkých jedno až štvorciferných čísel začínajúcich nulou bude zrejme platiť
V(3,1)+V(3,2)+V(3,3) = 1 + 3 + 6 + 6 =16.
Pre počet všetkých jedno až štvorciferných čísel z cifier 0, 1, 2, 3 je rovný
64 - 16
Koľko rôznych jedno až štvorciferných čísel môžeme vytvoriť z cifier 0, 1, 2, 3?
Riešenie
Keby medzi ciframi nebola nula, tak počet všetkých jedno až štvorciferných čísel by bol súčet čísel
V(4,1)+V(4,2)+V(4,3)+V(4,3) = 4 + 12 + 24 + 24 = 64.
Pre počet všetkých jedno až štvorciferných čísel začínajúcich nulou bude zrejme platiť
V(3,1)+V(3,2)+V(3,3) = 1 + 3 + 6 + 6 =16.
Pre počet všetkých jedno až štvorciferných čísel z cifier 0, 1, 2, 3 je rovný
64 - 16
Úloha 3.
K vyhotoveniu vlajky, ktorá má byť zložená z troch rôznofarebných vodorovných pruhov, sú k dispozícii látky farby modrej, červenej, zelenej, bielej a žltej.
K vyhotoveniu vlajky, ktorá má byť zložená z troch rôznofarebných vodorovných pruhov, sú k dispozícii látky farby modrej, červenej, zelenej, bielej a žltej.
- Určte počet vlajok, ktoré možno z látok týchto 5 farieb zostaviť.
- Koľko ich má v strede modrý pruh?
- Koľko ich má (kdekoľvek) biely pruh?
- Koľko ich nemá uprostred červený pruh?
Vytváranie farebnej zostavy/vlajky pomocou appletu. Zvoľte farbu a priraďte ju niektorému štvorčeku mriežky.
Cvičenie. Vytvorte všetky zostavy, ktoré sú zložené z 3 štvorčekov siete. Použite len 2 farby - modrú a žltú.
Variácie s opakovaním
Z prvkov množiny
je možné vytvoriť skupiny po
prvkov najvoľnejšie tak, že na každé miesto v tejto skupine umiestnime ľubovoľný prvok množiny
. Takto vzniknutým skupinám budeme hovoriť variácie s opakovaním. V závere predchádzajúcej kapitoly sme v rámci cvičenia vytvárali takéto skupiny - farebné zostavy. Farby sa mohli opakovať a zároveň záležalo na poradí.
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.png)
Definícia.
Usporiadaná
-tica prvkov množiny
sa nazýva
-variácia s opakovaním množiny
.
Počet všetkých
-variácií s opakovaním množiny
budeme označovať symbolom
.
Usporiadaná
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![\small V'(n,r) \small V'(n,r)](https://lms.umb.sk/filter/tex/pix.php/29f26a8001d993c3a7d2d3bb59f56e19.png)
Príklad.
Utvorte všetky 3-variácie s opakovaním množiny
.
Riešenie.
Postupne vytvárajme
-variácie s opakovaním množiny
.
Utvorte všetky 3-variácie s opakovaním množiny
![\small M_2=\left\{1,\ 2\right\} \small M_2=\left\{1,\ 2\right\}](https://lms.umb.sk/filter/tex/pix.php/4251a8bc2018a7218f49dac9aa6e0cf1.png)
Riešenie.
Postupne vytvárajme
![1,\; 2 ,\; 3 1,\; 2 ,\; 3](https://lms.umb.sk/filter/tex/pix.php/fcc0de8ae11d4475cc0a5d28d68f7d06.png)
![\small M_2 \small M_2](https://lms.umb.sk/filter/tex/pix.php/90dc18adf304afaa42381e6f163781c7.png)
Veta.
Pre počet všetkých
-variácií s opakovaním množiny
platí vzťah
Dôkaz.
Použitím matematickej indukcie. Pre
je tvrdenie pravdivé, presvedčte sa o tom. Predpokladajme, že tvrdenie platí pre
. Teda
Všetky usporiadané
-tice s opakovaním množiny
možno vytvoriť z
-tíc tak, že ku každej dodáme na koniec po jednom každý prvok
množiny
. Preto z každej
-tice získame
rôznych
-tíc. Využitím indukčného predpokladu dostaneme
.
Pre počet všetkých
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/00cee01a69aebc07ff0ee38576f3a70c.png)
![\small V'(n,r)=n^r \small V'(n,r)=n^r](https://lms.umb.sk/filter/tex/pix.php/99d96b424546882851abf8ac89eec551.png)
Dôkaz.
Použitím matematickej indukcie. Pre
![r=1,2 r=1,2](https://lms.umb.sk/filter/tex/pix.php/a1f6318add3560f84d2dc63812c6cf0b.png)
![r-1 r-1](https://lms.umb.sk/filter/tex/pix.php/884b04b62c377f0efc6f93bb99df5194.png)
![\small V'(n,r-1)=n^{r-1} \small V'(n,r-1)=n^{r-1}](https://lms.umb.sk/filter/tex/pix.php/361d8c9ecd3a4418b5c84a4094cbde02.png)
Všetky usporiadané
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/bc20dea0783de7178216591827290b39.png)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/467f914e5a4a7eab32d6892e81c8a564.png)
![\small M_n \small M_n](https://lms.umb.sk/filter/tex/pix.php/bc20dea0783de7178216591827290b39.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/bfbdd7d089006253c9a32f7c78c15270.png)
![r r](https://lms.umb.sk/filter/tex/pix.php/1af9dcecc465950e25f7153943970180.png)
![\small V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r \small V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r](https://lms.umb.sk/filter/tex/pix.php/d90bd72f140a98af270c9d705c580616.png)
Urobte dôkaz využitím kombinačného pravidla súčinu.
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)
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)
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)
Príklady/Cvičenie
- Vyžitím binomickej vety vypočítajte
.
- Určte desiaty člen binomického rozvoja výrazu
- "V obchode majú dva druhy kompótu: ananásový a hruškový. Určte počet všetkých možností nákupu 5 balení kompótu v tomto obchode." Otvorte tabuľu Tu.
Zistite, či riešením nasledujúcej úlohy dostaneme rovnaký výsledok?
"V obchode majú 5 druhov múky v kilogramovom balení: hladkú, polohrubú, hrubú, špeciálnu hladkú a bezlepkovú. Určte počet všetkých možností nákupu 2 kg múky v tomto obchode." Otvorte tabuľu Tu. - Kombinačné čísla
môžeme ľahko určiť z tabuľky
Otvorte tabuľku Tu
- Určte počet všetkých trojuholníkov, z ktorých žiadne dva nie sú zhodné a každá ich strana má jednu z veľkostí daných číslami 5, 6, 7, 8, 9, 10. [Rieš = 53: Zrejme pre trojice 448,449,459 neexistuje trojuholník - trojuholníková nerovnosť; máme 6 druhov strán a vytvárame trojice].
Princíp zapojenia a vypojenia
Príklad.
Písomnú prácu z matematiky písalo 35 študentov. Písomka obsahovala tri úlohy A, B, C. Vieme, že
Typické stredoškolské riešenie využíva grafickú schému - Vennov diagram, pomocou ktorého sa graficky vyjadruje príslušnosť prvkov k množine. V našom prípade to bude Vennov diagram pre tri množiny.
V diagrame postupne zapisujeme hodnoty
Písomnú prácu z matematiky písalo 35 študentov. Písomka obsahovala tri úlohy A, B, C. Vieme, že
- Úlohu A vyriešilo 22 študentov, úlohu B vyriešilo 26 študentov, úlohu C vyriešilo 23 študentov.
- Úlohu A aj úlohu B vyriešilo 16 študentov, úlohu A aj úlohu C vyriešilo 14 študentov, úlohu B aj úlohu C vyriešilo 17 študentov.
- Všetky úlohy vyriešilo 10 študentov. Zistite koľko študentov nevyriešilo ani jednu úlohu?
Typické stredoškolské riešenie využíva grafickú schému - Vennov diagram, pomocou ktorého sa graficky vyjadruje príslušnosť prvkov k množine. V našom prípade to bude Vennov diagram pre tri množiny.
![](https://lms.umb.sk/pluginfile.php/387410/mod_book/chapter/9117/Venov.png)
V diagrame postupne zapisujeme hodnoty
Základný vzťah
V tejto časti budeme používať symboliku z predchádzajúcej kapitoly. Napríklad
označuje počet všetkých objektov skúmanej množiny.
![N N](https://lms.umb.sk/filter/tex/pix.php/a4b1432432038fbb6d340407982580cb.png)
Tvrdenie
V kombinatorike princíp zapojenia a vypojenia alebo princíp exklúzie a inklúzie hovorí, že ak
sú konečné množiny, tak
V kombinatorike princíp zapojenia a vypojenia alebo princíp exklúzie a inklúzie hovorí, že ak
![A_1, ..., A_n A_1, ..., A_n](https://lms.umb.sk/filter/tex/pix.php/181b68df9c78992f386971dc70a43779.png)
![N(0)=N- \sum{N(a_i)} + \sum{N(a_ra_s)} - \sum{N(a_ra_sa_t)} + \cdot \cdot \cdot(-1)^{n} \sum{N(a_ra \cdot \cdot \cdot a_n)} N(0)=N- \sum{N(a_i)} + \sum{N(a_ra_s)} - \sum{N(a_ra_sa_t)} + \cdot \cdot \cdot(-1)^{n} \sum{N(a_ra \cdot \cdot \cdot a_n)}](https://lms.umb.sk/filter/tex/pix.php/8afe05598b5d770216ec66a2f69e64fc.png)
Dôkaz tvrdenia.
- Objekt, ktorý nemá ani jednu z vlastností
prispieva jednotkou k číslu
aj k číslu
, ale vo zvyšných sčítancoch na pravej strane sa nevyskytuje.
- Ak nejaký objekt má
vlastností, kde
, potom prispieva
- jednotkou k číslu N
-
jednotkami k sume
(lebo prispieva jednotkou k
sčítancom)
jednotkami k sume
. (Z
vlastností daného objektu možno vybrať
dvojíc, preto objekt prispieva k tejto sume
jednotkami), atď.
- Teda objekt s
vlastnosťami prispieva k pravej strane rovnosti hodnotou
- Podľa binomickej vety vieme, že táto hodnota (striedavé sčítanie a odčítanie kombinačných čísel
je rovná nule.
- Preto celkový príspevok objektu s aspoň jednou vlastnosťou k obidvom stranám rovnosti je rovný nule.
Problém šatniarky
Problém šatniarky.
Pri vstupe do klubu si každý z piatich pánov odloží klobúk do šatne. Pri odchode šatniarka vydá náhodne každému pánovi jeden klobúk bez toho, že by skontrolovala, či je to správny klobúk. Aké sú šance, že žiaden z pánov nedostane vlastný klobúk?
Pri vstupe do klubu si každý z piatich pánov odloží klobúk do šatne. Pri odchode šatniarka vydá náhodne každému pánovi jeden klobúk bez toho, že by skontrolovala, či je to správny klobúk. Aké sú šance, že žiaden z pánov nedostane vlastný klobúk?
- Pravdepodobnosť bude predstavovať podiel počtu permutácií bez pevného bodu k počtu všetkých permutácií.
- Ide o permutácie klobúkov. Šatniarka priraďuje klobúky pánom.
- Jedno priradenie klobúkov pánom je permutácia. Predstavme si, že páni sú očíslovaní a klobúky tiež.
- Keď permutácia má pevný bod, tak to znamená, že niektorý klobúk bol daný správne svojmu pánovi.
- Čitateľ bude rovný počtu všetkých permutácií
mínus počet permutácií s aspoň jedným pevným bodom - to musíme spočítať.
- Na permutácie s aspoň jedným pevným bodom sa uplatňuje princíp inklúzie a exklúzie.
Aplikovaním princípu zapojenia a vypojenia (tvrdenie v predchádzajúcej kapitole) dostaneme: