§ 18. Классифицирование. Схема размещения элементов по ячейкам

Под классифицированием понимают распределение объектов из некоторой совокупности по классам, причем каждый объект принадлежит точно одному классу (некоторые классы могут быть пустыми). Объекты из одного и того же класса не обязательно считаются эквивалентными, т. е. рассматриваемое здесь понятие класса шире понятия класса эквивалентности в теории множеств.

Физическая интерпретация классифицирования — это «схема размещения» или «размещение» объектов по ячейкам; каждая ячейка соответствует классу.

Во избежание недоразумений, мы вместо классов будем говорить о ячейках

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

(1.1): объекты различимые и неупорядоченные, ячейки различимые и неупорядоченные;

(1.2): объекты различимые и неупорядоченные, ячейки различимые и упорядоченные;

(1.3): объекты различимые и неупорядоченные, ячейки неразличимые;

(2.1): объекты различимые и упорядоченные, ячейки различимые и неупорядоченные;

(2.2): объекты различимые и упорядоченные, ячейки различимые и упорядоченные;

(2.3): объекты различимые и упорядоченные, ячейки неразличимые;

(3.1): объекты неразличимые, ячейки различимые и неупорядоченные;

(3.2): объекты неразличимые, ячейки различимые и упорядоченные;

(3.3): объекты неразличимые, ячейки неразличимые.

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

Случай (1.3) не следует смешивать со случаем (1.1). Подмножество ячеек в (1.1) может быть образовано, например, ячейками 1, 2, 4, 5. В случае (1.3) понятие подмножества не имеет смысла.

В случае (1.1) размещение описывается так: ячейка 1 содержит ячейка 2 пуста, ячейка 3 содержит ячейка 4 содержит ячейка 5 содержит В.

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

О случаях (2.3) и (2.1) следует сделать те же замечания, что и о случае (1.3).

Установим теперь формулы, дающие числа различных размещений объектов по ячейкам для некоторых случаев, указанных выше.

Число размещений r различимых и неупорядоченных объектов по n различимым и неупорядоченным ячейкам. Случай (1.1). Это число равно

В самом деле, пусть объектов перенумерованы от 1 до Объект с номером 1 можно поместить в ячеек в точности способами, объекты с номерами 1 и 2 — в точности способами, объектов — в точности способами.

Найдем теперь денумератор таких размещений, что некоторое число объектов попадает в заданную ячейку, а затем — то же для фиксированного множества ячеек.

Пусть денумератор, дающий число объектов, которые могут быть помещены в ячейки с номерами причем соответствует ячейке Очевидно,

ибо один объект можно поместить в каждую из ячеек. Для двух объектов

для объектов

Применим экспоненциальное преобразование:

Для ячейки имеем

С другой стороны, можем записать (см. (7.102))

где суммирование производится по всем целым неотрицательным числам таким, что

Отсюда следует, что число таких размещений различимых и неупорядоченных объектов по различимым и неупорядоченным ячейкам, что объектов попадает в ячейку объектов — в ячейку объектов — в ячейку равно

Это число получено в (3.34).

следует

Применим (18.5) к более сложным случаям.

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

и

Полагая в имеем

Если соответствующий денумератор, то

Сравнение (18.13) и (18.14) дает

таким образом, искомое число равно

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

откуда

Полагая получаем

Сравнивая (18.19) с имеем

Таким образом, искомое число равно

Если теперь эти объектов размещаются по различимым ячейкам с тем условием, что ячеек заняты, ячеек пусты, то

Припишем занятым ячейкам номера от 1 до (не уточняя, какие именно ячейки заняты). Имеем

Таким образом, искомое число равно

что обобщает (18.21).

Рассмотрим еще некоторые случаи.

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

Запишем

Отсюда следует рекуррентное соотношение для соответствующих чисел

и

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

Отсюда следует рекуррентное соотношение для

Число размещений r неразличимых объектов по n различимым и неупорядоченным ячейкам. Случай (3.1). Это число равно

В самом деле, расположим на одной строке объектов и между ними поставим черточек, соответствующих ячейкам (рис. 33). Мы можем теперь рассматривать черточки как объекты. Число размещений неразличимых объектов по ячейкам равно поэтому числу перестановок объектов, т. е. числу упорядоченных -выборок без повторения. Так как мест (черточек) фиксированы, а остальные объектов неразличимы, то

Рис. 33.

Найдем денумератор, соответствующий размещению объектов в ячейке Воспользуемся (18.6), учитывая, что коэффициенты при нужно умножить на (объекты одинаковы); имеем

Если рассматривать ячеек, то

Полагаем

где

а также

где

Можно дать общую формулу для а и 0 с помощью формулы Бруно. Как показано ранее (см. (10.51) и (17.15)), из

следует

где суммирование производится по всем решениям уравнения

Запишем также

Сравнивая (18.37) с (18.39), получаем

где суммирование производится по всем решениям уравнения

Точно так же

и, сравнивая это с (18.37), получаем

Как пример выпишем формулы (18.40) и (18.42) при При

При

При

Наконец, обозначая через денумератор, соответствующий размещениям неразличимых объектов по различимым (указанным) ячейкам, имеем

Ввиду (18.43) — (18.46) получаем

Денумератор, соответствующий всем возможным случаям, получается из (18.32) при

откуда

т. e. опять приходим к (18.30).

Найдем теперь денумератор, соответствующий размещениям неразличимых объектов по различимым и неупорядоченным ячейкам при условии, что все ячейки заняты.

Для фиксированной ячейки находим аналогично (18.31)

Для всех ячеек

Когда ячейки конкретно не указываются, имеем

Разлагая запишем

откуда

таким образом, искомое число равно

Наконец, выпишем денумератор, соответствующий размещениям неразличимых объектов по различимым ячейкам при том условии, что в каждую ячейку попадает не более одного объекта.

Для фиксированной ячейки

для ячеек

Для всех возможных случаев

откуда

следовательно,

Число размещений r различимых и упорядоченных объектов по n различимым и упорядоченным ячейкам. Случай (2.2).

Это число равно

Докажем это. Размещаем неразличимых объектов по различимым и неупорядоченным ячейкам. Затем, рассматривая объекты в каждой ячейке как различимые, переставим их способами. Тем самым все возможные случаи рассмотрены и искомое число равно числу из (18.30), умноженному на

Если при этом потребовать, чтобы все ячейки были заняты, то точно так же из (18.56) получаем

Число размещений r различимых и неупорядоченных объектов по n неразличимым ячейкам. Случай (1.3). Это число равно

где

и через обозначены числа Стирлинга второго рода, определяемые формулой (10.5). Числа называют иногда кумулятивными числами Стирлинга второго рода.

Докажем (18.64). Рассмотрим сначала случай, когда каждая ячейка занята. Число таких размещений равно числу, полученному в (18.21), деленному на т. е. Так как каждую пустую ячейку можно выбирать только одним способом, то, суммируя от 1 до получаем искомое число.

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

За недостатком места и чтобы сохранить элементарность изложения, мы ограничимся рассмотренными выше случаями. Более полные сведения можно получить из [36].

УПРАЖНЕНИЯ

(см. скан)

(см. скан)