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

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

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

Примеры

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

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

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

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

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

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

Если $n$$n$  писем случайным образом положить в $n$$n$  различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт?

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

$1-<!--\; -\; -->\frac{!n}{n!}\approx <!--\; \approx \; -->1-<!--\; -\; -->\frac{1}{e}.$$1-{\frac {!n}{n!}}\approx 1-{\frac {1}{e}}.$ 

Таким образом, ответ слабо зависит от количества писем и конвертов и примерно равен константе $1-<!--\; -\; -->\frac{1}{e}\approx <!--\; \approx \; -->\mathrm{0,632}12$$1-{\frac {1}{e}}\approx 0{,}63212$ .

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

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

$!n=n!-<!--\; -\; -->\frac{n!}{1!}+\frac{n!}{2!}-<!--\; -\; -->\frac{n!}{3!}+\cdots <!--\; \cdots \; -->+(-<!--\; -\; -->1{)}^n\frac{n!}{n!}=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^k\frac{n!}{k!},$$!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!}},$ 

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

Количество беспорядков $!n=d(n)$$!n=d(n)$  удовлетворяет рекурсивным соотношениям

$d(n)=(n-<!--\; -\; -->1)[d(n-<!--\; -\; -->1)+d(n-<!--\; -\; -->2)]$$d(n)=(n-1)[d(n-1)+d(n-2)]$ 

и

$d(n)=nd(n-<!--\; -\; -->1)+(-<!--\; -\; -->1{)}^n,$$d(n)=nd(n-1)+(-1)^{n},$ 

где $d(1)=0$$d(1)=0$  и $d(2)=1$$d(2)=1$ .

Ввиду того, что $\underset{k=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}(-<!--\; -\; -->1{)}^k\frac{1}{k!}=\frac{1}{e}$$\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$ , значение $!n$$!n$  с ростом $n$$n$  ведёт себя как $\frac{n!}{e}$${\frac {n!}{e}}$ . Более того, при $n>0$$n>0$  его можно представить как результат округления числа $\frac{n!}{e}$${\frac {n!}{e}}$ .

См. также

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

Ссылки

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