Распределение объектов по ячейкам

Даны объектов (предметов) и ячеек (ящиков). Требуется определить количество способов, которыми объекты могут быть распределены по ячейкам. При этом в зависимости от условия задачи необходимо учитывать следующие варианты:

- объекты могут быть одинаковыми или различными;

- ячейки могут быть одинаковыми или различными;

- возможно ограничение на количество объектов в ячейках;

- возможен учёт порядка объектов в ячейках или порядка ячеек.

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

0 0 0 …0 – объекты (m штук);

/ – перегородка, отделяющая одну ячейку от другой (всего перегородок k-1 штук).

Приведём несколько примеров распределения объектов по ячейкам с учётом введённых обозначений:

- все объекты попали в последнюю ячейку;

- три объекта в первой ячейке, все остальные в последней.

Перейдём к обзору методов решения основных задач распределения объектов по ячейкам.

Распределение одинаковых объектов

Во всех следующих задачах (кроме пункта 5.4) предполагается, что ячейки различны и различают их по номерам: .

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

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