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

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

${\displaystyle _{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) показывают число беспорядков. Так,

${\displaystyle D_{0,0}=1,}$

${\displaystyle D_{1,0}=0,}$

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

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

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

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

Доказательство просто, если уметь считать число беспорядков ${\displaystyle !n}$: выберем m фиксированных элементов из n, затем посчитаем число беспорядков оставшихся n − m элементов (это будет ${\displaystyle !(n-m)={(n-m)!}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}}$).

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

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

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

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

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

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

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

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