Задача о беспорядках

Интуитивная постановка задачи

Пример

Пусть в рамках чемпионата в $n$ городах должно пройти ровно по одному матчу.

Матчи судят $n$ судей, каждый из которых из одного из городов, все из разных.

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

Пример

Пусть $n$ человек пришли в театр и сдали шляпы в гардероб.

Когда спектакль закончился и зрители получили шляпы назад, оказалось, что каждый из $n$ получил чужую шляпу.

Сколько существует вариантов такого события?

Формальная постановка задачи

Определение:

Беспорядком на множестве $\{1,...,n\}$ называется перестановка, которая не сохраняет ни одного элемента: $\pi(i)\neq i, i=\overline{1,n}$.

Рис. 1. Беспорядок — перестановка без неподвижных точек. Слева перестановка оставляет элементы 1 и 4 на месте (стрелки перечёркнуты), справа все четыре элемента сдвинуты. Для [math]\displaystyle{ n=4 }[/math] беспорядков 9 из 24 перестановок.

Задача. Найти число беспорядков на множестве $\{1,...,n\}$: $D(n) = |\{\pi | \pi\in\sigma_n, \pi(i)\neq i, i=\overline{1,n}\}|$.

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

Будем говорить, что $\pi\in\sigma_n$ обладает свойством $i$, если $\pi(i)=i$. Тогда $S=\{1,...,n\}$ — множество всех свойств, которыми может обладать перестановка.

Пусть $T\subseteq S$, $f_=(T)$ — число перестановок, каждая из которых обладает всеми свойствами из $T$ и не обладает свойствами из $S\setminus T$: [math]\displaystyle{ f_=(T) = |\{\pi | \pi\in\sigma_n, \pi(i)=i, i\in T; \pi(j)\neq j, j\in S\setminus T\}|. }[/math]

$f_\geq(T)$ — число перестановок, каждая из которых обладает всеми свойствами из $T$ и, возможно, какими-то еще: [math]\displaystyle{ f_\geq(T) = |\{\pi | \pi\in\sigma_n, \pi(i)=i, i\in T\}|. }[/math] Следовательно, верна формула: $f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y)$.

Нетрудно видеть, что $f_\geq(T) = |S\setminus T|!$ — число перестановок на множестве $S\setminus T$.

Рис. 2. Если закрепить [math]\displaystyle{ T=\{1,3\} }[/math], свободными остаются [math]\displaystyle{ n-|T|=2 }[/math] элемента; их можно переставить [math]\displaystyle{ 2!=2 }[/math] способами. Поэтому [math]\displaystyle{ f_\geq(T)=(n-|T|)! }[/math]; только второй вариант входит в [math]\displaystyle{ f_=(T) }[/math].

Очевидно, $D(n) = f_=(\varnothing)$. Следующее утверждение решает задачу.

Утверждение:

$D(n) = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}.$

Доказательство:

Так как [math]\displaystyle{ f_\geq(T) = |S\setminus T|! }[/math], то по формуле включения-исключения

[math]\displaystyle{ D(n) = f_=(\varnothing)= \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y) = \sum_{Y\subseteq S} (-1)^{|Y|} |S\setminus Y|!= }[/math] [math]\displaystyle{ = \sum_{i=0}^{n} \sum_{\substack{Y\subseteq S,\\ |Y|=i}} (-1)^{i} (n-i)! = \sum_{i=0}^{n} (-1)^i(n-i)!\binom{n}{i} = }[/math] [math]\displaystyle{ = \sum_{i=0}^{n} (-1)^i \frac{(n-i)! n!}{i! (n-i)!} = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}. }[/math]

[math]\displaystyle{ \blacksquare }[/math]

Рис. 3. Слагаемые [math]\displaystyle{ D(4) }[/math], сгруппированные по числу [math]\displaystyle{ i }[/math] закреплённых свойств: [math]\displaystyle{ C(4,i) }[/math] наборов по [math]\displaystyle{ (4-i)! }[/math] перестановок. Сумма [math]\displaystyle{ 24-24+12-4+1=9 }[/math]; то же даёт [math]\displaystyle{ 4!(1-1+1/2-1/6+1/24) }[/math].

Конспект: Дискретная математика