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

В комбінаторній математиці під числом зустрічей розуміється число перестановок множини {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)::

${\displaystyle _{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) показують число безладів. Так,

${\displaystyle D_{0,0}=1,\!}$

${\displaystyle D_{1,0}=0,\!}$

${\displaystyle D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})\!}$

для невід'ємного n. Виявляється

${\displaystyle D_{n,0}=\left[{n! \over e}\right]}$

де дріб округляється вгору для парних n і вниз для непарних, і для n ≥ 1, це відповідає найближчому цілому. Доказ простий, якщо вміти рахувати число безладів: виберемо m фіксованих елементів з n, потім обчислимо число безладів для n — m елементів, які залишились. Це буде:

${\displaystyle !n={(n-m)!}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.}$).

${\displaystyle D_{n,m}=C_{n}^{m}D_{n-m,0}={\frac {n!}{m!}}\sum _{k=0}^{n-m}{\frac {(-1)^{k}}{k!}}.}$^[1]

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \lim _{n\to \infty }{D_{n,k} \over n!}={e^{-1} \over k!}.}$

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

Примітки

1. Кофман А. — Введение в прикладную комбинаторику — 1975.

Джерела

• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — ISBN 978-966-496-136-0.(укр.)
• John Riordan, An Introduction to Combinatorial Analysis, New York, Wiley, 1958, pages 57, 58, and 65.
• Weisstein, Eric W. Partial Derangements(англ.) на сайті Wolfram MathWorld.