Безлад (перестановка)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Число можливих перестановок та безладів для n елементів. n! (n факторіал) — це число n-перестановок; !n (n субфакторіал) — це число безладів — n-перестановок, в яких усі n елементів змінюють свої початкові місця.

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

Число безладів множини з n елементів, зазвичай позначається Dn, dn, або !n, і називається «числом безладів» або «числом Монмора». (Ці числа узагальнюються числами, що відповідають числу зустрічей.) Функція субфакторіа́л (не плутайте з факторіалом n!) ставить у відповідність числу n число !n.[1] Не існує стандартного позначення для субфакторіалу. Інколи позначають n¡ замість !n.[2]

Задача підрахунку числа безладів була уперше розглянута П'єром де Монмором[3] у 1708; він розв'язав її у 1713, як це зробив Микола I Бернуллі приблизно в той же час.

Приклади

[ред. | ред. код]

Перевірка робіт

[ред. | ред. код]

Припустимо, що професор дав чотирьом студентам (назвемо їх A, B, C і D) контрольну, а потім запропонував їм перевірити її один у одного. Звісно, жоден студент не повинен перевіряти свою контрольну. Скільки у професора варіантів розподілу контрольних, в яких жодному студенту не дістанеться своя робота? З усіх 24-х перестановок (4!) для повернення робіт, нам підходять тільки 9 безладів:

BADC, BCDA, BDAC,
CADB, CDAB, CDBA,
DABC, DCAB, DCBA.

У будь-який інший перестановці цих 4-х елементів, принаймні один студент отримує свою контрольну на перевірку.

Задача про листи

[ред. | ред. код]

Обчислення кількості безладів є популярною задачею в олімпіадній математиці[ru], яка зустрічається в різних формулюваннях таких як завдання про безлад, завдання про листи, завдання про зустрічі і т. д.

Якщо листів випадковим чином покласти в різних конвертів, то яка ймовірність, що якийсь лист потрапить в свій конверт?

Відповідь дається виразом

Таким чином, відповідь слабо залежить від кількості листів і конвертів і приблизно дорівнює константі .

Кількість безладів

[ред. | ред. код]

Кількість всіх безладів порядку n може бути обчислено за допомогою принципу включення-виключення і дається виразом:

яке називається субфакторіалом числа n.

Кількість безладів задовольняє рекурсивним співвідношенням

і

де і

З огляду на те, що , значення зі збільшенням веде себе як . Більше того, при його можна представити як результат округлення числа .

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Назва «субфакторіал» походить від William Allen Whitworth; див. Cajori, Florian (2011), A History of Mathematical Notations: Two Volumes in One, Cosimo, Inc., с. 77, ISBN 9781616405717, архів оригіналу за 25 квітня 2016, процитовано 6 червня 2015.
  2. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison-Wesley, Reading MA. ISBN 0-201-55802-5
  3. de Montmort, P. R. (1708). Essay d'analyse sur les jeux de hazard. Paris: Jacque Quillau. Seconde Edition, Revue & augmentée de plusieurs Lettres. Paris: Jacque Quillau. 1713.

Посилання

[ред. | ред. код]