Русская Википедия:Число встреч (комбинаторика)
В комбинаторной математике под числом встреч понимается число перестановок множества {1, ..., n} с заданным числом неподвижных элементов. Для n ≥ 0 и 0 ≤ k ≤ n число встреч Dn, k – это число перестановок {1, ..., n}, содержащих ровно k элементов, не изменивших положение в перестановке.
Например, если семь подарков было выдано семи различным лицам, но только два человека получили подарки, предназначенные именно им, в D7, 2 = 924 вариантах. В другом часто приводимом примере, в школе танцев с семью парами учеников, после перерыва на чай, участники случайно выбирают партнера для продолжения танцев, и снова в D7, 2 = 924 случаях 2 пары окажутся прежними.
Численные значения
Фрагмент таблицы числа встреч (Шаблон:OEIS):
| <math>_n\!\!\diagdown\!\!^k</math> | 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) показывают число беспорядков. Так,
- <math>D_{0,0} = 1,</math>
- <math>D_{1,0} = 0,</math>
- <math>D_{n+2,0} = (n + 1)(D_{n+1,0} + D_{n,0})</math>
для неотрицательного n. Оказывается
- <math>D_{n,0} = \left[{n! \over e}\right]</math>,
где дробь округляется вверх для четных n и вниз для нечетных, и для n ≥ 1, это соответствует ближайшему целому.
Доказательство просто, если уметь считать число беспорядков <math>!n</math>: выберем m фиксированных элементов из n, затем посчитаем число беспорядков оставшихся n − m элементов (это будет <math>!(n-m) = {(n-m)!}\sum_{k=0}^{n-m} \frac{(-1)^k}{k!}</math>).
- <math>D_{n,m} = C_n^m D_{n-m,0} = \frac{n!}{m!} \sum_{k=0}^{n-m} \frac{(-1)^k}{k!}.</math>[1]
Отсюда следует, что
- <math> \frac{D_{n, m}}{n!} \approx \frac{e^{-1}}{m!}</math>
для больших n и фиксированного m.
Распределение вероятности
Сумма элементов строки в вышеприведенной таблице является числом всех перестановок набора {1, ..., n}, и она равна n!. Если разделить все элементы строки n на n!, получим распределение вероятностей числа перестановок с неподвижными точками в равномерно распределенных случайных перестановках элементов {1, ..., n}. Вероятность того, что перестановка будет иметь k неподвижных точек, равна
- <math>{D_{n,k} \over n!}.</math>
Для n ≥ 1 математическое ожидание числа неподвижных точек равно 1.
Более того, для i ≤ n, i-й момент этого распределения является i-м моментом распределения Пуассона со значением 1.[2] Для i > n i-й момент меньше соответствующего момента распределения Пуассона. Точнее, для i ≤ n i-й момент является i-м числом Белла, т. е. число разбиений множества размера i.
Ограничение значений распределения вероятности
С возрастанием числа элементов мы получим
- <math>\lim_{n\to\infty} {D_{n,k} \over n!} = {e^{-1} \over k!}. </math>
Это как раз равно вероятности того, что случайная величина, распределенная по закону Пуассона с математическим ожиданием 1, равна k. Другими словами, при возрастании n распределение числа неподвижных точек у случайной перестановки n элементов приближается к распределению Пуассона с математическим ожиданием 1.
Примечания
Ссылки
- John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
- Шаблон:Mathworld
- ↑ Кофман А. — Введение в прикладную комбинаторику — 1975.
- ↑ Jim Pitman, "Some Probabilistic Aspects of Set Partitions", American Mathematical Monthly, volume 104, number 3, March 1997, pages 201–209.
