Задача о числе беспорядков (Задача о встречах)

В качеcтве канонического примера возможного приложения выведенной формулы включений-исключений рассмотрим знаменитую задачу о числе беспорядков или инверсий.

Пусть мы хотим найти число таких перестановок _n , которые не имеют неподвижных точек, то есть ни один элемент не стоит на своем месте: (i)  i для всех i  {1, 2, ... ,n}. Таким образом, мы ищем число перестановок a₁a₂ ...a_n n чисел {1,2, ... , n}, таких, что , i = 1,2, ... , n. Такие перестановки будем называть беспорядками. Обозначим их число D(n). Тогда D(0)=1, D(1)=0, D(2)=1, D(3)=2.

Рассмотрим множество _n всех n! перестановок b₁ b₂ ...b_n , и пусть свойство_i перестановки  состоит в том, что b_i = i. Тогда N(n-s)! , i₁< ...< i_s , поскольку они являются перестановками, в которых s объектов закреплены на своих позициях, а остальные объекты свободны. Число беспорядков есть N₀ и применение формулы включений-исключений дает равенство

,

так как число способов выбора k неподвижных точек из n- элементного множества есть .

Последнее выражение после упрощений можно переписать в виде:

. (1.26)

Сумма в скобках в ( 1 .26) есть начальный отрезок ряда . Из формулы ( 1 .26) видно, что - хорошее приближение к D(n), и, в действительности, нетрудно показать, что D(n) - ближайшее целое к . Это означает, что беспорядки составляют фиксированную долю е^-1 всех перестановок и, что удивительно, эта доля не зависит от n .

В задаче о беспорядках функция b(i) (см. ( 1 .23)) имеет очень специальное свойство b(i)=i! - она зависит только от i, но не зависит от n. Эквивалентным образом, число перестановок, множество подвижных точек которых лежит во множестве T, зависит только от T , но не от n. Это означает, что формулу ( 1 .26) можно переписать на языке конечных разностей (см. уравнение ( 1 .6)) в виде

.

(Сокращенная запись D(n) = ⁿ 0!).

Так как число b(i) перестановок, подвижные точки которых содержатся в некотором определенном i -элементном множестве, зависит только от i, то же верно и для числа a(i) перестановок , имеющих в качестве множества подвижных точек некоторое определенное i -элементное множество. Из комбинаторных соображений ясно, что a(i) = D(i). 

Из формулы ( 1 .26) также немедленно следует, что при n  1

D(n) = nD(n1) + (1)ⁿ , (1.27)

D(n) = nD(n1) + D(n2). (1.28)

Значительного труда требует комбинаторное доказательство формулы ( 1 .27), хотя прямое комбинаторное доказательство ( 1 .28) совершенно просто. Приведем его.

Выберем и зафиксируем некоторый элемент i>1 множества {1, 2, ... , n}. Все перестановки без неподвижных точек разобьем на два типа следующим образом. К первому типу K₁ отнесем перестановки, в которых i стоит на первом месте, но 1 не стоит на i-ом месте ( K₁ = {_n (i)=1, (1)  i}). Количество таких перестановок равно D(n1). Ко второму типу K₂ отнесем перестановки, в которых i стоит на первом месте, а 1 на i-ом месте ( K₂ = {_n (i)=1, (1) = i}). Количество таких перестановок равно D(n2). Указанные типы перестановок не пересекаются, а их объединение по всем значениям i дает множество всех перестановок без неподвижных точек. Учитывая, что элемент i может быть выбран n  1 способом, получаем формулу ( 1 .28). 

Рассмотрим пример, к которому непосредственно неприложимы предшествующие рассуждения, проведенные при решении задачи о числе беспорядков. Пусть h(n) - число таких перестановок мультимножества M_n = {1²,2², ... , n²}, никакие два последовательных члена которых не равны. Таким образом, h(0) = 1, h(1) = 0, h(2) = 2 (соответствующие перестановки есть 1212 и 2121). Пусть A - множество всех перестановок  мультимножества M_n и P_i для 1 i  n - свойство перестановки  иметь последовательными членами два числа i. Тогда мы ищем f₌() =h(n). Из соображений симметрии ясно, что при фиксированном n f _ (T) зависит только от i = T , так что обозначим g(i) = f _ (T). Ясно, что g(i) равно числу перестановок  мультимножества {1, 2, ... , (i+1)², (i+2)², ... ,n²} (замените каждое число j  i, встречающееся в , двумя последовательными членами, равными j), так что

g(i) = (2n  i)! 2^{- (n - i)} .

Заметим, что b(i) = g(n  i) = (n+i)!2^{ i} не является функцией лишь от i, так что предшествующее рассуждение в действительности неприменимо. Однако из формулы ( 1 .25) получаем, что

.