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

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

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

Заметим, что внутренняя сумма для заданного содержит слагаемых.

В частности:

Знак при внутренней сумме «минус» для четного и «плюс» для нечетного.

Первый вывод

Индукция по .

Базис (нетривиальный) при - см. выше.

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

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

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

Второй вывод

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

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

Но

, откуда , что и требовалось.

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

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

Тогда

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

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

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

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

, что составит

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

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

Так как 420 = 2²×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.

Беспорядки

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

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

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

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

Множество беспорядков есть множество . Следовательно, число на -элементном множестве составит

Вспомним теперь формулу Тейлора для функций и :

Тогда при больших число .

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

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

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

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

Доски

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

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

Доске с клетками, которая является частью квадратной доски , сопоставляется полином

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

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

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

Теорема 1. Если доски и дизъюнктны, то .

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

что и является коэффициентом при в произведении .

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

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

Тогда .

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

Возможны два случая: 1) в клетке есть ладья и 2) в клетке ладьи нет.

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

Теперь преобразуем ладейный полином для всей доски:

так как (на этой доске меньше клеток).

Для доски на рисунке выше, выбирая в качестве клетки среднюю, получим: