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

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

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

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

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

Фрагмент таблиці числа зустрічей (послідовність A008290 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)::

$_{n}\!\!\diagdown \!\!^{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[{n! \over 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\geq k$, де $B_{k}$ — числа Белла.

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

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

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

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

Більш того, для i ≤ n, i-ий момент цього розподілу є i-им моментом розподілу Пуассона зі значенням 1. Для 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.

Джерела

• John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• Weisstein, Eric W. Partial Derangements(англ.) на сайті Wolfram MathWorld.