Математика / Дискретная математика
Распределение числа совпадений в перестановке
Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.
Формула
Над каждым k стоит точное число перестановок. Сумма высот равна 120, а при четырёх совпадениях пятый объект тоже вынужденно совпадает.
Обозначения
- $n$
- число различных объектов и позиций, шт.
- $k$
- требуемое точное число совпавших позиций, шт.
- $D_{n,k}$
- число перестановок с ровно k совпадениями, шт.
- $!m$
- число беспорядков m объектов; !0=1, !1=0, шт.
Условия применения
Объекты и позиции различимы, перестановки равновероятны, а совпадением считается пара «объект — исходное место». Числа n и k целые, 0≤k≤n. После выбора k фиксированных мест остальные n−k объекты должны образовать беспорядок.
Ограничения
Формула не подходит для независимых размещений с повторениями или неравных вероятностей. Для «не менее k» совпадений суммируют D по всем большим индексам. При k=n−1 результат нулевой: последний объект тоже обязан совпасть.
Подробное объяснение
Сначала выбирают k позиций, которые сохранят владельцев: C(n,k) способов. На остальных n−k позициях нельзя допустить дополнительного совпадения, поэтому остаётся !(n−k) беспорядков. Отсюда D(n,k)=C(n,k)!(n−k).
При k=0 получаем обычные беспорядки, а при k=n−1 — ноль, поскольку один оставшийся объект не может избежать совпадения. Сумма по всем k равна n!: каждая перестановка имеет ровно одно число совпадений. Деление D(n,k) на n! даёт вероятность.
Для больших n распределение числа совпадений приближается Пуассону с параметром 1, но при малых n нужна точная формула. Важно отличать «ровно» от «не менее»: простое умножение на (n−k)! разрешает дополнительные совпадения и завышает ответ.
Практический алгоритм состоит из выбора совпавших мест, расчёта беспорядка остатка и проверки суммы таблицы. Независимый перебор перестановок полезен для малых n и подтверждает формулу.
Эта структура также даёт быстрый тест на здравый смысл: крайние значения D(n,n)=1 и D(n,n−1)=0 должны появиться автоматически. Если они нарушены, на остатке разрешены лишние фиксированные места.
Как пользоваться формулой
- Запишите число объектов n и требуемое число совпадений k; проверьте целые границы 0≤k≤n и различимость объектов.
- Выберите совпавшие позиции биномиальным коэффициентом C(n,k); порядок перечисления выбранных мест не создаёт новых вариантов.
- Вычислите число беспорядков остатка m=n−k по рекурсии !m=(m−1)(!(m−1)+!(m−2)), начиная с !0=1 и !1=0.
- Перемножьте число наборов совпавших мест и число беспорядков; для вероятности разделите результат на полное число перестановок n!.
Историческая справка
Подсчёт неподвижных точек относится к классической традиции задач о случайной раздаче различных предметов владельцам. Его математическое содержание удобно отделить от бытового сюжета: любая перестановка разбивается на фиксированные позиции и перестановку оставшихся объектов без фиксированных позиций. Это разбиение даёт точную формулу без вероятностных приближений.
В современных учебниках комбинаторики и вероятностных методов начала XXI века те же задачи служат примерами включений и исключений и предельного распределения Пуассона. Переход от полного отсутствия совпадений к ровно k совпадениям сохраняет прежний подсчёт беспорядков, но добавляет выбор фиксированного множества. Историческое название rencontres обозначает совпадения; современная запись D(n,k) здесь введена для удобства и не приписывается единственному автору.
Историческая линия формулы
Подсчёт относится к классической комбинаторике перестановок и задачам о совпадениях, известным под названием rencontres. В приведённых учебных источниках он выводится из включений и исключений. Современное обозначение D(n,k) не рассматривается как отдельное историческое открытие.
Пример
Пять писем раскладывают по пяти конвертам. Ровно два совпадения: выбираем их C(5,2)=10 способами, а оставшиеся три располагаем как беспорядок !3=2. Получаем D(5,2)=10·2=20 и вероятность 20/120=1/6. Проверка строки: 44+45+20+10+0+1=120=5!, поэтому все перестановки учтены. Дополнительная проверка перебором всех 120 перестановок даёт ровно 20 строк с двумя совпадениями, что совпадает с вычислением по формуле. Важно, что 20 — это количество раскладок, а не вероятность: единица измерения у D — «раскладки», тогда как после деления получается безразмерная вероятность. Так сохраняется различие между подсчётом и оценкой события.
Частая ошибка
Нельзя использовать (n−k)! вместо !(n−k): это разрешает дополнительные совпадения. Нельзя забывать C(n,k), выбирающий совпавшие позиции. Для вероятности делят на n!, а не на C(n,k). Проверка суммы по k должна вернуть n!. Ещё одна ошибка — считать выбранные совпавшие места неразличимыми; они различимы по исходным индексам, поэтому нужен биномиальный множитель.
Практика
Задачи с решением
Ровно одно совпадение
Условие. Четыре письма раскладывают по конвертам. Сколько раскладок дают ровно одно совпадение?
Решение. D(4,1)=C(4,1)!3=4·2=8.
Ответ. 8 раскладок.
Проверка суммы
Условие. Для n=3 найдите D(3,0), D(3,1), D(3,2), D(3,3).
Решение. 2, 3, 0, 1; сумма 2+3+0+1=6=3!.
Ответ. Сумма равна 3!.
Дополнительные источники
- https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf
- https://ocw.mit.edu/courses/18-226-probabilistic-methods-in-combinatorics-fall-2022/mit18_226_f22_lec_full.pdf
Связанные формулы
Математика
Ладейный многочлен: назначения с запретами
Ладейные числа считают совместимые наборы запрещённых назначений. Чередующаяся сумма с факториалами затем даёт число перестановок, которые избегают всех запрещённых клеток таблицы.
Математика
Лемма Бёрнсайда: число объектов с учётом симметрий
Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.
Математика
Эйлеровы числа: перестановки с заданным числом спусков
Эйлерово число A(n,k) считает перестановки n различных чисел с ровно k спусками между соседними позициями. Рекурсия строит распределение по k вставкой нового наибольшего элемента.
Математика
Число перестановок без повторений
Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.