Число встреч (комбинаторика)

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В комбинаторной математике под числом встреч понимается число перестановок множества { 1, ..., n } с заданным числом неподвижных элементов. Для n ≥ 0 и 0 ≤ k ≤ n число встреч Dnk а – это число перестановок { 1, ..., n }, содержащих ровно k элементов, не изменивших положение в перестановке.

Например, если семь подарков было выдано семи различным лицам, но только два человека получили подарки, предназначенные именно им, в D7, 2 = 924 вариантах. В другом часто приводимом примере, в школе танцев с семью парами учеников, после перерыва на чай, участники случайно выбирают партнера для продолжения танцев, и снова в D7, 2 = 924 случаях 2 пары окажутся прежними.

Численные значения[править | править вики-текст]

Фрагмент таблицы числа встреч (последовательность A008290 в OEIS):

_n\!\!\diagdown\!\!^k 0 1 2 3 4 5 6 7
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

Формулы[править | править вики-текст]

Числа в первом столбце (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[{n! \over e}\right]

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

Доказательство просто, если уметь считать число беспорядков !n: выберем m фиксированных элементов из n, затем посчитаем число беспорядков оставшихся n − m элементов (это будет !n = {(n-m)!}\sum_{k=0}^{n-m} \frac{(-1)^k}{k!}.).

D_{n,m} = C_n^m D_{n-m,0} = \frac{n!}{m!} \sum_{k=0}^{n-m} \frac{(-1)^k}{k!}.[1]

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

 \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.[2] Для 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.

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

  1. Кофман А. - Введение в прикладную комбинаторику - 1975.
  2. Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.
  • John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
  • Weisstein, Eric W. Partial Derangements (англ.) на сайте Wolfram MathWorld.