Числа встреч: перестановки с фиксированными точками
Rencontres numbers
Числа реконтрів у комбінаториці: перестановки з фіксованою кількістю незмінних елементів. Формула Dn,k, приклади та пояснення. Математика, перестановки, дерaнжування.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
В комбинаторике числа Ранкуан (rencontres numbers) — это треугольный массив целых чисел, перечисляющий перестановки множества {1, 2, …, n} с заданным числом неподвижных точек, то есть частные беспорядки. (Слово "rencontre" во французском языке означает "встреча". По некоторым сведениям, задача получила название в честь карточной игры-пасьянса.) Для n ≥ 0 и 0 ≤ k ≤ n число Ранкуан Dn,k — это количество перестановок множества {1, 2, …, n}, имеющих ровно k неподвижных точек. Например, если семь подарков дарят семи разным людям, но только двум суждено получить свой подарок, то существует D7,2 = 924 способа, которыми это может произойти. Другой часто приводимый пример — танцевальная школа с 7 парами, где после перерыва участникам предлагается случайным образом выбрать себе партнёра для продолжения танцев, и тогда снова существует D7,2 = 924 возможностей, что 2 предыдущие пары случайно встретятся вновь.
In combinatorics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, , n } with specified numbers of fixed points: in other words, partial derangements. (Rencontre is French for encounter. By some accounts, the problem is named after a solitaire game.) For n ≥ 0 and 0 ≤ k ≤ n, the rencontres number Dn, k is the number of permutations of { 1, , n } that have exactly k fixed points. For example, if seven presents are given to seven different people, but only two are destined to get the right present, there are D7, 2 = 924 ways this could happen. Another often cited example is that of a dance school with 7 couples, where, after tea break the participants are told to randomly find a partner to continue, then once more there are D7, 2 = 924 possibilities that 2 previous couples meet again by chance.
Распределение вероятности
Сумма элементов в каждой строке таблицы в разделе "Численные значения" равна общему числу перестановок множества {1, 2, ..., n} и, следовательно, равна n!. Если разделить все элементы в n-й строке на n!, то получится распределение вероятностей числа неподвижных точек случайной перестановки множества {1, 2, ..., n}, выбранной равномерно. Вероятность того, что число неподвижных точек равно k, равна
The sum of the entries in each row for the table in "Numerical Values" is the total number of permutations of { 1, , n }, and is therefore n!. If one divides all the entries in the nth row by n!, one gets the probability distribution of the number of fixed points of a uniformly distributed random permutation of { 1, , n }. The probability that the number of fixed points is k is
Для n ≥ 1, математическое ожидание числа неподвижных точек равно 1 (это следует из линейности математического ожидания). В более общем случае, для i ≤ n, i-й момент этого распределения вероятностей равен i-му моменту распределения Пуассона с математическим ожиданием 1. Для i > n, i-й момент меньше, чем соответствующий момент распределения Пуассона. В частности, для i ≤ n, i-й момент является i-м числом Белла, то есть числом разбиений множества размера i.
For n ≥ 1, the expected number of fixed points is 1 (a fact that follows from linearity of expectation). More generally, for i ≤ n, the ith moment of this probability distribution is the ith moment of the Poisson distribution with expected value 1. For i > n, the ith moment is smaller than that of that Poisson distribution. Specifically, for i ≤ n, the ith moment is the ith Bell number, i. e. the number of partitions of a set of size i.