Схема сочетаний с повторениями (с. с. п.)

Обычно эта схема приводится в следующей наглядной интерпретации: производится случайное размещение r неразличимых шаров по n различимым ящикам. Если схематично изображать размещенные шары звездочками «», а перегородки ящиков палочками «|», то, очевидно, что все варианты размещений этих r шаров по этим n ящикам определяются взаимными расположениями элементов двух типов, неразличимых внутри типа, r «» и (n–1) «|» – внутренних перегородок между n ящиками, и могут быть вычислены по с. п. п., то есть их число по (1) есть:

.

В данной схеме решим следующую частную задачу: при найдем число N₁ размещений шаров по ящикам без пустых ящиков. Для нахождения N₁ представим получение требуемых размещений шаров так: во все ящики разложим по шару, а остальные (r–n) шаров раскидаем по n ящикам всеми способами. Тогда по (3) получим, что

.

Теперь, ограничившись приведенными комбинаторными схемами, подведем некоторые итоги.

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

Теперь большая часть приведенных здесь сведений из комбинаторики можно компактно представить в виде небольшой таблицы: