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

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

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

Вот начало этого массива (последовательность 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 \выберите k}\cdot D_{nk,0}.}$

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

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

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

Это сразу подразумевает, что

${\displaystyle D_{n,m}={n \выберите m}D_{nm,0}\;\;{\mbox{ и }}\;\;{\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 , аналогичная проблема, связанная с частичными расстройствами.

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