Значит, теорема утверждает, что C из n по k с чертой,
можно вычислить как C из n + k − 1 по k.
То есть сочетания с повторениями, их,
конечно, больше, чем сочетаний, просто, без повторений, но вот на столько.
Можно посчитать обычную C.
Давайте между множеством всех сочетаний, с повторениями, k-сочетаний с повторениями.
и некоторым множеством последовательности из нулей и единиц, установим биекцию.
Иными словами, сейчас мы каждому k-сочетанию
с повторением сопоставим некоторую последовательность из нулей и единиц,
и вот это сопоставление будет биективным.
Так, ну смотрите, вот у нас есть
объекты наши: a1, ..., an.
Давайте рассмотрим произвольное k-сочетание
с повторениями.
Это кучка объектов, которые еще и могут повторяться, к тому же.
Ну, сейчас я буду говорить в абстрактных терминах,
потому что я верю, что вы все люди очень умные и воспримите меня сразу так.
Но, если вы мне скажете, что это невнятно,
я вот здесь вот нарисую еще пример, и тогда будет понятно совсем.
Хорошо?
Так.
Давайте сделаем следующее – посчитаем,
сколько раз вот в
этом фиксированном нами
k-сочетании, в этом k-сочетании,
сколько раз в этом k-сочетании встречается объект a1.
Встречается a1.
Ну теоретически, сколько раз он может встречаться?
От 0 до k, правильно.
От 0 до k.
Может вообще не встречаться.
Что ж нас заставляет использовать a1 для построения k-сочетаний?
Может всяко раз встречаться, такое тоже возможно.
Но вот посчитали, сколько раз он встречается, и вот сколько
получилось, столько единиц рисуем.
Рисуем столько единиц,
сколько раз объект a1 встречается вот в этом нашем конкретном k-сочетании.
Мы его зафиксировали, k -сочетание, посчитали, сколько раз a1 встречается,
и нарисовали столько единиц.
Я думаю, что вы хотите меня очень спросить: «А что делать,
если он встречается 0 раз, да?» Ну, ничего не рисуем.
Нарисовать 0 единиц – это ничего не нарисовать, так тоже бывает.
Понятно, да?
Теперь, без относительно того, нарисовали мы сколько-то единиц,
или нарисовали мы 0 единиц, мы рисуем 0, 0 служит перегородкой.
Ноль вот этот служит перегородкой.
Вот, сколько бы единиц мы ни нарисовали, даже если мы ни одну не рисуем,
всё равно нолик ставим.
Успеваете?
А дальше делаем то же самое, но только уже не относительно встречаемости элемента a1,
а относительно встречаемости элемента a2.
То есть, опять, рисуем столько единиц, сколько раз у нас встречается элемент a2.
Сейчас я договорю до конца, а потом, видимо,
всё-таки приведу пример, иначе будет тяжело.
Значит, рисую столько единиц, сколько раз встречается элемент a2.
Ну опять, если ни разу не встречается, ни одно и не рисую, но,
в любом случае добавляю здесь 0.
То есть теоретически может получиться просто два нуля.
Ну как угодно.
И так далее.
Вот появился очередной 0, как разделитель такой, и я,
наконец, дошел до a с индексом n.
Я, опять же, считаю, сколько раз a с индексом n встречается в моем конкретном
k-сочетании, и столько единиц здесь рисую.
Вот это уже количество единиц,
которое равно числу встреч с вот этим элементом an в нашем k-сочетании.
Успеваете?
Так, смотрите, никакого 0 в начале, никакого 0 в конце.
Давайте поймем, сколько у нас нулей в такой последовательности.
Сколько?
n − 1, правильно.
Нулей получится n − 1 штука, потому что мы смотрим на встречаемость a1,
потом ставим 0, смотрим на встречаемость a2, потом ставим 0.
И так доходим до a с индексом n − 1, после него ставим 0, вот этот самый.
Потом рисуем столько единиц, сколько раз встречалось an -ное,
а больше нулей не ставим.
То есть нулей – n − 1 штука.
Так, а единиц сколько?
Ну, разумеется, k.
Разумеется, Разумеется, единиц в сумме будет k-штук,
потому что просто это количество элементов в нашем k-сочетании, по совокупности.
Верно?
То есть, смотрите, у нас получилась такая последовательность,
состоящая из n − 1 + k,
или, что, то же самое n + k − 1,
от перестановки мест слагаемых, вы понимаете, сумма не меняется.
У нас получилась последовательность, состоящая из n + k − 1, нулей и единиц,
в которой ровно k-единиц.
Ровно k-единиц.
[ПАУЗА] Я утверждаю,
что если, наоборот, взять произвольную такую последовательность, неважно,
где единицы стоят, по ней можно однозначно восстановить то k-сочетание,
из которого она получена.
Вот это очевидно?
Я утверждаю, что мы получили с помощью этой конструкции биекцию между
множеством всех k-сочетаний с повторением и множеством всех ноль один
последовательностей, в которых ровно k-единиц.
Вывод: количество k-сочетаний, ну,
то есть вот это вот C из n по k с чертой,
равно числу таких
последовательностей из нулей и единиц.
[ПАУЗА] Ну,
оно-то совершенно очевидно считается.
Ну опять, у нас есть n + k −
1 позиция и у нас есть k-единиц,
то есть нам нужно из
множества вот такой вот мощности выбрать произвольное подмножество
мощности k и на позиции с номерами из этого подмножества поставить единицы.
Очевидно, что это делается в аккурат C из n + k − 1 по k-способами.
Ну, просто из n + k − 1 выбрать k-позиции,
это обычное число сочетаний, и таким образом теорема наша доказана.
Правда?
Биекцию установили,
последовательности посчитали, и всё отлично получилось.