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

В комбинаторной математике под числом встреч понимается число перестановок множества {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\mathrm{╲<!--\; ╲\; -->}{}^k$$_{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_{0,0}=1,$ 

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

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

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

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

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

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

$D_{n,m}=C_n^m{D}_{n-<!--\; -\; -->m,0}=\frac{n!}{m!}\underset{k=0}{\overset{n-<!--\; -\; -->m}{\sum <!--\; \sum \; -->}}\frac{(-<!--\; -\; -->1{)}^k}{k!}.$$D_{{n,m}}=C_{n}^{m}D_{{n-m,0}}={\frac {n!}{m!}}\sum _{{k=0}}^{{n-m}}{\frac {(-1)^{k}}{k!}}.$ 

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

$\frac{D_{n,m}}{n!}\approx <!--\; \approx \; -->\frac{e^{-<!--\; -\; -->1}}{m!}$${\frac {D_{{n,m}}}{n!}}\approx {\frac {e^{{-1}}}{m!}}$ 

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

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

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

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

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

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

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

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

$\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{D_{n,k}}{n!}=\frac{e^{-<!--\; -\; -->1}}{k!}.$$\lim _{{n\to \infty }}{D_{{n,k}} \over n!}={e^{{-1}} \over k!}.$ 

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

СсылкиПравить

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