Беспорядок (перестановка)

Не следует путать с Инверсия (перестановка).

В комбинаторике беспорядком называется перестановка без неподвижных точек.

Примеры

Проверка работ

Допустим, профессор дал четырём студентам (назовём их A, B, C и D) контрольную, а затем предложил им проверить её друг у друга. Естественно, ни один студент не должен проверять свою контрольную. Сколько у профессора вариантов распределения контрольных, в которых ни одному студенту не достанется своя работа? Из всех 24 перестановок (4!) для возврата работ, нам подходят только 9 беспорядков:

   BADC, BCDA, BDAC,
   CADB, CDAB, CDBA,
   DABC, DCAB, DCBA.

В любой другой перестановке этих 4 элементов как минимум один студент получает свою контрольную на проверку.

Задача о письмах

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

Если [math]\displaystyle{ n }[/math] писем случайным образом положить в [math]\displaystyle{ n }[/math] различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт?

Ответ даётся выражением

[math]\displaystyle{ 1 - \frac{!n}{n!} \approx 1 - \frac{1}{e}. }[/math]

Таким образом, ответ слабо зависит от количества писем и конвертов и примерно равен константе [math]\displaystyle{ 1 - \frac{1}{e} \approx 0{,}63212 }[/math].

Количество беспорядков

Количество всех беспорядков порядка n может быть вычислено с помощью принципа включения-исключения и дается выражением

[math]\displaystyle{ !n = n! - \frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\dots +(-1)^n\frac{n!}{n!} = \sum_{k=0}^n(-1)^k\frac{n!}{k!}, }[/math]

которое называется субфакториалом числа n.

Количество беспорядков [math]\displaystyle{ !n = d(n) }[/math] удовлетворяет рекурсивным соотношениям

[math]\displaystyle{ d(n) = (n-1)[d(n-1) + d(n-2)] }[/math]

и

[math]\displaystyle{ d(n) = n d(n-1) + (-1)^n, }[/math]

где [math]\displaystyle{ d(1) = 0 }[/math] и [math]\displaystyle{ d(2) = 1 }[/math].

Ввиду того, что [math]\displaystyle{ \sum_{k=0}^\infty(-1)^k\frac{1}{k!} = \frac{1}{e} }[/math], значение [math]\displaystyle{ !n }[/math] с ростом [math]\displaystyle{ n }[/math] ведёт себя как [math]\displaystyle{ \frac{n!}{e} }[/math]. Более того, при [math]\displaystyle{ n \gt 0 }[/math] его можно представить как результат округления числа [math]\displaystyle{ \frac{n!}{e} }[/math].

См. также

• Парадокс дней рождения

Ссылки

• Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.