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

Беспорядок в комбинаторике — перестановка без неподвижных точек; количество беспорядков заданного числа ${\displaystyle n}$ — его субфакториал${\displaystyle !n}$.

Пример задачи, где требуется вычислить число всех беспорядков — задача о письмах, считающаяся классикой олимпиадной математики: если ${\displaystyle n}$ писем случайным образом положить в ${\displaystyle n}$ различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт? Ответ даётся выражением:

${\displaystyle 1-{\frac {!n}{n!}}}$, при этом при увеличении n вычитаемое ${\displaystyle {\frac {!n}{n!}}}$ стремится к пределу^[1]${\displaystyle \lim _{n\to \infty }{!n \over n!}=\lim _{n\to \infty }\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}=e^{-1}\approx 0.36788\ldots .}$

Таким образом, ответ почти не зависит (при ${\textstyle n\geq 5}$) от количества писем и конвертов и примерно равен константе ${\displaystyle 1-e^{-1}\approx 0{,}63212}$.

Количество беспорядков порядка ${\displaystyle n}$ равно субфакториалу числа ${\displaystyle n}$ и вычисляется по формуле^[2]:

${\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!}}.}$

Воспользуемся принципом включений-исключений^[2]. Обозначим через ${\displaystyle A_{i}}$ множество перестановок ${\displaystyle n}$ элементов, в которых ${\displaystyle i}$-й элемент стоит на своём месте. Тогда:

${\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A}}_{i}\right|=|U|-\sum _{i}|A_{i}|+\sum _{i$

где ${\displaystyle U}$ — множество всех перестановок порядка ${\displaystyle n}$, а ${\displaystyle {\bar {A}}_{i}}$ — множество перестановок, в которых ${\displaystyle i}$-й элемент не стоит на своём месте. Величина ${\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A}}_{i}\right|}$ есть искомое число беспорядков.

Поскольку ${\displaystyle |A_{i}|=(n-1)!}$ (позиция ${\displaystyle i}$ зафиксирована), получаем:

${\displaystyle \sum _{i=1}^{n}|A_{i}|={\binom {n}{1}}(n-1)!}$

Аналогично, для пересечения ${\displaystyle k}$ множеств ${\displaystyle A_{i_{1}}\cap \dots \cap A_{i_{k}}}$ имеем ${\displaystyle |A_{i_{1}}\cap \dots \cap A_{i_{k}}|=(n-k)!}$, а число способов выбрать ${\displaystyle k}$ позиций равно ${\displaystyle {\binom {n}{k}}}$, откуда:

${\displaystyle \sum _{1\leq i_{1}<\dots$

Подставляя в формулу включений-исключений и раскрывая биномиальный коэффициент, получаем:

${\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A}}_{i}\right|=n!+\sum _{k=1}^{n}(-1)^{k}{\binom {n}{k}}(n-k)!=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}.}$

Число беспорядков удовлетворяет двум рекуррентным соотношениям^[2][1]:

${\displaystyle D(n)=(n-1){\bigl [}D(n-1)+D(n-2){\bigr ]},}$

${\displaystyle D(n)=n\cdot D(n-1)+(-1)^{n},}$

при начальных условиях ${\displaystyle D(1)=0}$, ${\displaystyle D(2)=1}$.

Второе соотношение. Так как ${\displaystyle D(n)={!n}}$, перепишем формулу субфакториала:

${\displaystyle !n=n!\sum _{k=0}^{n-1}{\frac {(-1)^{k}}{k!}}+(-1)^{n}=n\cdot !(n-1)+(-1)^{n}.}$

Первое соотношение. Пусть первый элемент занял место с номером ${\displaystyle i}$ (${\displaystyle n-1}$ вариантов, так как место 1 запрещено). Далее возможны два случая:

• Элемент ${\displaystyle i}$ занимает место 1. Остаются ${\displaystyle n-2}$ элемента и ${\displaystyle n-2}$ мест — задача сводится к ${\displaystyle D(n-2)}$ беспорядкам.
• Элемент ${\displaystyle i}$ не занимает место 1. Это равносильно задаче для ${\displaystyle n-1}$ элементов (место 1 запрещено для ${\displaystyle i}$-го элемента) — задача сводится к ${\displaystyle D(n-1)}$ беспорядкам.

Так как оба случая не пересекаются, суммируя и учитывая ${\displaystyle n-1}$ вариантов для выбора ${\displaystyle i}$, получаем первое соотношение.

1. ↑ ¹²Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107–108.
2. ↑ ¹²³Виленкин Н. Я., Виленкин А. Н., Виленкин П. А. Комбинаторика. — 4-е изд., испр. — М.: МЦНМО, 2013. — ISBN 978-5-89492-018-4.

• Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика, Изд. 4-е, исправленное. — МЦНМО ISBN 978-5-89492-018-4, 2013.
• Р. Стенли. Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107—108.