Психическое расстройство

Количество возможных перестановок и неисправностей n элементов. п ! ( n факториал) - количество n -перестановок; ! n ( n субфакториал) - это количество нарушений - n -перестановок, при которых все n элементов меняют свои начальные места.

Таблица значений
${\ displaystyle 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 852016 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

В комбинаторной математике , А психоз является перестановкой из элементов набора , таким образом, что ни один элемент не появляется в исходном положении. Другими словами, расстройство - это перестановка, не имеющая фиксированных точек .

Количество расстройств набора размера п известно как subfactorial из п или в n - й психоз числа или п - го де Монмор числа . Обозначения для часто используемых субфакториалов включают! n, D _n , d _n или n ¡. ^[1]^[2]

Это можно показать! n равно ближайшему к n ! / e целому числу , где n ! обозначает факториал числа n, а e - число Эйлера .

Проблему подсчета неисправностей впервые рассмотрел Пьер Раймон де Монморт ^[3] в 1708 году; он решил ее в 1713 году, как и Николас Бернулли примерно в то же время.

Пример

Выделены 9 нарушений (из 24 вариантов).

Предположим, что профессор дал тест 4 студентам - A, B, C и D - и хочет, чтобы они оценили тесты друг друга. Конечно, ни один ученик не должен ставить оценку за свой тест. Сколькими способами профессор мог бы передать тесты студентам для выставления оценок, чтобы ни один студент не получил обратно свой тест? Из 24 возможных перестановок (4!) Для сдачи тестов,

ABCD ,	AB DC,	А CB D ,	CDB,	DBC,	A D C B,
BA CD ,	BADC ,	BCA D ,	BCDA ,	BDAC ,	BD C A,
КАБИНА D ,	CADB ,	C B A D ,	C B DA,	CDAB ,	CDBA ,
DABC ,	DA C B,	D B AC,	D BC A,	DCAB ,	DCBA .

неисправностей всего 9 (показаны выше синим курсивом). В каждой другой перестановке этого набора из 4-х членов по крайней мере один ученик получает обратно свой тест (выделенный жирным красным).

Другая версия проблемы возникает, когда мы спрашиваем количество способов, которыми n писем, адресованных разному человеку, могут быть помещены в n предварительно адресованных конвертов, чтобы ни одна буква не появлялась в конверте с правильным адресом.

Подсчет расстройств

Подсчет расстройств из набора составляет то , что известно как проблема Хет-проверку , ^[4] , в котором один считает количество способов , в которых п шляп (называют их час ₁ через час _п ) можно вернуть в п человек ( Р _{С 1} по P _n ), так что шляпа не вернется к своему владельцу.

Каждый человек может получить любую из n - 1 головных уборов, которые ему не принадлежат. Назовите ту шляпу, которую P ₁ получит h _i, и рассмотрите, что h _{i является} владельцем: P _i получает шляпу P ₁ , h ₁ или что-то другое. Соответственно, проблема распадается на два возможных случая:

P _i получает шляпу, отличную от h ₁ . Этот случай эквивалентен решению задачи с n - 1 человеком и n - 1 шляпами, потому что для каждого из n - 1 человека, кроме P _1, есть ровно одна шляпа из оставшихся n - 1 шляп, которые они могут не получить (для для любого P _j, кроме P _i , _{недопустимая} шляпа - h _j , а для P _i - h ₁ ).
P _i получает h ₁ . В этом случае задача сводится к n - 2 людям и n - 2 головам.

Для каждой из n - 1 шляп, которые может получить P ₁ , количество способов, которыми P ₂ ,…, P _n могут все получить шляпы, является суммой подсчетов для двух случаев. Это дает нам решение проблемы проверки шляпы: алгебраически сформулированное число! n неисправностей n -элементного множества равно

!n=(n-1)({!(n-1)}+{!(n-2)})

,

где! 0 = 1 и! 1 = 0. Первые несколько значений! п :

Число нарушений набора n -элементов (последовательность A000166 в OEIS ) для малых n
п	0	1	2	3	4	5	6	7	8	9	10	11	12	13
! п	1	0	1	2	9	44 год	265	1,854	14 833	133 496	1,334,961	14 684 570	176 214 841	2,290,792,932

Существуют также различные другие (эквивалентные) выражения для! n : ^[5]

!n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}},\quad n\geq 0,

!n=\left\lfloor {\frac {n!}{e}}\right\rceil =\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor ,\quad n\geq 1.

(где - ближайшая целочисленная функция ^[6], а - функция пола ) $\left\lfloor x\right\rceil$ $\left\lfloor x\right\rfloor$

Для любого целого $п \geq 1$ ,

!n={\begin{cases}\lfloor {\frac {n!}{e}}+r_{1}\rfloor ,&n{\text{ is odd}},\quad \ r_{1}\in [0,{\frac {1}{2}}],\\\lfloor {\frac {n!}{e}}+r_{2}\rfloor ,&n{\text{ is even}},\quad r_{2}\in [{\frac {1}{3}},1].\end{cases}}

Итак, для любого целого $n \geq 1$ и для любого действительного числа $r \in [1 / 3, 1 / 2]$ ,

!n=\left\lfloor {\frac {n!}{e}}+r\right\rfloor ,\quad \ n\geq 1,\quad r\in \left[{\frac {1}{3}},{\frac {1}{2}}\right].

Следовательно, при $e = 2,71828\dots$ , $1 / е \in [1 / 3, 1 / 2]$ , затем ^[7]

!n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor ,\quad \ n\geq 1,

!n=\left\lfloor (e+e^{-1})n!\right\rfloor -\lfloor en!\rfloor ,\quad n\geq 2,

!n=n!-\sum _{i=1}^{n}{n \choose i}\cdot {!(n-i)},\quad \ n\geq 1.

Также имеет место следующая рекуррентность: ^[8]

!n={\begin{cases}1&{\text{if }}n=0,\\n\left(!(n-1)\right)+(-1)^{n}&{\text{if }}n\geq 0.\end{cases}}

Вывод по принципу включения – исключения

Другой вывод (эквивалентной) формулы для числа неисправностей n -множества следующий. Ибо мы определяем набор перестановок n объектов, которые фиксируют k- й объект. Любое пересечение набора i этих множеств фиксирует конкретный набор i объектов и, следовательно, содержит перестановки. Есть такие коллекции, так что принцип включения-исключения дает $1\leq k\leq n$ $S_{k}$ $(n-i)!$ ${n \choose i}$

{\begin{aligned}|S_{1}\cup \cdots \cup S_{n}|&=\sum _{i}\left|S_{i}\right|-\sum _{i<j}\left|S_{i}\cap S_{j}\right|+\sum _{i<j<k}\left|S_{i}\cap S_{j}\cap S_{k}\right|+\cdots +(-1)^{n+1}\left|S_{1}\cap \cdots \cap S_{n}\right|\\&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{n+1}{n \choose n}0!\\&=\sum _{i=1}^{n}(-1)^{i+1}{n \choose i}(n-i)!\\&=n!\ \sum _{i=1}^{n}{(-1)^{i+1} \over i!}\end{aligned}}

а поскольку расстройство - это перестановка, которая не оставляет фиксированным ни один из n объектов, мы получаем

!n=n!-|S_{1}\cup \cdots \cup S_{n}|=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}.

Предел отношения расстройства к перестановке, когда n приближается к ∞

Из

!n=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}

а также

e^{x}=\sum _{i=0}^{\infty }{x^{i} \over i!}

немедленно получаем, используя x = −1:

\lim _{n\to \infty }{!n \over n!}={1 \over e}\approx 0.367879\ldots .

Это предел вероятности того, что случайно выбранная перестановка большого количества объектов является нарушением. Вероятность очень быстро сходится к этому пределу с увеличением n , вот почему! n - ближайшее к n ! / e целое число . Приведенный выше полулогарифмический график показывает, что граф неисправности отстает от графа перестановок почти на постоянное значение.

Более подробную информацию об этом вычислении и указанном выше ограничении можно найти в статье о статистике случайных перестановок .

Обобщения

Задача des rencontres спрашивает, сколько перестановок набора размера n имеют ровно k неподвижных точек.

Расстройства - это пример более широкого поля ограниченных перестановок. Например, проблема мужского пола спрашивает , сидят ли за столом n пар противоположного пола мужчина-женщина-мужчина-женщина -..., сколькими способами они могут сидеть так, чтобы никто не сидел рядом со своим партнером?

Более формально, учитывая множества A и S , и некоторые наборы U и V из сюръекции → S , мы часто хотим знать число пар функций ( ф , г ) такая , что F в U и г в V , и для всех a в A , f ( a ) ≠ g ( a ); другими словами, где для каждого f и g существует нарушение φ Sтакое, что f ( a ) = φ ( g ( a )).

Еще одно обобщение - следующая проблема:

Сколько существует анаграмм без фиксированных букв данного слова?

Например, для слова, состоящего только из двух разных букв, скажем, n букв A и m букв B, ответ, конечно, будет 1 или 0 в зависимости от того, n = m или нет, для единственного способа сформировать анаграмму без фиксированные буквы - это заменить все A на B , что возможно тогда и только тогда, когда n = m . В общем случае для слова из n ₁ букв X ₁ , n ₂ букв X ₂ , ..., n _r букв X _rоказывается (после правильного использования формулы включения-исключения ) ответ имеет вид:

\int _{0}^{\infty }P_{n_{1}}(x)P_{n_{2}}(x)\cdots P_{n_{r}}(x)e^{-x}\,dx,

для некоторой последовательности многочленов P _n , где P _n имеет степень n . Но приведенный выше ответ для случая r = 2 дает соотношение ортогональности, откуда P _n являются многочленами Лагерра (с точностью до знака, который легко определяется). ^[9]

\int _{0}^{\infty }(t-1)^{z}e^{-t}dt

в комплексной плоскости.

В частности, для классических расстройств

!n=\int _{0}^{\infty }(x-1)^{n}e^{-x}dx.

Вычислительная сложность

Это NP-полный, чтобы определить, содержит ли данная группа перестановок (описываемая данным набором перестановок, которые ее порождают) какие-либо нарушения. ^[10]

Внешние ссылки

Поищите психическое заболевание в Викисловаре, бесплатном словаре.

Баэз, Джон (2003). "Давайте психовать!" (PDF) .
Bogart, Kenneth P .; Дойл, Питер Г. (1985). «Несексистское решение проблемы мужчин и женщин» .
Дикау, Роберт М. "Диаграммы неисправностей" . Математические фигуры в системе Mathematica .
Хассани, Мехди. «Нарушения и приложения» . Журнал целочисленных последовательностей (JIS), том 6, выпуск 1, статья 03.1.2, 2003 г.
Weisstein, Эрик W . «Психология» . MathWorld - Интернет-ресурс Wolfram.

[1] Название «субфакторный» происходит от Уильяма Аллена Уитворта ; см. Cajori, Florian (2011), История математических обозначений: два тома в одном , Cosimo, Inc., стр. 77, ISBN 9781616405717.

[2] Рональд Л. Грэм, Дональд Э. Кнут, Орен Паташник, Конкретная математика (1994), Аддисон-Уэсли, Ридинг, Массачусетс. ISBN 0-201-55802-5

[3] де Монморт, PR (1708). Essay d'analyse sur les jeux de risk . Париж: Жак Кийо. Seconde Edition, Revue & augmentée de plusieurs Lettres . Париж: Жак Кийо. 1713.

[4] Сковилл, Ричард (1966). «Проблема проверки шляпы». Американский математический ежемесячник . 73 (3): 262–265. DOI : 10.2307 / 2315337 . JSTOR 2315337 .

[5] Хассани, М. "Нарушения и приложения". J. Целочисленная последовательность. 6, № 03.1.2, 1–8, 2003 г.

[Mathworld-NearestIntegerFunction-6] Вайсштейн, Эрик В. «Ближайшая целочисленная функция» . MathWorld .

[Mathworld-Subfactorial-7] Вайсштейн, Эрик В. «Субфакторный» . MathWorld .

[8] См. Примечания для (последовательность A000166 в OEIS ).

[9] Даже, S .; Дж. Гиллис (1976). «Расстройства и многочлены Лагерра» . Математические труды Кембриджского философского общества . 79 (1): 135–143. DOI : 10.1017 / S0305004100052154 . Проверено 27 декабря 2011 года .

[10] Lubiw, Анна (1981), "Некоторые NP-полные задачи , аналогичные изоморфизма графов", SIAM журнал по вычислениям , 10 (1): 11-21, DOI : 10,1137 / 0210002 , MR 0605600 . Бабай, Ласло (1995), "Группы автоморфизмов, изоморфизм, реконструкция", Справочник по комбинаторике, Vol. 1, 2 (PDF) , Амстердам: Elsevier, стр. 1447–1540, MR 1373683 , Удивительный результат Анны Любив утверждает, что следующая проблема является NP-полной: есть ли в данной группе перестановок элемент без неподвижных точек? .

[1]