3.2. Размещения без повторений

Введем ограничения на постановку задачи о размещениях. Пусть на декартовом произведении n‑Х и r‑S множеств построены все функции F: r‑S→ n‑X. Сколько из них инъективных? В качестве примера рассмотрим случай, когда r = n = 3.

Все функции, соответствующие этому случаю, представлены на рисунке 3.3:

1, 1, 1 1, 1, 2 1, 1 , 3

1, 2, 1  1, 2, 2  1, 2, 3

1, 3, 1 1, 3, 2 1, 3, 3

2, 1, 1  2, 1, 2 2, 1, 3

 2, 2, 1 2, 2, 2  2, 2, 3

2, 3, 1  2, 3, 2 2, 3, 3

3, 1, 1 3, 1, 2  3, 1, 3

3, 2, 1 3, 2, 2 3, 2, 3

3, 3, 1 3, 3, 2  3, 3, 3

Рисунок 3.3

В данном примере из всех полученных функций имеем 6 инъективных . Все они на рисунке 3.3 выделены.

Размещения, соответствующие инъективным функциям называются размещениями без повторений либо инъективными размещениями.

Ясно, что инъективные функции составляют всего лишь подмножество всех функций F : r‑S → n‑X. Поэтому для их получения достаточно наложить ограничения на алгоритмы (3.5) или (3.6). Рассмотрим этот вопрос на примере решения задачи выбора без повторений r объектов на множестве n‑X.

Данная задача имеет следующую интерпретацию.

В урне имеется n пронумерованных шаров. После­довательно один за другим извлекаются r шаров и их номера фиксируются. Сколько и каких различных r‑ок шаров может быть выбрано?

Проведем соответствующие комбинаторные рас­суждения.

Выбор значения первого элемента у₁ можно осуществить n способами. Выбор второго элемента у₂ можно осу­ще­ствить только n–1 способами с каждым из первых, за­претив применять уже выбранное значение. Индуктивно пред­по­ла­гая, что таким образом выбраны уже r – 1 элемент, по­лучим, что r‑тый элемент можно выбрать n(n -1…(n - (r -1)) спо­собами с каждым из предыдущих, поскольку для него за­пре­щен выбор любого из уже выбранных предыдущих зна­чений. Поэтому всего будет получено n(n-1…(n-(r-1)) раз­ли­чных элементов комбинаторной конфигурации.

Для определения числа инъективных размещений при­няты обозначения: A_n^r или [n]_r.

В соответствии с проведенными выше рассуждениями имеем

A_n^r = n(n - 1)… (n - (r - 1)). (3.7)

Выражение (3.7) представляет полином по переменнойn степени r.

Коэффициенты s(r, k) этого полинома известны в комбинаторике как числа Стирлинга первого рода. Они вычисляются следующим образом. Представив (3.7) в виде полинома в развернутой записи, видим, что s(r, 0) = 1, а s(r, r-1) = = r-1! для любого r  n. Остальные числа s(r, k) подчиняются рекурсии:

s(r +1, k) = s(r, k) - r s(r, k - 1).

Последняя формула легко выводится из (3.7) по индукции.

Алгоритм инъективных размещений получим, если введем рассмотренные выше ограничения в алгоритме (3.6). С учетом ранее введенных обозначений, будем иметь:

Рассмотренная нами задача именуется: выбор без воз­вращений.

Соответствующая задача расположения имеет следу­ющую формулировку.

Требуется расположить r пронумерованных шаров по n пронумерованным урнам так, чтобы ни в какую урну не попадало два шара одновременно. Сколько и каких расположений возможно?

Ясно, что эта задача также решается применением ал­горитма (3.8), соответственно в обозначениях, принятых для алгоритма (3.5).

На основании изложенного выше, имеем доказа­тель­ство следующей теоремы.

Теорема 3.2 Размещения r различных объектов n различными способами без повторений эквивалентны всем инъективным функциям, определенным на множестве r‑S со значениями в множестве n‑X, число которых равно

A_n^r = n(n - 1)… (n - (r - 1)).