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

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

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

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

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

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

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

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

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

).

[1]

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

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

для , де - числа Белла.

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

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

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

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

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

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

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

Примітки

  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.