Predchádzajúci
Nasledujúci

Kombinácie bez opakovania

Pevný prvok - počet kombinácií


Tvrdenie. Nech x je pevný prvok množiny M_n a nech r \geq 1 . Počet r - kombinácií množiny M_n , ktoré
\ast prvok x obsahujú sa rovná C(n-1,r-1)
\ast prvok x neobsahujú sa rovná    C(n-1,r)
Dôkaz tvrdenia:
    1. Odstráňme prvok x zo všetkých r - kombinácií (ktoré ho obsahujú)
      • Dostaneme práve všetky (r-1) - kombinácie množiny M_{n-1}= M_n - \lbrace{x}\rbrace
      • Ich počet je  rovný C(n-1,r-1) .
    2. Ak nejaká ( r - \) kombinácia množiny M_n neobsahuje prvok x , je vlastne r - kombináciou množiny M_{n-1}
      • Ich počet týchto je C(n-1,r) .
                                  

Dôsledok: Ak 1 \leq r \leq n , tak platí     C(n,r )=C(n-1,r-1 )+C(n-1,r ) .
Poznámka.
Rovnosť uvedená v dôsledku je vlastne rekurentným vzťahom. Počet r -kombinácií n -prvkovej množiny je vyjadrený pomocou počtu kombinácií (n-1) -prvkovej množiny. Stačí začať s 1-prvkovou množinou, pre ktorú platí:
C(1,0 )+C(1,1 )= 1+1=2\stackrel{dosledok}{=}C(2,1)
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) .
\( .\)
Predchádzajúci
Nasledujúci