Связь между числом сочетаний и биномиальными коэффициентами

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

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

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

Давайте начнём с конкретного примера. Возьмём сумму и возведём её в какую-то степень, например в четвёртую.

Раскроем скобки справа, при этом не будем приводить подобные слагаемые, использовать при записи степени, а так же забудем на минуту о коммутативности умножения, т.е. не будем менять порядок множителей в слагаемых:

Давайте думать о слагаемых в итоговом многочлене как о символьных строках. Мы получили 16 строк длиной 4 символа. Понять, почему именно 16 несложно. Каждый раз, когда мы умножаем на скобку, содержащую 2 слагаемых, мы увеличиваем число элементов в конечном результате в два раза. Всего мы перемножили 4 скобки с двумя слагаемыми, т.е. в итоге получили .

Будем считать, что если в строке элемент равен , то он не «выбран», а если , то «выбран». В таком случае строка соответствует случаю, когда из 4-х элементов не выбрали ни одного, а строка — случаю когда все элементы выбраны.

Предположим теперь, что мы хотим ответить на вопрос «сколькими способами можно выбрать два элемента из четырёх». С учётом нашей договорённости, всё что нам надо сделать — это посчитать количество строк, в которых ровно две буквы : . Их ровно шесть.

Теперь вспомним о коммутативности умножения и о нотации «степень». Все эти строки можно записать как , и в исходной сумме мы получим:

Коэффициент 6 и есть ответ на наш вопрос про количество способов выбора двух элементов. Не удивительно, ведь когда мы приводим подобные слагаемые, то подсчитываем количество множителей, в которых и входят в одинаковой степени. То есть подсчитываем число строк, в которых «выбрано» одно и то же число элементов.

Вернёмся к начальной сумме и приведём все слагаемые. Для наглядности я в явном виде буду записывать коэффициент 1 и буду использовать тот факт, что .

В такой записи чтобы узнать количество способов выбора элементов из достаточно просто посмотреть на коэффициент перед слагаемым в котором входит в -ой степени.

Кстати, обратите внимание, что . Это еще одно свойство биномальных коэффициентов, которое становится очевидным, если вспомнить, что мы начинали с многочлена в котором слагаемых.

Для общего случая

Нотация очень простая: у снизу стоит — степень скобки, сверху — степень, в которой в слагаемом стоит .

Или, как мы теперь знаем, это количество элементов в множестве, из которого мы делаем выборку, — количество элементов, которые мы выбираем.

Добавлю, что обычно определение биномального коэффициента даётся не через произведение и , а через произведение и в многочление, который получается в итоге, есть только (т.к. при любая степень равна еденице). Суть от этого не меняется, но заметить комбинаторную сущность получившийся формулы становится сложнее.