Каждый раз, когда начинаю рассказывать комбинаторику я рисую следующую табличку, которая постепенно заполняется:
И каждый раз доходя до неупорядоченных с возвращениями я говорю что-то из серии "попробуйте вывести сами, а если не получится спросите". Надо ли говорить, что спрашивают не часто?) Я оставлю этот пункт на разбор ученикам по ряду причин: во-первых этот тип выборок встречается крайне редко и поэтому мало полезен в олимпиадных задачах, во-вторых доказательство требует некоторого времени и я хочу дать в это время ещё и порешать ( благо комбинаторика в одно занятие обычно не впихивается, хотя и такие экстремальные ситуации встречаются).
Но так или иначе - мне будет удобно оставить здесь доказательство, чтобы каждый желающих смог изучить его в своё время. + я обещала :)
Доказательство. Как и в случае со всеми остальными выборками рассмотрим набор из N различных шаров. Доставая
Любая выборка определяется разбиением данного набора на \( (a_1, \dots, a_k) \) :
Получаем, что выборка зависит от расположения разделителей:
Сколько способов их расставить? Всего шариков N, а разделителей k-1 (чтобы разбить на k областей). Значит N+k-1 мест, из которых в k ставят разделители, причём делаем это неупорядоченно без возвращений ( если мы хотим, чтобы \( a_i \) =0, то ставим разделители рядом последовательно: | |). Таким образом количество неупорядоченных с возвращениями выборок $$C_{N+k-1}^k$$
Без возвращений
|
||
$$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$$
