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

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

Таблиця значень
$n$	Перестановка, $n!$	Безлад, $!n$	${\frac {!n}{n!}}$
0	1 =1×100	1 =1×100	= 1
1	1 =1×100	0	= 0
2	2 =2×100	1 =1×100	= 0.5
3	6 =6×100	2 =2×100	≈0.33333 33333
4	24 =2.4×101	9 =9×100	= 0.375
5	120 =1.20×102	44 =4.4×101	≈0.36666 66667
6	720 =7.20×102	265 =2.65×102	≈0.36805 55556
7	5 040 ≈5.04×103	1 854 ≈1.85×103	≈0.36785 71429
8	40 320 ≈4.03×104	14 833 ≈1.48×104	≈0.36788 19444
9	362 880 ≈3.63×105	133 496 ≈1.33×105	≈0.36787 91887
10	3 628 800 ≈3.63×106	1 334 961 ≈1.33×106	≈0.36787 94643
11	39 916 800 ≈3.99×107	14 684 570 ≈1.47×107	≈0.36787 94392
12	479 001 600 ≈4.79×108	176 214 841 ≈1.76×108	≈0.36787 94413
13	6 227 020 800 ≈6.23×109	2 290 792 932 ≈2.29×109	≈0.36787 94412
14	87 178 291 200 ≈8.72×1010	32 071 101 049 ≈3.21×1010	≈0.36787 94412
15	1 307 674 368 000 ≈1.31×1012	481 066 515 734 ≈4.81×1011	≈0.36787 94412
16	20 922 789 888 000 ≈2.09×1013	7 697 064 251 745 ≈7.70×1012	≈0.36787 94412
17	355 687 428 096 000 ≈3.56×1014	130 850 092 279 664 ≈1.31×1014	≈0.36787 94412
18	6 402 373 705 728 000 ≈6.40×1015	2 355 301 661 033 953 ≈2.36×1015	≈0.36787 94412
19	121 645 100 408 832 000 ≈1.22×1017	44 750 731 559 645 106 ≈4.48×1016	≈0.36787 94412
20	2 432 902 008 176 640 000 ≈2.43×1018	895 014 631 192 902 121 ≈8.95×1017	≈0.36787 94412
21	51 090 942 171 709 440 000 ≈5.11×1019	18 795 307 255 050 944 540 ≈1.88×1019	≈0.36787 94412
22	1 124 000 727 777 607 680 000 ≈1.12×1021	413 496 759 611 120 779 881 ≈4.13×1020	≈0.36787 94412
23	25 852 016 738 884 976 640 000 ≈2.59×1022	9 510 425 471 055 777 937 262 ≈9.51×1021	≈0.36787 94412
24	620 448 401 733 239 439 360 000 ≈6.20×1023	228 250 211 305 338 670 494 289 ≈2.28×1023	≈0.36787 94412
25	15 511 210 043 330 985 984 000 000 ≈1.55×1025	5 706 255 282 633 466 762 357 224 ≈5.71×1024	≈0.36787 94412
26	403 291 461 126 605 635 584 000 000 ≈4.03×1026	148 362 637 348 470 135 821 287 825 ≈1.48×1026	≈0.36787 94412
27	10 888 869 450 418 352 160 768 000 000 ≈1.09×1028	4 005 791 208 408 693 667 174 771 274 ≈4.01×1027	≈0.36787 94412
28	304 888 344 611 713 860 501 504 000 000 ≈3.05×1029	112 162 153 835 443 422 680 893 595 673 ≈1.12×1029	≈0.36787 94412
29	8 841 761 993 739 701 954 543 616 000 000 ≈8.84×1030	3 252 702 461 227 859 257 745 914 274 516 ≈3.25×1030	≈0.36787 94412
30	265 252 859 812 191 058 636 308 480 000 000 ≈2.65×1032	97 581 073 836 835 777 732 377 428 235 481 ≈9.76×1031	≈0.36787 94412

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

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

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

Приклади

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

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

BADC, BCDA, BDAC,

CADB, CDAB, CDBA,

DABC, DCAB, DCBA.

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

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

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

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

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

$1-{\frac {!n}{n!}}\approx 1-{\frac {1}{e}}$

Таким чином, відповідь слабо залежить від кількості листів і конвертів і приблизно дорівнює константі $1-{\frac {1}{e}}\approx 0,63212$.

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

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

$!n=n!-{\frac {n!}{1!}}+{\frac {n!}{2!}}-{\frac {n!}{3!}}+\dots +(-1)^{n}{\frac {n!}{n!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}$

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

Кількість безладів $!n=d(n)$ задовольняє рекурсивним співвідношенням

$d(n)=(n-1)[d(n-1)+d(n-2)]$

і

$d(n)=nd(n-1)+(-1)^{n}$

де $d(1)=0$ і $d(2)=1$

З огляду на те, що $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}={\frac {1}{e}}$, значення $!n$ зі збільшенням $n$ веде себе як ${\frac {n!}{e}}$. Більше того, при $n>0$ його можна представити як результат округлення числа ${\frac {n!}{e}}$.

Див. також

• Парадокс днів народження

Посилання

• Виведення формули кількості безладів трьома способами (англ.)
• В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — ISBN 978-966-496-136-0.(укр.)
• Р. Стенлі. Перелічувальна комбінаторика. — М. : Мир, 1990. — С. 107-108.
• Baez, John (2003). Let's get deranged! (PDF). Архів оригіналу (PDF) за 30 вересня 2012. Процитовано 6 червня 2015.
• Bogart, Kenneth P. and Doyle, Peter G. (1985). Non-sexist solution of the ménage problem. Архів оригіналу за 20 липня 2008. Процитовано 6 червня 2015.
• Dickau, Robert M. Derangement diagrams. Figures Using Mathematica. Архів оригіналу за 27 червня 2008. Процитовано 6 червня 2015.
• Hassani, Mehdi. Derangements and Applications. Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003. Архів оригіналу за 4 червня 2008. Процитовано 6 червня 2015.
• Weisstein, Eric W. Безлад(англ.) на сайті Wolfram MathWorld.