Binomni koeficijent: Razlika između inačica

Oznake: mobilni uređaj m.wiki
Oznake: mobilni uređaj m.wiki
Neka je <math>S</math> skup svih takvih <math>k</math>-članih podskupova <math>n</math>-članog skupa. Vrijedi <math>|S| = \binom{n}{k}</math>.
 
Izaberimo neki element <math> x </math> iz <math> \{1, 2, ..., n \} </math>. Neka je <math> S_1 </math> skup podskupova iz <math>S</math> koji sadrže <math>x</math>. Njih ima <math>|S_1| = \binom{n - 1}{k - 1}</math> jer preostalih <math> n - 1 </math> brojeva iz <math> \{1, 2, ..., n \} </math> (ne možemo opet birati <math> x </math> jer je očito već sadržan u tim podskupovima) raspoređujemo na preostalih <math> k - 1 </math> mjesto. Neka je pak s druge strane <math> S_2 </math> skup podskupova iz <math> S </math> koji ne sadrže <math> x </math>. imaImamo ih <math>|S_2| = \binom{n - 1}{k} </math> jer sada raspoređujemo sve elemente iz <math> \{1, 2, ..., n\} </math> osim elementa <math> x </math>, njih <math> n - 1 </math>, na svih <math> k </math> mjesta jer na nijednom mjestu nije element <math> x. </math>
 
Očito je <math> |S_1| + |S_2| = |S| </math>, čime je tvrdnja dokazana.