Число зустрічей (комбінаторика)

В комбінаторній математиці під числом зустрічей розуміється число перестановок множини {1, …, n} з заданим числом нерухомих елементів.

Для чисел n і k (n ≥ 0 і 0 ≤ k ≤ n), які позначають кількість всіх та кількість нерухомих елементів відповідно, число зустрічей D_n, k — це число всіх перестановок {1, …, n}, які містять рівно k елементів, що не змінили положення в перестановці.

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

Чисельні значення

Фрагмент таблиці числа зустрічей (Шаблон:OEIS)::

${}_n╲{}^k$	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

Формули

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

де дріб округляється вгору для парних n і вниз для непарних, і для n ≥ 1, це відповідає найближчому цілому. Доказ простий, якщо вміти рахувати число безладів: виберемо 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!}.$

Звідси випливає, що

$\frac{D_{n,m}}{n!}\approx \frac{e^{-1}}{m!}$

для великих n і фіксованого m.

$\sum _{m=0}^n{m}^k{D}_{n,m}=B_{k}n!$ для $n\ge k$, де $B_k$ — числа Белла.

Розподіл ймовірності

Сума елементів рядка в вищенаведеної таблиці є числом всіх перестановок набору {1, …, n}, і вона дорівнює n!. Якщо розділити всі елементи рядка n на n!, отримаємо розподіл ймовірностей числа перестановок з нерухомими точками в рівномірно розподілених випадкових перестановках елементів {1, …, n}. Ймовірність того, що перестановка матиме k нерухомих точок, дорівнює

$\frac{D_{n,k}}{n!}.$

Для n ≥ 1, математичне сподівання числа нерухомих точок дорівнює 1.

Більш того, для i ≤ n, i-ий момент цього розподілу є i-им моментом розподілу Пуассона зі значенням 1. Для i>n i-ий момент менше відповідного моменту розподілу Пуассона. Точніше, для i ≤ n i-ий момент є i-им числом Белла, тобто число всіх можливих розбиттів множини розміру i.

Обмеження значень розподілу ймовірностей

Із зростанням числа елементів ми отримаємо

$\underset{n\to \mathrm{\infty }}{\lim }\frac{D_{n,k}}{n!}=\frac{e^{-1}}{k!}.$

Це є ймовірністю того, що випадкова величина, розподілена за законом Пуассона з математичним очікуванням 1, дорівнює k. Іншими словами, при зростанні n розподіл ймовірності числа перестановок з фіксованими точками серед випадкових перестановок множини з n елементів наближається до розподілу Пуассона з математичним очікуванням 1.

Джерела

• Шаблон:Вишенський.Перестюк.Комбінаторика
• John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• Шаблон:Mathworld