Номера знакомств

В комбинаторике представляют числа recontres собой треугольный массив целых чисел , перечисляющий перестановки набора {1,..., n } с заданным числом фиксированных точек : другими словами, частичные нарушения . ( Rencontre по-французски означает «встреча» . По некоторым сведениям, проблема названа в честь пасьянса .) Для n ≥ 0 и 0 ≤ k ≤ n число recontres D _{n , k} — это количество перестановок { 1, .. ., n }, которые имеют ровно k неподвижных точек.

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

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

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

к н	0	1	2	3	4	5	6	7	8
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
8	14833	14832	7420	2464	630	112	28	0	1

показывать упорядочен по количеству перемещенных элементов
The usual way (table above) to show the rencontres numbers is in columns corresponding to the number of fixed points $k$. But one can also order them in columns corresponding to the number of moved elements $i=n-k$ (sequence A098825 in the OEIS). Each entry in the table below on the left can be factored into two terms given in the table below on the right: the product of a binomial coefficient (given first in red) and a subfactorial (given second in blue). In this order each column corresponds to one subfactorial: $~~~T(n,i)={\binom {n}{i}}~\cdot ~!i$
i n  0 1 2 3 4 5 6 7 8 0 1 1 1 0 2 1 0 1 3 1 0 3 2 4 1 0 6 8 9 5 1 0 10 20 45 44 6 1 0 15 40 135 264 265 7 1 0 21 70 315 924 1855 1854 8 1 0 28 112 630 2464 7420 14832 14833	i n  0 1 2 3 4 5 6 7 8 0 1⋅1 1 1⋅1 1⋅0 2 1⋅1 2⋅0 1⋅1 3 1⋅1 3⋅0 3⋅1 1⋅2 4 1⋅1 4⋅0 6⋅1 4⋅2 1⋅9 5 1⋅1 5⋅0 10⋅1 10⋅2 5⋅9 1⋅44 6 1⋅1 6⋅0 15⋅1 20⋅2 15⋅9 6⋅44 1⋅265 7 1⋅1 7⋅0 21⋅1 35⋅2 35⋅9 21⋅44 7⋅265 1⋅1854 8 1⋅1 8⋅0 28⋅1 56⋅2 70⋅9 56⋅44 28⋅265 8⋅1854 1⋅14833

Формулы

Числа в столбце 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\lceil {\frac {n!}{e}}\right\rfloor ,$

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

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

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

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

Числа D _{n ,0} /( n ! порождаются ) степенным рядом e ^{- г} /(1 - z ) ; соответственно,явную формулу для D _{n , m} можно получить следующим образом:

$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!}}.$

Это сразу означает, что

$D_{n,m}={n \choose m}D_{n-m,0}\;\;{\mbox{ and }}\;\;{\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. Для 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.

См. также

• Задача Обервольфаха — другая математическая задача, связанная с расположением посетителей за столами.
• Бытовая проблема , аналогичная проблема с частичными нарушениями

Ссылки

• Риордан, Джон , Введение в комбинаторный анализ , Нью-Йорк, Уайли, 1958, страницы 57, 58 и 65.
• Вайсштейн, Эрик В. «Частичные расстройства» . Математический мир .