§ 7. Задача о беспорядках и встречах

Пусть задано конечное (упорядоченное) множество чисел 1, 2, 3,...,n. Из них могут быть образованы различные перестановки. Число всех перестановок рано n! Среди этих перестановок имеются такие, что ни один элемент не сохранил своего первоначального места: ai ≠ i, i=1,2,...,n. Такие перестановки называют беспорядками. Сколько существует беспорядков?

Введем свойства p1, p2, ..., pn такие, что свойство pi означает, что элемент ai остался на своём месте: ai = i, i=1,2,...,n.

Пусть N(k) – число перестановок, для которых k элементов находятся на своих местах. Ясно, что число N(k) равно (n–k)! Число беспорядков, т. е. число N(0), находится с помощью метода включения и исключения. Тогда имеем:

$N(0)=n!-C_n^1 (n-1)! + C_n^2 (n-2)! - ... + (-1)^k C_n^k (n-k)!+...= n!(1-1+\frac{1}{2!}-\frac{1}{3!} + ... +\frac{(-1)^n}{n!})$

Это число является целым числом, ближайшим к (n! e-1). Например, если n = 7, то N(0)=1854.

Если нас интересует число перестановок, для которых ai=i точно в r местах $(0 < r < n)$, то возникает задача, известная под названием «задачи о встречах». В этом случае получим следующее: r чисел из 1,2,...,n можно выбрать r n C способами и, выбрав их, умножим на число беспорядков из оставшихся n - r символов. В результате получим:

$N(r)=\frac{n!}{r!}(1-1+\frac{1}{2!}+...+(-1)^{n-r} \frac{1}{(n-r)!})$