Вероятность и статистика · объяснение и практика
Как посчитать перестановки без единого совпадения с исходным местом
Посчитайте перестановки, в которых ни один различимый предмет не остаётся на своём месте, и не путайте их с одним общим циклическим сдвигом.

В теме Комбинаторика и пространство исходов · Учебная карта
Главная мысль
Число беспорядков Dₙ считает перестановки без неподвижных точек. Оно равно n!·Σ от j=0 до n величин (−1)ʲ/j!; для равновероятной перестановки вероятность равна Dₙ/n!.
Запрещено каждое совпадение с исходной позицией
Есть n разных конвертов и n разных подписанных карточек. Каждую карточку кладут в один конверт так, чтобы каждый получил ровно одну. Условие беспорядка означает, что ни одна карточка не попала в свой конверт. Просто изменить общий порядок недостаточно: перестановка может быть не исходной, но сохранять несколько отдельных совпадений.
Циклический сдвиг на одно место действительно подходит при нескольких предметах, но это лишь один из многих возможных беспорядков. Не надо требовать, чтобы все предметы составляли один длинный цикл. Например, две независимые перестановки местами в двух парах тоже не оставляют ни одного предмета на своей позиции. Различимость предметов существенна для общего числа n!.
Включения и исключения удаляют все совпадения
Начинаем со всех n! перестановок. Для каждой выбранной позиции с совпадением остальные предметы переставляются произвольно. Если закреплены j конкретных совпадений, остаётся (n−j)! перестановок. Вычитая одиночные события, добавляя парные пересечения и продолжая знаки, получаем Dₙ=Σ(−1)ʲC(n,j)(n−j)!. Это та же факториальная сумма из короткого ответа.
Для четырёх предметов расчёт равен 24−24+12−4+1=9. Вероятность при равномерной случайной перестановке — 9/24=3/8. Нельзя ограничиться вычитанием четырёх событий по шесть: перестановки с несколькими совпадениями тогда были бы вычтены повторно и итог исказился бы.
Пример
Известны D₃=2 и D₄=9. Найдите D₅ по рекурсии Dₙ=(n−1)(Dₙ₋₁+Dₙ₋₂).
Получаем D₅=4(9+2)=44. Среди всех 120 перестановок это вероятность 44/120=11/30. Начальные значения рекурсии D₀=1 и D₁=0 учитывают пустую перестановку и невозможность сдвинуть единственный предмет.
Вероятностная модель задаёт веса перестановок
Деление на n! справедливо, когда все перестановки равновероятны. Если алгоритм перемешивания предпочитает некоторые порядки, комбинаторное число беспорядков остаётся тем же, но вероятность уже не равна простой доле. Например, выбор одного случайного циклического сдвига — совсем не равномерная перестановка всего набора.
Для больших n доля приближается к 1/e, но это не точное значение для каждого конечного размера. На малых наборах нужно считать точно. Края тоже важны: у одного предмета беспорядков нет, у двух — один. Случай «хотя бы один предмет не на месте» является другим, гораздо более слабым условием и не решается тем же числителем.
От чтения к действию
А теперь — вы
Частые вопросы
Все предметы должны образовать один цикл?
Нет. Разрешены несколько циклов длиной не меньше двух. Запрещены только неподвижные точки, то есть циклы длиной один.
Всегда ли вероятность близка к 1/e?
Это предельное приближение для равномерных перестановок при больших n. Для конкретного небольшого набора точное отношение Dₙ/n! может заметно отличаться.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как включения и исключения считают распределения без пустых ящиков
Посчитайте размещения различимых объектов по подписанным ящикам без пустых: включения и исключения исправят многократное вычитание.
Открыть темуПочему совпадение дней рождения зависит от числа пар
Вычислите вероятность любого совпадения через дополнение к случаю всех разных и отличите её от совпадения с одним заранее названным днём.
Открыть тему