Вообще математика — наука довольно строгая и упорядоченная, но и в ней есть место небольшому хаосу. А конкретно — беспорядкам. 😜

Что это
Беспорядком длины n называется любая перестановка множества {1, 2, …, n}, у которой ни один элемент не стоит на своём месте.
То есть 1 не стоит на первой позиции, 2 не стоит на второй, 3 — на третьей и т. д.

Пример
Для множества {1, 2, 3} беспорядками будут 312 и 231. А вот 321 — не беспорядок, ведь число 2 сохранило своё место!

Количество беспорядков
Число всех беспорядков длины n обозначают через !n. Читается как «субфакториал». Очень похоже на обозначение факториала, только восклицательный знак стоит с другой стороны (даже тут хаос!)

Если в множестве два элемента, беспорядок будет всего один — это 21. Значит, !2=1.
Для множества из трёх элементов беспорядков будет !3=2 штуки — это 231 и 312.

Как посчитать количество беспорядков
Простой способ — выписать все возможные перестановки и выбрать из них беспорядки. Это удобно для маленьких множеств. Но для больших множеств перестановок становится многовато. Например, для множества из 6 элементов их уже 720 — не очень хочется столько перебирать!

Облегчит жизнь рекуррентная формула — она позволяет вычислить число беспорядков, опираясь на два предыдущих значения. Для !4 понадобятся !3 и !2, для !5 — !4 и !3, для !6 — !5 и !4 и так далее.

В общем виде рекуррентная формула для количества беспорядков выглядит так:
!n = (n-1)⋅(!(n-1) + !(n-2))

Почему и как это работает — можно увидеть на интерактивной иллюстрации из нашего бесплатного тренажёра. Она показывает, как вычислить !4, для общего вида логика будет такая же.

Задачи с беспорядками
➡️ Вчерашняя задача о династических браках — как раз о беспорядках! Невеста и жених должны быть из разных домов — разумное жизненное требование, а с точки зрения математики — беспорядок! Решение этой задачи мы положили в комментарии ко вчерашнему посту.
➡️ Задача о перепутанных телефонах
➡️ Задача про Тайного Санту

А в каких ещё ситуациях вам встречались беспорядки?