Сочетанием из $\$inline\$n\$inline\$$ по $\$inline\$k\$inline\$$ называется выборка из $\$inline\$k\$inline\$$ элементов, взятая на множестве содержащем $\$inline\$n\$inline\$$ элементов. Один и тот же элемент нельзя выбирать несколько раз; порядок, в котором нам предъявляют решение об избранности того или иного элемента не учитывается. Число всех возможных сочетаний из $\$inline\$n\$inline\$$ по $\$inline\$k\$inline\$$ равно $\$inline\$С\_n^k\$inline\$$ — коэффициенту в биноме Ньютона. Факт известный каждому школьнику: о нём можно прочитать в википедии или любом учебнике, где вообще упомянаются сочетания и комбинаторика.

Однако почему эти два числа равны, нигде не объясняется. Возможно все считают этот факт очевидным и не требующим каких-то дополнительных пояснений.

На самом деле связь и вправду очень простая, если задуматься. Тем не менее, до какого-то момента связь между коэффициентами многочлена и комбинаторикой была для меня чем-то из области магии. Если для вас это и сейчас так, добро пожаловать под кат, буду объяснять очевидное.
Читать дальше →

https://habrahabr.ru/post/339784/