www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

Приклади Редагувати

Перевірка робіт Редагувати

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

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

Задача про листи Редагувати

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

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

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

Кількість безладів Редагувати

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

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

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

і

де і

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

Див. також Редагувати

Примітки Редагувати

  1. Назва «субфакторіал» походить від William Allen Whitworth; див. Cajori, Florian (2011). . 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.

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V kombinatorici be zladom nazivayetsya perestanovka bez neruhomih tochok tobto zhodnij element ne zalishayetsya na pochatkovomu misci Chislo mozhlivih perestanovok ta bezladiv dlya n elementiv n n faktorial ce chislo n perestanovok n n subfaktorial ce chislo bezladiv n perestanovok v yakih usi n elementiv zminyuyut svoyi pochatkovi miscya Tablicya znachen n displaystyle n Perestanovka n displaystyle n Bezlad n displaystyle n n n displaystyle 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 94412Chislo bezladiv mnozhini z n elementiv zazvichaj poznachayetsya Dn dn abo n i nazivayetsya chislom bezladiv abo chislom Monmora Ci chisla uzagalnyuyutsya chislami sho vidpovidayut chislu zustrichej Funkciya subfaktoria l ne plutajte z faktorialom n stavit u vidpovidnist chislu n chislo n 1 Ne isnuye standartnogo poznachennya dlya subfaktorialu Inkoli poznachayut n zamist n 2 Zadacha pidrahunku chisla bezladiv bula upershe rozglyanuta P yerom de Monmorom 3 u 1708 vin rozv yazav yiyi u 1713 yak ce zrobiv Mikola I Bernulli priblizno v toj zhe chas Zmist 1 Prikladi 1 1 Perevirka robit 1 2 Zadacha pro listi 2 Kilkist bezladiv 3 Div takozh 4 Primitki 5 PosilannyaPrikladi RedaguvatiPerevirka robit Redaguvati Pripustimo sho profesor dav chotirom studentam nazvemo yih A B C i D kontrolnu a potim zaproponuvav yim pereviriti yiyi odin u odnogo Zvisno zhoden student ne povinen pereviryati svoyu kontrolnu Skilki u profesora variantiv rozpodilu kontrolnih v yakih zhodnomu studentu ne distanetsya svoya robota Z usih 24 h perestanovok 4 dlya povernennya robit nam pidhodyat tilki 9 bezladiv BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA U bud yakij inshij perestanovci cih 4 h elementiv prinajmni odin student otrimuye svoyu kontrolnu na perevirku Zadacha pro listi Redaguvati Obchislennya kilkosti bezladiv ye populyarnoyu zadacheyu v olimpiadnij matematici ru yaka zustrichayetsya v riznih formulyuvannyah takih yak zavdannya pro bezlad zavdannya pro listi zavdannya pro zustrichi i t d Yaksho n displaystyle n nbsp listiv vipadkovim chinom poklasti v n displaystyle n nbsp riznih konvertiv to yaka jmovirnist sho yakijs list potrapit v svij konvert Vidpovid dayetsya virazom 1 n n 1 1 e displaystyle 1 frac n n approx 1 frac 1 e nbsp Takim chinom vidpovid slabo zalezhit vid kilkosti listiv i konvertiv i priblizno dorivnyuye konstanti 1 1 e 0 63212 displaystyle 1 frac 1 e approx 0 63212 nbsp Kilkist bezladiv RedaguvatiKilkist vsih bezladiv poryadku n mozhe buti obchisleno za dopomogoyu principu vklyuchennya viklyuchennya i dayetsya virazom n n n 1 n 2 n 3 1 n n n k 0 n 1 k n k displaystyle 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 nbsp yake nazivayetsya subfaktorialom chisla n Kilkist bezladiv n d n displaystyle n d n nbsp zadovolnyaye rekursivnim spivvidnoshennyamd n n 1 d n 1 d n 2 displaystyle d n n 1 d n 1 d n 2 nbsp id n n d n 1 1 n displaystyle d n nd n 1 1 n nbsp de d 1 0 displaystyle d 1 0 nbsp i d 2 1 displaystyle d 2 1 nbsp Z oglyadu na te sho k 0 1 k 1 k 1 e displaystyle sum k 0 infty 1 k frac 1 k frac 1 e nbsp znachennya n displaystyle n nbsp zi zbilshennyam n displaystyle n nbsp vede sebe yak n e displaystyle frac n e nbsp Bilshe togo pri n gt 0 displaystyle n gt 0 nbsp jogo mozhna predstaviti yak rezultat okruglennya chisla n e displaystyle frac n e nbsp Div takozh RedaguvatiParadoks dniv narodzhennyaPrimitki Redaguvati Nazva subfaktorial pohodit vid William Allen Whitworth div Cajori Florian 2011 A History of Mathematical Notations Two Volumes in One Cosimo Inc s 77 ISBN 9781616405717 Arhiv originalu za 25 kvitnya 2016 Procitovano 6 chervnya 2015 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 amp augmentee de plusieurs Lettres Paris Jacque Quillau 1713 Posilannya RedaguvatiVivedennya formuli kilkosti bezladiv troma sposobami angl R Stenli Perelichuvalna kombinatorika M Mir 1990 S 107 108 Baez John 2003 Let s get deranged Arhiv originalu za 30 veresnya 2012 Procitovano 6 chervnya 2015 Bogart Kenneth P and Doyle Peter G 1985 Non sexist solution of the menage problem Arhiv originalu za 20 lipnya 2008 Procitovano 6 chervnya 2015 Dickau Robert M Derangement diagrams Figures UsingMathematica Arhiv originalu za 27 chervnya 2008 Procitovano 6 chervnya 2015 Hassani Mehdi Derangements and Applications Journal of Integer Sequences JIS Volume 6 Issue 1 Article 03 1 2 2003 Arhiv originalu za 4 chervnya 2008 Procitovano 6 chervnya 2015 Weisstein Eric W Derangement MathWorld A Wolfram Web Resource Arhiv originalu za 28 lipnya 2015 Procitovano 6 chervnya 2015 Otrimano z https uk wikipedia org w index php title Bezlad perestanovka amp oldid 39503730