Kombinácie bez opakovania

Pevný prvok - počet kombinácií

Tvrdenie.
Nech x je pevný prvok množiny \small  M_n a nech r \geq 1 . Počet r - kombinácií množiny \small  M_n , ktoré 
\ast prvok x obsahujú sa rovná \small  C(n-1,r-1)
\ast prvok x neobsahujú sa rovná   \small  C(n-1,r)
Dôkaz.
  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 \small  M_{n-1}= M_n - \lbrace{x}\rbrace
    • Ich počet je  rovný \small  C(n-1,r-1) .
  2. Ak nejaká ( r - \) kombinácia množiny \small  M_n neobsahuje prvok x , je vlastne r - kombináciou množiny \small  M_{n-1}
    • Ich počet týchto je \small  C(n-1,r) .
                                  
Dôsledok.
Ak 1 \leq r \leq n , tak platí    \small  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í:
\small  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 \small  C(n,r) .

\( .\)