Номера 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 предыдущие пары встретятся снова. случайно.

СОДЕРЖАНИЕ

• 1 Числовые значения
• 2 формулы
• 3 Распределение вероятностей
  • 3.1 Предельное распределение вероятностей
• 4 См. Также
• 5 ссылки

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

Вот начало этого массива (последовательность 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 ^ {nm}] {\ frac {e ^ {- z}} {1-z}} = {\ frac {n!} {m!}} \ sum _ {k = 0} ^ {nm} {\ frac {(-1) ^ {k}} {k!}}.}.}$

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

${\ displaystyle D_ {n, m} = {n \ choose m} D_ {nm, 0} \; \; {\ t_dv {and}} \; \; {\ frac {D_ {n, m}} {n !}} \ приблизительно {\ frac {e ^ {- 1}} {м!}}}$

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

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

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

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

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

В более общем смысле, для I  ≤  п, то я й момент этого распределения вероятностей является я - й момента распределения Пуассона с ожидаемым значением 1. Для I  gt;  п, то я й момент меньше, чем у этого распределения Пуассона. В частности, для I  ≤  п, то я й момент это я й номер Bell, то есть количество разделов набора размера я.

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

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

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

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

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

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

использованная литература

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