Сочетания

Доказательство. Множество размещений из n по k разобьем на группы по следующему принципу: к одной группе отнесем те и только те размещения, которые отличаются порядком, но не отличаются составом. То есть размещения, попавшие в одну группу, можно считать перестановками на множестве из k элементов, откуда следует, что таких размещений k! штук. С другой стороны, так как размещения из одной группы не отличаются составом, то они задают одно и то же сочетание, то есть число всех сочетаний равно числу групп. Итак, всего размещений , они разбиты на группы по k! в каждой, то есть на групп, причем число групп равно числу сочетаний. Используя теперь доказанную выше формулу для числа размещений, получим формулу для числа сочетаний.