Kombinatorika
Portál: | Virtuálna Univerzita Mateja Bela |
Kurz: | Didaktika matematiky |
Kniha: | Kombinatorika |
Vytlačil(a): | Hosťovský používateľ |
Dátum: | streda, 3 júla 2024, 11:27 |
Ú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.
Od draka k trojuholníkom
Drak.
Kráľ má osem dcér. Určite, koľkými spôsobmi môže kráľ vybrať dve dcéry, ktoré chce zjesť stohlavý drak. Vzhľadom na to, že drak bude jesť obe princezné naraz, nezáleží na tom (na poradí), ktorú vyberieme ako prvú a ktorú ako druhú.
Kráľ má osem dcér. Určite, koľkými spôsobmi môže kráľ vybrať dve dcéry, ktoré chce zjesť stohlavý drak. Vzhľadom na to, že drak bude jesť obe princezné naraz, nezáleží na tom (na poradí), ktorú vyberieme ako prvú a ktorú ako druhú.
Riešenie.
Postupne vyberáme princezné na raňajky:
možností. Zrejme nemá cenu rozlišovať výbery typu princezná {Anna, Dana} od {Dana, Anna} resp. kráľov výber {Anna, Dana} je ten istý ako výber {Dana, Anna}. Pozrite si obrázok. Z matematického pohľadu: dvojicu {Anna, Dana} sme započítali dvakrát. Z toho dôvodu počet všetkých možných rôznych kráľových výberov bude rovný číslu
.
Princezné A - Anna, B- Barbora, ..., D - Dana, ...
Záver: Každú možnosť sme započítali dvakrát. Preto počet možností ako nakŕmiť draka je polovičná:
.
Postupne vyberáme princezné na raňajky:
- výber: 8 možností
- výber: 7 možností
![\small p = 8 \times 7 \times ... \small p = 8 \times 7 \times ...](https://lms.umb.sk/filter/tex/pix.php/e129bc6624f831d7c646c9144c289a87.png)
![\frac{p}{2} \frac{p}{2}](https://lms.umb.sk/filter/tex/pix.php/d9191ec71f6654c13a6010a3bd69ef7f.png)
![](https://lms.umb.sk/pluginfile.php/159053/mod_book/chapter/10459/Sn%C3%ADmka1.png)
Princezné A - Anna, B- Barbora, ..., D - Dana, ...
Záver: Každú možnosť sme započítali dvakrát. Preto počet možností ako nakŕmiť draka je polovičná:
![p= \frac{8.7}{2} =28 p= \frac{8.7}{2} =28](https://lms.umb.sk/filter/tex/pix.php/88de9035fed2c6d2cd9b2b2f73272fe9.png)
Analogická a typická úloha pre stredné školy je sformulovaná takto:
Priamky.
V rovine je daných
bodov (
), z ktorých žiadne tri neležia v jednej priamke. Určite, koľko rôznych priamok je určených týmito bodmi. Odvodený vzťah overte
dosadením konkrétneho čísla miesto
.
V rovine je daných
![\small n \small n](https://lms.umb.sk/filter/tex/pix.php/c8d96a80294a355f5bb30dea8f45254c.png)
![\small n \geq 2 \small n \geq 2](https://lms.umb.sk/filter/tex/pix.php/85cc84a268f028b5d3446ba1c38baebc.png)
![\small n \small n](https://lms.umb.sk/filter/tex/pix.php/c8d96a80294a355f5bb30dea8f45254c.png)
Riešenie.
Priamka je určená práve dvoma rôznymi bodmi (základná axióma euklidovskej roviny). Budeme hľadať, koľkými spôsobmi je možné vybrať dva rôzne body: Ku každému bodu, ktorý sme vybrali ako prvý, môžeme vystriedať všetky body vybrané ako druhé. Celkový počet takto vybraných priamok je rovný číslu
.
Keďže každú možnosť sme započítali dvakrát, počet
rôznych priamok bude určený vzťahom (vzorcom)
.
Priamka je určená práve dvoma rôznymi bodmi (základná axióma euklidovskej roviny). Budeme hľadať, koľkými spôsobmi je možné vybrať dva rôzne body: Ku každému bodu, ktorý sme vybrali ako prvý, môžeme vystriedať všetky body vybrané ako druhé. Celkový počet takto vybraných priamok je rovný číslu
![\small n.(n-1) \small n.(n-1)](https://lms.umb.sk/filter/tex/pix.php/234f558cf7ea417f51d135112ea43922.png)
![\small p \small p](https://lms.umb.sk/filter/tex/pix.php/808500f8856652a623272d5c67cfef33.png)
![p=\frac{n.(n-1)}{2} p=\frac{n.(n-1)}{2}](https://lms.umb.sk/filter/tex/pix.php/dbb8378a1743f823f0d259d01d467d92.png)
Trojuholníky.
Je daný štvorec
a na každej z jeho strán je daných
vnútorných bodov. Určite počet trojuholníkov, ktoré majú vrcholy v týchto
bodoch a na rôznych stranách štvorca
.
Je daný štvorec
![\small ABCD \small ABCD](https://lms.umb.sk/filter/tex/pix.php/69ddf1de17b4c3581b414a534711bbb3.png)
![\small k \small k](https://lms.umb.sk/filter/tex/pix.php/6369aa705d84184165a5878004551548.png)
![\small ABCD \small ABCD](https://lms.umb.sk/filter/tex/pix.php/69ddf1de17b4c3581b414a534711bbb3.png)
![](https://lms.umb.sk/pluginfile.php/159053/mod_book/chapter/10459/Sn%C3%ADmka2.png)
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/159053/mod_book/chapter/2843/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ť:
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
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/159053/mod_book/chapter/2847/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. 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.
- Nákup predstavuje partície, v ktorých záleží na poradí. 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_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)
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
4,5,6,7,8,9 .
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/159053/mod_book/chapter/4421/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?
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
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
Úlohy
Úloha 2.
Koľko rôznych jedno až štvorciferných čísel môžeme vytvoriť z cifier 0, 1, 2, 3?
Koľko rôznych jedno až štvorciferných čísel môžeme vytvoriť z cifier 0, 1, 2, 3?
Ú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
.
![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)
![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)
![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)
![V'(n,r) V'(n,r)](https://lms.umb.sk/filter/tex/pix.php/af0d42e5df373c20fc46a8a8971e3caa.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
.
![M_2=\left\{1,\ 2\right\} M_2=\left\{1,\ 2\right\}](https://lms.umb.sk/filter/tex/pix.php/a1ef8409a2d5bbcb4fc96d8b24f8d093.png)
Riešenie.
Postupne vytvárajme
![1,\; 2 ,\; 3 1,\; 2 ,\; 3](https://lms.umb.sk/filter/tex/pix.php/fcc0de8ae11d4475cc0a5d28d68f7d06.png)
![M_2 M_2](https://lms.umb.sk/filter/tex/pix.php/b62752675ac6d21b4fe23b787d16c18f.png)
Veta. Pre počet všetkých
-variácií s opakovaním množiny
platí vzťah
Dôkaz vety.
Dôkaz je výhodné urobiť pomocou 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
.
![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)
![V'(n,r)=n^r V'(n,r)=n^r](https://lms.umb.sk/filter/tex/pix.php/c62ffcfef6881b6e85cc518bc68f721d.png)
Dôkaz vety.
Dôkaz je výhodné urobiť pomocou 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)
![V'(n,r-1)=n^{r-1} V'(n,r-1)=n^{r-1}](https://lms.umb.sk/filter/tex/pix.php/0561b2c70aedd1a7346879e6772ab4c2.png)
Všetky usporiadané
![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)
![(r-1) (r-1)](https://lms.umb.sk/filter/tex/pix.php/467f914e5a4a7eab32d6892e81c8a564.png)
![M_n M_n](https://lms.umb.sk/filter/tex/pix.php/7ccc3e4bab00ea0a33023e7bab50dbf9.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)
![V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r V'(n,r)=n.V'(n,r-1)=n.n^{r-1}=n^r](https://lms.umb.sk/filter/tex/pix.php/63202d45ae45c56752201ffa99019823.png)
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)
Ukážka.
Ak máme napr. 3 žlté kocky, 1 modré kocka a 1 červená kocka a chceme ich poukladať do radu, jedná sa o permutácie s opakovaním z troch prvkov, kde prvý prvok sa opakuje 3x, druhý 1xa tretí 1x.
Ak máme napr. 3 žlté kocky, 1 modré kocka a 1 červená kocka a chceme ich poukladať do radu, jedná sa o permutácie s opakovaním z troch prvkov, kde prvý prvok sa opakuje 3x, druhý 1xa tretí 1x.
(žltá, modrá, červená kocka)
.
Skúste vypísať všetky permutácie, ktoré vyhovujú zadaniu.
Príklad
Cvičenie.
Určte, koľkými spôsobmi je možné poukladať do radu 2 modré a 2 červené kocky.
Určte, koľkými spôsobmi je možné poukladať do radu 2 modré a 2 červené kocky.
Riešenie.
Pri riešení využite priložený applet
Pri riešení využite priložený applet
Cvičenie.
Nájdite všetky možnosti, ako môže na 3 rovnakých hracích kockách padnúť súčet 11. (na poradí kociek nezáleží)
Nájdite všetky možnosti, ako môže na 3 rovnakých hracích kockách padnúť súčet 11. (na poradí kociek nezáleží)
Riešenie.
Pozrite si kurz "Elementárna matematika 6" stránke Tu, časť Permutácie s opakovaním; Odporúčame; odkaz: programy. Program si stiahnite a extrahujte. Potom vyberte časť 9. Vypíšte všetky možnosti pomocou tohto programu. Pozrite si nasledujúci obrázok.
S touto úlohou úzko súvisí úloha z pravdepodobnosti:
Pozrite si kurz "Elementárna matematika 6" stránke Tu, časť Permutácie s opakovaním; Odporúčame; odkaz: programy. Program si stiahnite a extrahujte. Potom vyberte časť 9. Vypíšte všetky možnosti pomocou tohto programu. Pozrite si nasledujúci obrázok.
![](https://lms.umb.sk/pluginfile.php/159053/mod_book/chapter/4424/Sn%C3%ADmka1.png)
S touto úlohou úzko súvisí úloha z pravdepodobnosti:
- "Aká je pravdepodobnosť, že na troch hracích kockách padne súčet rovný číslu 11. Pozrite si riešenie tejto úlohy z pravdepodobnosti na stránke "Príklady.eu.", časť pravdepodobnosť, príklad 4. Tu. Spustite interaktívny program pre výpočet pravdepodobnosti Tu.
- Riešte čiastkové úlohy "Vypíšte všetky možnosti pre prípad, že na kockách bude súčet 1+4+6 a súčet 1+5+5. Spustite si interaktívny program Tu.
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/159053/mod_book/chapter/4456/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
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: