Сочетанием из 
по 
называется выборка из 
элементов, взятая на множестве содержащем 
элементов. Один и тот же элемент нельзя выбирать несколько раз; порядок, в котором нам предъявляют решение об избранности того или иного элемента не учитывается. Число всех возможных сочетаний из 
по 
равно 
— коэффициенту в биноме Ньютона. Факт известный каждому школьнику: о нём можно прочитать в википедии или любом учебнике, где вообще упомянаются сочетания и комбинаторика.
Однако почему эти два числа равны, нигде не объясняется. Возможно все считают этот факт очевидным и не требующим каких-то дополнительных пояснений.
На самом деле связь и вправду очень простая, если задуматься. Тем не менее, до какого-то момента связь между коэффициентами многочлена и комбинаторикой была для меня чем-то из области магии. Если для вас это и сейчас так, добро пожаловать под кат, буду объяснять очевидное.
Читать полностью »