Число встреч (также число частичных беспорядков) — в комбинаторной математике число перестановок множества с заданным числом неподвижных элементов.
Для и число встреч (или ) — это точное количество перестановок , содержащих ровно элементов, не изменивших свою исходную позицию в перестановке. Случай соответствует полным беспорядкам (перестановкам без неподвижных точек).
Исторически эта концепция восходит к задаче анализа карточной азартной игры, впервые сформулированной Пьером Ремоном де Монмором в 1708 году («задача о совпадениях» или «задача о встречах»).
Примеры Классический пример задачи на числа встреч: если семь подарков было выдано семи различным лицам, но только два человека получили подарки, предназначенные именно им, это могло произойти в вариантах.
В другом часто приводимом примере, в школе танцев с семью парами учеников, после перерыва участники случайно выбирают партнера для продолжения танцев. Вероятностное пространство всех возможных исходов охватывает все перестановки, и ровно в случаях две пары окажутся прежними.
Численные значения Фрагмент таблицы чисел встреч (последовательность ):
0 1 2 3 4 5 6 7 8 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 8 14833 14832 7420 2464 630 112 28 0 1
Сумма элементов в каждой -й строке строго равна общему количеству перестановок элементов множества, то есть .
Формулы и свойства
Связь с беспорядками Числа в первом столбце () показывают число беспорядков. Таким образом, выполняются следующие базовые соотношения:
для любого неотрицательного .
Известно, что количество полных беспорядков выражается явной формулой через факториал и основание натурального логарифма: , где дробь округляется вверх для чётных и вниз для нечётных. Для всех это значение строго совпадает с ближайшим целым числом к .
Явные формулы Для вычисления общего значения применяется комбинаторное правило: необходимо выбрать фиксированных (неподвижных) элементов из возможных, а затем умножить это число на количество беспорядков для оставшихся элементов. Количество способов выбрать элементов из задаётся биномиальным коэффициентом . Количество беспорядков для оставшихся элементов равно субфакториалу .
Тогда формула принимает вид: Кофман А. — Введение в прикладную комбинаторику — 1975.
Отсюда выводится следующее асимптотическое приближение:
для достаточно больших и фиксированного значения .
Производящие функции В терминах экспоненциальных производящих функций последовательность чисел встреч может быть выражена единой формулой. Бивариантная (от двух переменных) производящая функция для имеет вид:
Распределение вероятности
Если случайным образом выбрать перестановку элементов (считая, что все перестановок равновероятны), то количество неподвижных точек в ней является случайной величиной. Деление каждого элемента в строке таблицы чисел встреч на задаёт распределение вероятностей числа неподвижных точек в случайной перестановке.
Вероятность того, что случайно выбранная перестановка будет иметь ровно неподвижных точек, равна:
Для математическое ожидание числа неподвижных точек всегда строго равно 1, независимо от длины перестановки .
Более того, для , -й момент этого распределения в точности равен -му моменту распределения Пуассона с параметром . Для , -й момент строго меньше соответствующего момента распределения Пуассона. Говоря точнее, для -й момент является -м числом Белла, которое задаёт общее число разбиений множества размера .
Ограничение значений распределения вероятности С возрастанием числа элементов распределение числа неподвижных точек асимптотически стремится к пуассоновскому. Предел вероятности равен:
Полученное значение строго совпадает с вероятностью того, что случайная величина, распределенная по закону Пуассона с математическим ожиданием , примет значение . Другими словами, при возрастании распределение числа неподвижных точек у случайной перестановки элементов по вероятности сходится к распределению Пуассона.
Примечания
Литература
Ссылки
Категория:Комбинаторика Категория:Перестановки Категория:Распределения вероятностей