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

Формулы включения и исключения

Вывод формулы для числа элементов объединения множеств

Подстановки с запрещенными позициями - student2.ru .

Заметим, что внутренняя сумма для заданного Подстановки с запрещенными позициями - student2.ru содержит Подстановки с запрещенными позициями - student2.ru слагаемых.

В частности:

Подстановки с запрещенными позициями - student2.ru

Знак при внутренней сумме «минус» для четного Подстановки с запрещенными позициями - student2.ru и «плюс» для нечетного.

Первый вывод

Индукция по Подстановки с запрещенными позициями - student2.ru .

Базис (нетривиальный) при Подстановки с запрещенными позициями - student2.ru - см. выше.

Далее (с учетом индукционного предположения):

Подстановки с запрещенными позициями - student2.ru

Во втором и третьем слагаемых учтены все новые наборы из Подстановки с запрещенными позициями - student2.ru множеств ( Подстановки с запрещенными позициями - student2.ru ), содержащие множество Подстановки с запрещенными позициями - student2.ru . Поэтому вся написанная выше сумма будет равна

Подстановки с запрещенными позициями - student2.ru ,

что и требовалось.

Второй вывод

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

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

Но

Подстановки с запрещенными позициями - student2.ru , откуда Подстановки с запрещенными позициями - student2.ru , что и требовалось.

Формула для пересечения дополнений множеств

Подсчет числа элементов в объединении множеств позволяет находить число элементов, обладающих хотя одним из Подстановки с запрещенными позициями - student2.ru свойств. Следующая формула позволяет находить число элементов, не обладающих ни одним из Подстановки с запрещенными позициями - student2.ru свойств. Если обозначить через Подстановки с запрещенными позициями - student2.ru множество всех тех элементов, которые обладают свойством Подстановки с запрещенными позициями - student2.ru (при Подстановки с запрещенными позициями - student2.ru ), то множество всех тех элементов, которые не обладают ни одним из указанных свойств, есть пересечение дополнений Подстановки с запрещенными позициями - student2.ru .

Тогда

Подстановки с запрещенными позициями - student2.ru

(Здесь Подстановки с запрещенными позициями - student2.ru - универсальное множество, т.е. «высший род» в заданном классе элементов.)

Пример. 1) Найти, сколько чисел, не больших 100, взаимно просты с 30.

Найдем, сколь много чисел, не больших 100, которые имеют с 30 общий делитель, больший 1. Для этого достаточно определить, сколь много чисел в указанном диапазоне, которые кратны 2, 3 или 5. Множества чисел, кратных другим делителям 30, будут подмножествами указанных.

Пусть Подстановки с запрещенными позициями - student2.ru - множества чисел, кратных 2, 3 и 5 соответственно. Тогда

Подстановки с запрещенными позициями - student2.ru , что составит

50+33+20 – (16+10+6)+3 = 74, откуда искомое число будет равно 100-74=26, а без учета единицы составит 25.

2) Сколько чисел, не больших 1000, взаимно простых с 420?

Так как 420 = 22×3­­×5×7, то аналогично предыдущему имеем для искомого числа:

1000- ([1000/2]+[1000/3]+[1000/5]+[1000/7]) + ([1000/6]+[1000/10]+[1000/14]+[1000/15]+[1000/21]+[1000/35]) – ([1000/30]+[1000/42])+[1000/105])+[1000/70])+[1000/210]=1000-772=228.

Без учета единицы – 227.

Беспорядки

Беспорядком (или разупорядочиванием) на множестве Подстановки с запрещенными позициями - student2.ru называется подстановка множества Подстановки с запрещенными позициями - student2.ru , не имеющая неподвижных элементов.

Число беспорядков на Подстановки с запрещенными позициями - student2.ru -элементном множестве можно подсчитать следующим образом.

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

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

Подстановки с запрещенными позициями - student2.ru .

Множество беспорядков есть множество Подстановки с запрещенными позициями - student2.ru . Следовательно, число Подстановки с запрещенными позициями - student2.ru на Подстановки с запрещенными позициями - student2.ru -элементном множестве составит

Подстановки с запрещенными позициями - student2.ru

Вспомним теперь формулу Тейлора для функций Подстановки с запрещенными позициями - student2.ru и Подстановки с запрещенными позициями - student2.ru :

Подстановки с запрещенными позициями - student2.ru

Тогда при больших Подстановки с запрещенными позициями - student2.ru число Подстановки с запрещенными позициями - student2.ru .

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

Матрицы подстановок

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

Будем называть такие матрицы матрицами подстановок.

Доски

Матрицу подстановок Подстановки с запрещенными позициями - student2.ru -го порядка нам будет удобно изображать в виде таблицы Подстановки с запрещенными позициями - student2.ru клеток, а, в свою очередь, эту таблицу рассматривать как «шахматную» доску, полагая, что в клетке, соответствующей единичному элементу матрицы, стоит ладья. Таким образом, каждой матрице подстановок соответствует доска, на которой находится Подстановки с запрещенными позициями - student2.ru ладей, ни одна из которых не может бить другую. Будем говорить, что такие ладьи находятся в неатакующих позициях. Части доски Подстановки с запрещенными позициями - student2.ru также будем называть досками. Будем рассматривать также объединения и пересечения досок. Доски будем называть дизъюнктными, если они не имеют ни общих строк, ни общих столбцов.

Ладейный полином

Доске Подстановки с запрещенными позициями - student2.ru с Подстановки с запрещенными позициями - student2.ru клетками, которая является частью квадратной доски Подстановки с запрещенными позициями - student2.ru , сопоставляется полином

Подстановки с запрещенными позициями - student2.ru ,

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

Подстановки с запрещенными позициями - student2.ru

Для изображенных выше досок имеем:

Подстановки с запрещенными позициями - student2.ru

То, что коэффициент при нулевой степени Подстановки с запрещенными позициями - student2.ru означает, что существует 1 способ оставить доску пустой, т.е. разместить 0 ладей.

Теорема 1. Если доски Подстановки с запрещенными позициями - student2.ru и Подстановки с запрещенными позициями - student2.ru дизъюнктны, то Подстановки с запрещенными позициями - student2.ru .

Доказательство. Рассмотрим коэффициент Подстановки с запрещенными позициями - student2.ru . Если на доске Подстановки с запрещенными позициями - student2.ru размещено Подстановки с запрещенными позициями - student2.ru ладей[1], то можно выбрать Подстановки с запрещенными позициями - student2.ru ладей на доске Подстановки с запрещенными позициями - student2.ru и Подстановки с запрещенными позициями - student2.ru ладей на доске Подстановки с запрещенными позициями - student2.ru . Тем самым при заданном Подстановки с запрещенными позициями - student2.ru существует Подстановки с запрещенными позициями - student2.ru способов разместить Подстановки с запрещенными позициями - student2.ru ладей на объединенной доске (заметим, что если бы доски не были дизъюнктны, то это было бы неверно). Рассматривая все возможные значения Подстановки с запрещенными позициями - student2.ru от нуля до Подстановки с запрещенными позициями - student2.ru , получим

Подстановки с запрещенными позициями - student2.ru ,

что и является коэффициентом при Подстановки с запрещенными позициями - student2.ru в произведении Подстановки с запрещенными позициями - student2.ru .

Рассмотрим теперь более сложную комбинацию досок.

Теорема 2. Пусть Подстановки с запрещенными позициями - student2.ru - доска с Подстановки с запрещенными позициями - student2.ru клетками, а Подстановки с запрещенными позициями - student2.ru - клетка (квадрат) этой доски; пусть Подстановки с запрещенными позициями - student2.ru - доска, полученная из доски Подстановки с запрещенными позициями - student2.ru удалением клетки Подстановки с запрещенными позициями - student2.ru , и пусть Подстановки с запрещенными позициями - student2.ru , полученная из доски Подстановки с запрещенными позициями - student2.ru удалением строки и столбца, содержащих клетку Подстановки с запрещенными позициями - student2.ru .

Тогда Подстановки с запрещенными позициями - student2.ru .

Доказательство. Определим число способов, которыми можно разместить Подстановки с запрещенными позициями - student2.ru ладей на доске Подстановки с запрещенными позициями - student2.ru .

Возможны два случая: 1) в клетке Подстановки с запрещенными позициями - student2.ru есть ладья и 2) в клетке Подстановки с запрещенными позициями - student2.ru ладьи нет.

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

Теперь преобразуем ладейный полином для всей доски: Подстановки с запрещенными позициями - student2.ru

так как Подстановки с запрещенными позициями - student2.ru (на этой доске меньше Подстановки с запрещенными позициями - student2.ru клеток).

Для доски Подстановки с запрещенными позициями - student2.ru на рисунке выше, выбирая в качестве клетки Подстановки с запрещенными позициями - student2.ru среднюю, получим:

Подстановки с запрещенными позициями - student2.ru

Наши рекомендации