Число встреч (комбинаторика)

В комбинаторной математике под числом встреч понимается число перестановок множества {1, ..., n} с заданным числом неподвижных элементов. Для n ≥ 0 и 0 ≤ k ≤ n число встреч D_n, k – это число перестановок {1, ..., n}, содержащих ровно k элементов, не изменивших положение в перестановке.

Например, если семь подарков было выдано семи различным лицам, но только два человека получили подарки, предназначенные именно им, в D_7, 2 = 924 вариантах. В другом часто приводимом примере, в школе танцев с семью парами учеников, после перерыва на чай, участники случайно выбирают партнера для продолжения танцев, и снова в D_7, 2 = 924 случаях 2 пары окажутся прежними.

Численные значения

Фрагмент таблицы числа встреч (последовательность A008290 в OEIS):

$_{n}\!\!\diagdown \!\!^{k}$	0	1	2	3	4	5	6	7
0	1
1	0	1
2	1	0	1
3	2	3	0	1
4	9	8	6	0	1
5	44	45	20	10	0	1
6	265	264	135	40	15	0	1
7	1854	1855	924	315	70	21	0	1

Формулы

Числа в первом столбце (k = 0) показывают число беспорядков. Так,

D_{0,0}=1,

D_{1,0}=0,

D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})

для неотрицательного n. Оказывается

D_{n,0}=\left[{n! \over e}\right]

,

где дробь округляется вверх для четных n и вниз для нечетных, и для n ≥ 1, это соответствует ближайшему целому.

Доказательство просто, если уметь считать число беспорядков $!n$ : выберем m фиксированных элементов из n, затем посчитаем число беспорядков оставшихся n − m элементов (это будет ${\displaystyle$ ).

D_{n,m}=C_{n}^{m}D_{n-m,0}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.

[1]

Отсюда следует, что

{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}

для больших n и фиксированного m.

Распределение вероятности

Сумма элементов строки в вышеприведенной таблице является числом всех перестановок набора {1, ..., n}, и она равна n!. Если разделить все элементы строки n на n!, получим распределение вероятностей числа перестановок с неподвижными точками в равномерно распределенных случайных перестановках элементов {1, ..., n}. Вероятность того, что перестановка будет иметь k неподвижных точек, равна

{D_{n,k} \over n!}.

Для n ≥ 1 математическое ожидание числа неподвижных точек равно 1.

Более того, для i ≤ n, i-й момент этого распределения является i-м моментом распределения Пуассона со значением 1.[2] Для i > n i-й момент меньше соответствующего момента распределения Пуассона. Точнее, для i ≤ n i-й момент является i-м числом Белла, т. е. число разбиений множества размера i.

Ограничение значений распределения вероятности

С возрастанием числа элементов мы получим

\lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.

Это как раз равно вероятности того, что случайная величина, распределенная по закону Пуассона с математическим ожиданием 1, равна k. Другими словами, при возрастании n распределение числа неподвижных точек у случайной перестановки n элементов приближается к распределению Пуассона с математическим ожиданием 1.

Примечания

Кофман А. — Введение в прикладную комбинаторику — 1975.
Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.

Ссылки

John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
Weisstein, Eric W. Partial Derangements (англ.) на сайте Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Кофман А. — Введение в прикладную комбинаторику — 1975.

[2] Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.