Номера Rencontres - Rencontres numbers

В комбинаторный математика, то номера rencontres площадь треугольная решетка из целые числа что перечислить перестановки множества {1, ...,п } с указанным количеством фиксированные точки: другими словами, частичные расстройства. (Rencontre французский для сталкиваться. По некоторым сведениям, проблема названа в честь пасьянс игра.) п ≥ 0 и 0 ≤ k ≤ п, число контактов D_п, k - количество перестановок {1, ...,п } которые имеют ровно k фиксированные точки.

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

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

Вот начало этого массива (последовательность A008290 в OEIS ):

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})\!}$

для неотрицательных п. Оказывается, что

${\displaystyle D_{n,0}=\left\lceil {\frac {n!}{e}}\right\rfloor ,}$

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

В общем, для любого ${\displaystyle k\geq 0}$, у нас есть

${\displaystyle D_{n,k}={n \choose k}\cdot D_{n-k,0}.}$

Доказательство легко, если знать, как перечислить расстройства: выбрать k фиксированные точки вне п; затем выберите психическое расстройство другого п − k точки.

Цифры D_п,0/(п!) находятся генерируется посредством степенной ряд е^−z/(1 − z); соответственно, явная формула для D_п, м можно получить следующим образом:

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

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

${\displaystyle D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{ and }}\;\;{\frac {D_{n,m}}{n!}}\approx {\frac {e^{-1}}{m!}}}$

за п большой, м фиксированный.

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

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

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

За п ≥ 1, ожидал количество неподвижных точек равно 1 (факт, вытекающий из линейности математического ожидания).

В более общем плане для я ≤ п, то яth момент этого распределения вероятностей является яй момент распределение Пуассона с ожидаемым значением 1.^[1] За я > п, то я-й момент меньше, чем у этого распределения Пуассона. В частности, для я ≤ п, то яй момент - это яth Номер звонка, т.е. количество перегородки набора размеров я.

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

По мере роста размера пермутированного множества мы получаем

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

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

Рекомендации

1. Джим Питман, "Некоторые вероятностные аспекты Установить разделы ", Американский математический ежемесячный журнал, том 104, номер 3, март 1997 г., страницы 201–209.

• Риордан, Джон, Введение в комбинаторный анализ, New York, Wiley, 1958, страницы 57, 58 и 65.
• Вайсштейн, Эрик В. «Частичные расстройства». MathWorld.