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

В комбінаториці бе́зладом називається перестановка без нерухомих точок, тобто жодний елемент не залишається на початковому місці.

Число безладів множини з n елементів, зазвичай позначається D_n, d_n, або !n, і називається «числом безладів» або «числом Монмора». (Ці числа узагальнюються числами, що відповідають числу зустрічей.) Функція субфакторіа́л (не плутайте з факторіалом n!) ставить у відповідність числу n число !n.^[1] Не існує стандартного позначення для субфакторіалу. Інколи позначають n¡ замість !n.^[2]

Задача підрахунку числа безладів була уперше розглянута П'єром де Монмором^[3] у 1708; він розв'язав її у 1713, як це зробив Микола I Бернуллі приблизно в той же час.

Припустимо, що професор дав чотирьом студентам (назвемо їх A, B, C і D) контрольну, а потім запропонував їм перевірити її один у одного. Звісно, жоден студент не повинен перевіряти свою контрольну. Скільки у професора варіантів розподілу контрольних, в яких жодному студенту не дістанеться своя робота? З усіх 24-х перестановок (4!) для повернення робіт, нам підходять тільки 9 безладів:

BADC, BCDA, BDAC,

CADB, CDAB, CDBA,

DABC, DCAB, DCBA.

У будь-який інший перестановці цих 4-х елементів, принаймні один студент отримує свою контрольну на перевірку.

Обчислення кількості безладів є популярною задачею в олімпіадній математиці^[ru], яка зустрічається в різних формулюваннях таких як завдання про безлад, завдання про листи, завдання про зустрічі і т. д.

Якщо ${\displaystyle n}$ листів випадковим чином покласти в ${\displaystyle n}$ різних конвертів, то яка ймовірність, що якийсь лист потрапить в свій конверт?

Відповідь дається виразом

${\displaystyle 1-{\frac {!n}{n!}}\approx 1-{\frac {1}{e}}}$

Таким чином, відповідь слабо залежить від кількості листів і конвертів і приблизно дорівнює константі ${\displaystyle 1-{\frac {1}{e}}\approx 0,63212}$.

Кількість всіх безладів порядку n може бути обчислено за допомогою принципу включення-виключення і дається виразом:

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

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

Кількість безладів ${\displaystyle !n=d(n)}$ задовольняє рекурсивним співвідношенням

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

і

${\displaystyle d(n)=nd(n-1)+(-1)^{n}}$

де ${\displaystyle d(1)=0}$ і ${\displaystyle d(2)=1}$

З огляду на те, що ${\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}}$, значення ${\displaystyle !n}$ зі збільшенням ${\displaystyle n}$ веде себе як ${\displaystyle {\frac {n!}{e}}}$. Більше того, при ${\displaystyle n>0}$ його можна представити як результат округлення числа ${\displaystyle {\frac {n!}{e}}}$.

• Парадокс днів народження

• Виведення формули кількості безладів трьома способами (англ.)
• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — ISBN 978-966-496-136-0.(укр.)
• Р. Стенлі. Перелічувальна комбінаторика. — М. : Мир, 1990. — С. 107-108.
• Baez, John (2003). Let's get deranged! (PDF). Архів оригіналу (PDF) за 30 вересня 2012. Процитовано 6 червня 2015.
• Bogart, Kenneth P. and Doyle, Peter G. (1985). Non-sexist solution of the ménage problem. Архів оригіналу за 20 липня 2008. Процитовано 6 червня 2015.
• Dickau, Robert M. Derangement diagrams. Figures Using Mathematica. Архів оригіналу за 27 червня 2008. Процитовано 6 червня 2015. {{cite web}}: Зовнішнє посилання в |work= (довідка)
• Hassani, Mehdi. Derangements and Applications. Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003. Архів оригіналу за 4 червня 2008. Процитовано 6 червня 2015.
• Weisstein, Eric W. Безлад(англ.) на сайті Wolfram MathWorld.