Число подстановок с запрещенными позициями

      Комментарии к записи Число подстановок с запрещенными позициями отключены

Рассмотрим снова группу подстановок Число подстановок с запрещенными позициями множества Число подстановок с запрещенными позициями . Пусть для каждого Число подстановок с запрещенными позициями определено множество Число подстановок с запрещенными позициями запрещенных значений, т.е. из группы Число подстановок с запрещенными позициями исключаются все такие подстановки Число подстановок с запрещенными позициями , для которых Число подстановок с запрещенными позициями . Упорядоченная пара Число подстановок с запрещенными позициями при Число подстановок с запрещенными позициями называется запрещенной парой. Множество Число подстановок с запрещенными позициями

называется запрещенной областью.

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

Заметим, что для беспорядков запрещенной областью является главная диагональ.

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

Тогда число всех подстановок, значения которых не являются запрещенными, равно

Число подстановок с запрещенными позициями

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

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

Число подстановок с запрещенными позициями .

Рассуждая аналогично, можно показать, что

Число подстановок с запрещенными позициями .

Итак, число допустимых подстановок составит

Число подстановок с запрещенными позициями ,

т.е. из числа всех подстановок надо вычесть значение ладейного полинома запрещенной области (без единицы) при подстановке вместо Число подстановок с запрещенными позициями -ой степени переменной числа Число подстановок с запрещенными позициями .

Формула может быть, очевидно, переписана и в таком виде:

Число подстановок с запрещенными позициями

В частности, для беспорядков Число подстановок с запрещенными позициями — число способов размещения Число подстановок с запрещенными позициями ладей на главной диагонали.

Число сюръекций

Формулы включения-исключения можно применить для подсчета числа сюръективных отображений одного конечного множества на другое.

Пусть Число подстановок с запрещенными позициями ; пусть Число подстановок с запрещенными позициями — множество всех таких отображений Число подстановок с запрещенными позициями в Число подстановок с запрещенными позициями , в область значений которых не попадает элемент Число подстановок с запрещенными позициями . Тогда для фиксированных Число подстановок с запрещенными позициями имеем Число подстановок с запрещенными позициями , а

Число подстановок с запрещенными позициями .

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

Число подстановок с запрещенными позициями

(число всех отображений, не являющихся сюръекциями).

Тогда число Число подстановок с запрещенными позициями всех сюръекций Число подстановок с запрещенными позициями на Число подстановок с запрещенными позициями составит

Число подстановок с запрещенными позициями .

Число Число подстановок с запрещенными позициями может быть получено и по другой формуле:

Число подстановок с запрещенными позициями ,

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

Например, Число подстановок с запрещенными позициями по первой формуле, тогда как по второй Число подстановок с запрещенными позициями .

Аналогично Число подстановок с запрещенными позициями .

На основании полученных результатов можно вывести формулу для числа всех возможных разбиений Число подстановок с запрещенными позициями -элементного множества на Число подстановок с запрещенными позициями подмножеств. Оно будет, как нетрудно показать, равно Число подстановок с запрещенными позициями [Сачков, с. 44][2]. При этом число разбиений при фиксированных ненулевых числах Число подстановок с запрещенными позициями будет равно Число подстановок с запрещенными позициями , т.е. суммирование ведется по всем различным векторам, компоненты которых суть числа Число подстановок с запрещенными позициями . Например, при Число подстановок с запрещенными позициями получим Число подстановок с запрещенными позициями , т.е. существует 6 способов разбить 4-элементное множество на 2 одноэлементных и одно двухэлементное. Вот эти разбиения:

1-{1}, {2}, {3,4}, 2-{1}, {3}, {2,4},3-{1}, {4}, {2,3}, 4-{2}, {3}, {1,4}, 5-{2}, {4}, {1,3}, 6-{3}, {4}, {1,2}.

Если в выше написанной формуле для числа сюръекций допустить, что некоторые из чисел Число подстановок с запрещенными позициями могут быть равны нулю, то получим формулу для числа всех отображений m-элементного множества в n-элементное.

По индукции может быть доказана такая формула:

Число подстановок с запрещенными позициями

([Сачков, с. 39]).

Тогда при Число подстановок с запрещенными позициями получаем Число подстановок с запрещенными позициями , что и равно числу всех отображений m-элементного множества в n-элементное.

[1] Везде в дальнейшем, говоря о размещении ладей, мы, естественно, имеем в виду размещение в неатакующих позициях.

[2] Числа называются числами Стирлинга 2-го рода. [Андерсон, с. 553.]

Дополнительные материалы:

GetAClass — Комбинаторика 2. Число перестановок


Похожие статьи: