§ 9. Денумераторы размещений

Для получения энумератора размещений следовало бы построить некоммутативную алгебру производящих функций. Это возможно, но очень сложно и в конечном счете не дает

преимуществ по сравнению с методом § 3. Напротив, для получения денумераторов размещений пользоваться производящими функциями удобно.

Учитывая (8.5) и (3.25), можно записать

Таким образом, число упорядоченных -выборок без повторения (размещений без повторения из элементов по равно коэффициенту при в (9.1).

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

Приходим к результату, полученному ранее (см. (3.9)): число упорядоченных -выборок с повторением равно

Употребление денумераторов размещений, если накладывать условия на повторение элементов, — вещь более сложная и тонкая.

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

Пример. Приведем числовой пример для

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

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

Возьмем

Например, при

Итак, имеем

упорядоченных -выборок с повторением, образуемых тремя элементами, каждый из которых встречается не более двух раз.

Приведем еще один пример. Дано множество из элементов, подсчитаем число упорядоченных -выборок, в которых элемент встречается раз, встречается раз, встречается раз, причем некоторые элементы этого множества.

Коэффициент при равен а коэффициент при равен . Это число — не что иное, как число разбиений (см. (3.34)).

УПРАЖНЕНИЯ

(см. скан)