Упорядоченное размещение

Разместим п объектов по m ящикам так, чтобы каждый ящик содержал бы последовательность, а не множество, как прежде, помещенных в нем объектов. Два размещения назовем равными, если в каждом ящике содержится одна и та же последовательность объектов. Размещения такого типа называются упорядоченными размещениями п объектов по m ящикам. Обозначим число таких упорядочений через A^т_п.

Теорема 1.4. Число упорядоченных размещений n объектов по т ящикам равно

A^т_п = т (т+1)... (т+ n-1)

(полагаем A⁰ _п = 1).

Доказательство. Будем строить упорядоченное размещение, джобавляя по очереди новые объекты. Первый объект мы можем построить т способами, второй – т+1 способами, ибо его можно разместить в одном из m – 1 пустых ящиков или в ящике, содержащим первый объект, перед ним или после него. В общем случае предположим, что уже размещено i – 1 объектов, причем для k = 1, 2,..., т в k -м ящике находится r_k объектов. Тогда i -й объект можем добавить в k -й ящик r_k + 1 способами, что дает в сумме

(r_k+1) +... + (r_m +1) = (r₁ +... + r_m) + m = m + i -1

возможностей. Таким образом, всех упорядоченных размещений будет т (т+1)... (т+ n-1).

Пример.

Изобразить упорядоченные размещения двух элементов a,b по трем ящикам.

В этом случае |3|² = 12 = 3 4

Теорема 1.2. Если |X| = n, |Y| = m то числе всех взаимно однозначных функций f: X —> Y равно

|т|_п = m (m - 1)…(m - n + 1) (полагаем |т|₀ = 1)

Доказательство. Будем определять на этот раз число инъективных (т. е. имеющих все различные члены) последовательностей < y₁..., y_n > с членами из множества Y. Элемент y₁ такого множества мы можем выбрать т способами, элемент y₂ — (m - 1) способами, в общем случае если уже выбраны элементы y₁,..., y_i-1, то в качестве y_i можем выбрать любой из т–i+1 элементов множества Y\{(y₁,,.., y_i-1} (принимаем п ≤ т; если п > т, то очевидно, что и |т|_п и искомое число функций равны нулю). (Это дает т (т - 1)... (т - п + 1) возможностей выбора инъективных последовательностей < y₁..., y_n >.)

Пример.

Дано множество Х из 4-х элементов Х = {1, 2, 3, 4}. Записать последовательности из 3 элементов.

Решение.

Число последовательностей длиной 3 с элементами из множества Х будет равно [4]₃ = 4 3 2 = 24.

Замечание. Перестановка является частным случаем размещения при n=k.