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

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

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

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

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

Якщо

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}}$ .

Див. також

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

Примітки

Назва «субфакторіал» походить від ; див. (2011), , Cosimo, Inc., с. 77, ISBN , архів оригіналу за 25 квітня 2016, процитовано 6 червня 2015.
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison-Wesley, Reading MA.
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.

Посилання

Виведення формули кількості безладів трьома способами (англ.)
В.А. Вишенський, М.О. Перестюк. Комбінаторика: перші кроки. — Кам'янець-Подільський : Аксіома, 2010. — 324 с. — .(укр.)
Р. Стенлі. Перелічувальна комбінаторика. — М. : Мир, 1990. — С. 107-108.
(2003). (PDF). Архів оригіналу (PDF) за 30 вересня 2012. Процитовано 6 червня 2015.
Bogart, Kenneth P. and Doyle, Peter G. (1985). . Архів оригіналу за 20 липня 2008. Процитовано 6 червня 2015.
Dickau, Robert M. . Figures Using Mathematica. Архів оригіналу за 27 червня 2008. Процитовано 6 червня 2015.
Hassani, Mehdi. . Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003. Архів оригіналу за 4 червня 2008. Процитовано 6 червня 2015.
Weisstein, Eric W. Безлад(англ.) на сайті Wolfram MathWorld.

[1] Назва «субфакторіал» походить від ; див. (2011), , Cosimo, Inc., с. 77, ISBN , архів оригіналу за 25 квітня 2016, процитовано 6 червня 2015.

[2] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison-Wesley, Reading MA.

[3] 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.

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