Номера Rencontres

В комбинаторной математике , то число встречи являются треугольным массивом из целых чисел , которые перечисляют перестановки множества {1, ...,  п  } с указанным числом неподвижных точек : иными словами, частичными расстройства . ( Rencontre по-французски означает « столкновение» . По некоторым сведениям, проблема названа в честь пасьянса .) Для n  ≥ 0 и 0 ≤ k  ≤  n число rencontres 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  ≥ 1 это дает ближайшее целое число.

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

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

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

Числа D _{п , 0} / ( п !) Которые генерируются в степенной ряд е ^{- г} / (1 - г ) ; соответственно, явная формула для 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 - й момент этого распределения вероятностей является я - й момент распределения Пуассона с ожидаемым значением 1. ^[1] Для I  >  п , то я й момент меньше , чем у этого распределения Пуассона . В частности, для I  ≤  п , то я й момент это я й номер Bell , то есть количество разделов набора размера я .

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

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

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

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

Ссылки [ править ]

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