Математика / Графы, логика

Беспорядки: перестановки без неподвижных точек

Беспорядок — перестановка, в которой ни один элемент не остаётся на своём первоначальном месте. Формула включений и исключений считает такие перестановки и помогает находить вероятность полного несовпадения.

Опубликовано: 16 октября 2026 г.Обновлено: 16 октября 2026 г.

Формула

D_n=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}

Схема Девять беспорядков четырёх элементов

Ни одна из девяти перестановок не содержит неподвижной точки.

Обозначения

$Dₙ$: число беспорядков n элементов, безразмерная величина
$n$: число различных элементов, безразмерная величина
$j$: число выбранных совпадающих позиций, безразмерная величина
$n!$: число всех перестановок, безразмерная величина

Условия применения

Все n элементов различимы, как и их исходные позиции. Единственный запрет — совпадение элемента с собственной позицией. Для вероятности Dₙ/n! дополнительно требуется равновероятный выбор среди всех перестановок. Для подсчёта принимаются D₀=1 и D₁=0.

Ограничения

Запреты нескольких позиций для одного элемента, обязательные пары и неравномерная раздача требуют другой модели. Приближение n!/e не является точным целым ответом без округления и оговорок. Событие «не все на своих местах» существенно шире события «ни один на своём месте».

Подробное объяснение

Из n! перестановок нужно удалить те, где хотя бы один элемент остался на своём месте. Если закрепить конкретный элемент, остальные можно переставить (n−1)! способами. Но простое вычитание n·(n−1)! удаляет перестановки с несколькими совпадениями неоднократно.

Принцип включений и исключений исправляет повторы. Для выбранных j неподвижных точек остаётся (n−j)! перестановок, а выбрать эти точки можно C(n,j) способами. Чередующаяся сумма имеет вид Σ(−1)ʲC(n,j)(n−j)!. После сокращения факториалов получается указанная формула.

Деление на n! даёт вероятность отсутствия совпадений при равномерной случайной перестановке. Конечная сумма 1−1+1/2!−1/3!+… приближается к e⁻¹. Поэтому для большого n вероятность близка к 0,3679, а не стремится к нулю.

Для точного вычисления удобна также рекурсия Dₙ=(n−1)(Dₙ₋₁+Dₙ₋₂) при n≥2. Она использует только целые числа и избегает сложения маленьких дробей с большим факториалом. Начальные значения дают D₂=1, D₃=2, D₄=9.

Беспорядок не требует единого цикла. При n=4 перестановка, меняющая местами первую пару и вторую пару, тоже не имеет неподвижных точек. Поэтому формула (n−1)! для одного цикла здесь не заменяет Dₙ.

Как пользоваться формулой

Пронумеруйте предметы и получателей одинаково, чтобы условие запрета записывалось как несовпадение номеров.
Убедитесь, что каждый предмет передаётся одному получателю, а других ограничений на раздачу в задаче нет.
Для небольшого n вычислите чередующуюся сумму или рекурсию с начальными значениями D₀=1 и D₁=0.
Если нужна вероятность, разделите Dₙ на n! только после подтверждения равновероятности всех перестановок.

Историческая справка

Задача о несовпадениях связана с ранней математической теорией карточных игр. В книге Пьера Ремона де Монмора Essay d’analyse sur les jeux de hazard 1708 года рассматривалась задача встреч, известная также через игру Treize. Университетский исторический материал MacTutor разбирает эту постановку и показывает малые случаи, включая девять беспорядков четырёх элементов. Современный язык заменяет карточные совпадения неподвижными точками перестановки и позволяет применять принцип включений и исключений. В NIST DLMF число беспорядков приведено в разделе о циклической записи перестановок. Такая формулировка объединяет историческую игровую задачу с нынешней дискретной математикой; современную сигма-запись не нужно дословно переносить в книгу начала XVIII века.

Историческая линия формулы

Исторический сюжет задачи встреч обоснованно связан с Монмором и его книгой 1708 года. Формула на странице дана в современной нотации перестановок и включений-исключений; это не утверждение, что её нынешняя запись буквально присутствовала в первом историческом изложении.

Пример

Четыре подписанных письма случайно раскладывают по четырём адресным конвертам, по одному в каждый. Сколько раскладок не имеют ни одного правильного адреса? D₄=4!(1−1+1/2!−1/3!+1/4!)=24(1/2−1/6+1/24)=12−4+1=9. Проверка рекурсией: D₂=1, D₃=2, поэтому D₄=3(D₃+D₂)=3·3=9. Всего раскладок 24, и при их равной вероятности шанс полного несовпадения равен 9/24=0,375, то есть 37,5%. Это не 23/24: такая доля относится к любому нарушению правильной раскладки, включая случаи, когда часть писем всё же попала в свои конверты.

Частая ошибка

Не путайте отсутствие всех совпадений с отсутствием хотя бы одного: это разные события. Не считайте предметы неразличимыми, иначе исходных перестановок не будет n!. Не заменяйте беспорядок одним циклом. Не округляйте члены чередующейся суммы заранее: точный ответ обязан оставаться целым.

Практика

Задачи с решением

Три подарка

Условие. Трое участников обмениваются тремя различными подарками; никто не должен получить свой. Сколько вариантов?

Решение. D₃=3!(1−1+1/2−1/6)=6·(1/3)=2.

Ответ. 2 варианта

Пять конвертов

Условие. Найдите число беспорядков пяти писем и вероятность при равномерной раздаче.

Решение. D₅=4(D₄+D₃)=4(9+2)=44. Вероятность 44/120=11/30≈0,366667.

Ответ. 44 варианта; вероятность 11/30

Дополнительные источники

https://dlmf.nist.gov/26.13
https://discrete.openmathbooks.org/dmoi3/sec_advPIE.html
https://mathshistory.st-andrews.ac.uk/Extras/Montmort_Treize/

Связанные формулы

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Формула включений и исключений для трех множеств

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Формула включений и исключений для трех множеств считает элементы, попавшие хотя бы в одно из A, B или C. Она складывает три мощности, вычитает попарные пересечения и возвращает тройное пересечение, чтобы каждый объект был учтен ровно один раз.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.