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

Habrahabr

Сочетанием из

$n$

по

$k$

называется выборка из

$k$

элементов, взятая на множестве содержащем

$n$

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

$n$

по

$k$

равно

$С_n^k$

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

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

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

$(a + b)$

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

$(a + b)^4 = (a + b)(a + b)(a + b)(a + b).$

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

$ (a + b)^4 = $

$ (a + b)(a + b)(a + b)(a + b) = $

$ ((a + b)(a + b))((a + b)(a + b)) = $

$ (aa + ab + ba + bb)(aa + ab + ba + bb) = $

$ aa(aa + ab + ba + bb) + ab(aa + ab + ba + bb) + $

$ ba(aa + ab + ba + bb) + bb(aa + ab + ba + bb) = $

$ aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb + $

$ baaa + baab + baba + babb + bbaa + bbab + bbba + bbbb. $

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

$2 \times 2 \times 2 \times 2 = 2^4 = 16$

.

Будем считать, что если в строке элемент равен

$a$

, то он не «выбран», а если

$b$

, то «выбран». В таком случае строка

$aaaa$

соответствует случаю, когда из 4-х элементов не выбрали ни одного, а строка

$bbbb$

— случаю когда все элементы выбраны.

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

$b$

:

$aabb, abab, abba, baab, baba, bbaa$

. Их ровно шесть.

Теперь вспомним о коммутативности умножения и о нотации «степень». Все эти строки можно записать как

$a^2b^2$

, и в исходной сумме мы получим:

$aabb + abab + abba + baab + baba + bbaa = $

$ a^2b^2 + a^2b^2 + a^2b^2 + a^2b^2 + a^2b^2 + a^2b^2 = $

$ 6a^2b^2.$

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

$a$

и

$b$

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

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

$a^0 = b^0 = 1$

.

$(a + b)^4 = 1a^4b^0 + 4a^3b^1 + 6a^2b^2 + 4a^1b^3 + 1a^0b^4. $

В такой записи чтобы узнать количество способов выбора

$k$

элементов из

$4$

достаточно просто посмотреть на коэффициент перед слагаемым в котором

$b$

входит в

$k$

-ой степени.

Кстати, обратите внимание, что

$1 + 4 + 6 + 4 + 1 = 16 = 2^4$

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

$2^4$

слагаемых.

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

$(a + b)^n = C_n^0a^nb^0 + C_n^1a^{n-1}b^1 + ... + C_n^na^0b^n$

$\sum_{k=0}^{n}{C_n^k} = 2^n.$

Нотация очень простая: у

$C$

снизу стоит

$n$

— степень скобки, сверху

$k$

— степень, в которой в слагаемом стоит

$b$

.

Или, как мы теперь знаем,

$n$

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

$k$

— количество элементов, которые мы выбираем.

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

$a$

и

$b$

, а через произведение

$(1 + х)^n$

и в многочление, который получается в итоге, есть только

$х$

(т.к. при

$a = 1$

любая степень

$a$

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