Kombinatorika
Kombinácie bez opakovania
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)