Математика / Дискретная математика

Распределение числа совпадений в перестановке

Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.

Опубликовано: Обновлено:

Формула

$$D_{n,k}=\binom nk !(n-k)$$
Схема Совпадения пяти объектов
44k=045k=120k=210k=30k=41k=5

Над каждым 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 должны появиться автоматически. Если они нарушены, на остатке разрешены лишние фиксированные места.

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

  1. Запишите число объектов n и требуемое число совпадений k; проверьте целые границы 0≤k≤n и различимость объектов.
  2. Выберите совпавшие позиции биномиальным коэффициентом C(n,k); порядок перечисления выбранных мест не создаёт новых вариантов.
  3. Вычислите число беспорядков остатка m=n−k по рекурсии !m=(m−1)(!(m−1)+!(m−2)), начиная с !0=1 и !1=0.
  4. Перемножьте число наборов совпавших мест и число беспорядков; для вероятности разделите результат на полное число перестановок 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

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

Математика

Ладейный многочлен: назначения с запретами

$N(B)=\sum_{k=0}^{n}(-1)^k r_k(B)(n-k)!,\qquad r_0(B)=1$

Ладейные числа считают совместимые наборы запрещённых назначений. Чередующаяся сумма с факториалами затем даёт число перестановок, которые избегают всех запрещённых клеток таблицы.

Математика

Лемма Бёрнсайда: число объектов с учётом симметрий

$|X/G|=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|$

Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.

Математика

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

$P_n=n!$

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