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

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

Число безладів множини з n елементів, зазвичай позначається D_n, d_n, або !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-х елементів, принаймні один студент отримує свою контрольну на перевірку.

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

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

Якщо

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) = n d (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}$ .

Див. також

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

Примітки

Шаблон:Reflist

Посилання

↑ Назва «субфакторіал» походить від William Allen Whitworth; див. Шаблон:Citation.
↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison-Wesley, Reading MA. ISBN 0-201-55802-5
↑ 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.

[1] Назва «субфакторіал» походить від William Allen Whitworth; див. Шаблон:Citation.

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

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

[1]

[2]

[3]

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

Зміст

Приклади

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

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

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

Див. також

Примітки

Посилання

Навігаційне меню

Таблиця значень
$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

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

Приклади

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

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

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

Див. також

Примітки

Посилання

Навігаційне меню

Пошук