Номера встреч

В комбинаторной математике числа 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 ):

Формулы

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

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

В более общем смысле для любого мы имеем ${\displaystyle k\geq 0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Задача Обервольфаха — другая математическая задача, связанная с расположением посетителей за столами.
• Problème des ménages , аналогичная проблема, связанная с частичными расстройствами.

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

1. Джим Питман, «Некоторые вероятностные аспекты разбиения множеств », American Mathematical Monthly , том 104, номер 3, март 1997 г., страницы 201–209.

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