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

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

Формули

Числа в першому стовпці (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!}}.

[1]

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

{\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.

Примітки

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

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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