Выборки неупорядоченные с возвращениями.

Каждый раз, когда начинаю рассказывать комбинаторику я рисую следующую табличку, которая постепенно заполняется:

	С возвращениями	Без возвращений
Упорядоченные	$$N^k$$	$$\frac{N!}{(N-k)!}$$
Неупорядоченные		$$C_N^k$$

И каждый раз доходя до неупорядоченных с возвращениями я говорю что-то из серии "попробуйте вывести сами, а если не получится спросите". Надо ли говорить, что спрашивают не часто?) Я оставлю этот пункт на разбор ученикам по ряду причин: во-первых этот тип выборок встречается крайне редко и поэтому мало полезен в олимпиадных задачах, во-вторых  доказательство требует некоторого времени и я хочу дать в это время ещё и порешать ( благо комбинаторика в одно занятие обычно не впихивается, хотя и такие экстремальные ситуации встречаются).

Но так или иначе  - мне будет удобно оставить здесь доказательство, чтобы каждый желающих смог изучить его в своё время. + я обещала :)

Теорема. Пусть всего дано N элементов, из них выбирается k неупорядоченно с возвращениями. Тогда таких выборок $$C_{N+k-1}^k$$

Доказательство. Как и в случае со всеми остальными выборками рассмотрим набор из N различных шаров. Доставая

их мы можем получить один и тот же шар несколько раз. Обозначим количество выниманий одного и того же $i$-ого шара за $a_i$. Тогда $$a_1+a_2+\dots + a_k=N$$

Выборки различаются тогда, когда различаются упорядоченные наборы $(a_1, \dots, a_k)$ и выполняется условие суммы приведённое выше. Поэтому применить формулу $N^k$ не выйдет. Рассмотрим такую модель:

Любая выборка определяется разбиением данного набора на $(a_1, \dots, a_k)$ :

 Получаем, что выборка зависит от расположения разделителей:

Сколько способов их расставить? Всего шариков N, а разделителей k-1 (чтобы разбить на k областей). Значит N+k-1 мест, из которых в k ставят разделители, причём делаем это неупорядоченно без возвращений ( если мы хотим, чтобы $a_i$ =0, то ставим разделители рядом последовательно: | |). Таким образом количество неупорядоченных с возвращениями выборок $$C_{N+k-1}^k$$