Derangement

File:N! v !n.svg

Number of possible permutations and derangements of n elements. n! (n factorial) is the number of n-permutations; !n (n subfactorial) is the number of derangements — n-permutations where all of the n elements change their initial places.

Table of values
$n$	Permutations, $n!$	Derangements, $!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

조합론적(combinatorial) 수학(mathematics)에서, 교란(derangement)은, 어떤 원소도 그것의 원래 위치에 나타나지 않음을 만족하는, 집합(set)의 원소들의 순열(permutation)입니다. 달리 말해서, 교란은 고정 점(fixed points)을 가지지 않는 순열입니다.

크기 n의 집합에 대한 교란의 숫자는 n의 서브팩토리얼(subfactorial) 또는 n-번째 교란 숫자(derangement number) 또는 n-번째 드 몽모르 숫자(de Montmort number)로 알려져 있습니다. 공통 사용에서 서브팩토리얼에 대해 표기법은 !n, D_n, d_n, 또는 n¡를 포함합니다.^[1]^[2]

우리는 !n이 n!/e에 가장 가까운 정수와 같음을 보일 수 있으며, 여기서 n!은 n의 팩토리얼(factorial)을 나타내고 e는 오일러의 숫자(Euler's Number)입니다.

교란을 세는 것의 문제는 1708년 피에르 레몽 드 몽모르(Pierre Raymond de Montmort)에 의해 처음으로 고려되었습니다;^[3] 그는 1713년에 그것을 해결했으며, 거의 같은 시기에 니콜라우스 베르누이(Nicholas Bernoulli)도 그것을 풀었습니다.

Example

File:Derangement4.png

The 9 derangements (from 24 permutations) are highlighted

선생님이 4 명의 학생– A, B, C, D –에게 테스트를 출제했고 서로의 테스트에 점수를 매기는 것을 가정해 보십시오. 물론, 어떤 학생도 자신의 테스트를 점수를 매겨서는 안됩니다. 선생님이 점수를 매기는 것에 대해 학생들에게 테스트를 돌려줄 때, 어떤 학생도 그 자신의 테스트를 되돌려받지 않는 것을 만족하는, 방법은 몇 가지일까요? 테스트를 되돌려주는 24 가지 가능한 순열(24 possible permutations) (4!) 중에서:

ABCD,	ABDC,	ACBD,	ACDB,	ADBC,	ADCB,
BACD,	BADC,	BCAD,	BCDA,	BDAC,	BDCA,
CABD,	CADB,	CBAD,	CBDA,	CDAB,	CDBA,
DABC,	DACB,	DBAC,	DBCA,	DCAB,	DCBA.

(위의 파란색 이탤릭체로 표시된) 오직 9개의 교란이 있습니다. 이들 4-명 집합의 모든 각 다른 순열에서, 적어도 한 학생은 (굵은 빨간색으로 표시된) 자신의 테스트를 되돌려 받습니다.

문제의 또 다른 버전은, 서로 다른 사람에 대한 주소가 미리-적힌 n 개의 봉투에 해당하는 사람들의 편지를 봉투에 1개씩 넣었을 때, 봉투와 편지에 같은 주소가 적혀있지 않는, n 편지를 넣는 방법에 대해 물을 때 발생합니다.

Counting derangements

집합의 교란을 계산하는 것은 모자-검사 문제(hat-check problem)로 알려진 것이며,^[4] 이것에서, 우리는 n 모자 (h₁부터 h_n까지 부름)는 어떤 모자도 소유자에게 돌려주지 않는 것을 만족하는 n 명 (P₁부터 P_n까지)에게 돌려줄 수 있는 방법의 숫자를 고려합니다.

각 개인은 자신의 것이 아닌 n − 1의 임의의 모자를 받을 수 있습니다. P₁이 받는 모자를 h_i라고 부르고 h_i의 소유자를 생각해 보십니다: P_i는 P₁의 모자, h₁을 받거나 다른 모자를 받습니다. 그것에 따라서, 문제는 두 가지 가능한 경우로 나뉩니다:

P_i는 h₁ 이외의 모자를 받습니다. 이 경우는 n − 1 명과 n − 1 모자를 갖는 문제를 해결하는 것과 동일한데 왜냐하면 P₁ 이외에 n − 1 명의 각 사람에 대해 그들이 돌려받지 않아야 하는 남아있는 n − 1 모자 중에서 정확히 하나의 모자가 있기 때문입니다 (P_i 이외에 임의의 P_j에 대해, 받을 수 없는 모자는 h_j이지만, P_i에 대해 그것은 h₁입니다).
P_i는 h₁을 받습니다. 이 경우에서 문제는 n − 2 명과 n − 2 모자로 줄어듭니다.

P₁이 받을 수 있는 n − 1 모자 각각에 대해, P₂, … ,P_n이 모두 모자를 받을 수 있는 방법의 숫자는 두 경우에 대한 셈의 합입니다. 이것은 우리에게 모자-검사 문제에 대한 해결책을 제공합니다; 대수적으로 말하면, n-원소 집합의 교란의 숫자 !n는 다음입니다:

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

,

여기서 !0 = 1 및 !1 = 0입니다. !n의 처음 몇 개의 값은 다음입니다:

작은 n에 대해 n-원소 집합의 교란의 숫자 (OEIS에서 수열 A000166)
n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
!n	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.

(여기서 $\left\lfloor x\right\rceil$ 는 가장-가까운 정수 함수(nearest integer function)이고^[6] $\left\lfloor x\right\rfloor$ 는 바닥 함수(floor function)입니다)

임의의 정수 $n \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 / e \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=n\left(!(n-1)\right)+(-1)^{n},\quad \ n\geq 1.

Derivation by inclusion–exclusion principle

n-집합의 교란의 숫자에 대해 (동등한) 공식의 또 다른 유도는 다음 처럼입니다. $1\leq k\leq n$ 에 대해, 우리는 $S_{k}$ 를 k-번째 대상을 고정하는 n 대상의 순열의 집합으로 정의합니다. 이들 집합의 i의 모듬의 임의의 교집합은 i 대상의 특정 집합을 고정하고 따라서 $(n-i)!$ 순열을 포함합니다. ${n \choose i}$ 그러한 모음이 있으므로, 포함–제외 원리(inclusion–exclusion principle)는 다음을 산출합니다:

{\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!}}.

Limit of ratio of derangement to permutation as n approaches ∞

다음과

!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.3679\ldots .

이것은 대상의 많은 숫자의 무작위로 선택된 순열이 교란인 확률(probability)의 극한입니다. 확률은 n이 증가함에 따라 매우 빠르게 이 극한에 수렴하며, 이것이 바로 !n이 n!/e에 가장 가까운 정수인 이유입니다. 위의 세미-로그(semi-log) 그래프가 교란 그래프가 순열 그래프보다 거의 상수 값만큼 뒤처짐을 보여줍니다.

이 계산과 위의 극한에 대한 자세한 내용은 무작위 순열의 통계(statistics of random permutations)에 대한 기사에서 찾을 수 있습니다.

Generalizations

마주침의 문제(problème des rencontres)는 정확히 k 고정된 점을 갖는 크기-n 집합의 순열의 숫자가 얼마나 많은지를 묻습니다.

교란은 제한된 순열의 더 넓은 분야의 예제입니다. 예를 들어, 상-차림 문제(ménage problem)는 만약 n 이성-커플이 테이블 주위로 남자-여자-남자-여자-... 앉아 있으면, 그 또는 그녀의 파트너 옆에 아무도 앉지 않도록 그들이 앉을 수 있는 몇 가지 방법이 있는지?를 묻는 것입니다.

보다 공식적으로, 집합 A와 S, 및 전사(surjection) A → S의 일부 집합 U와 V가 주어지면, 우리는 종종 f가 U에 있고 g가 V에 있고, A에서 모든 a에 대해, f(a) ≠ g(a)를 만족하는 함수의 쌍 (f, g)의 숫자를 알고 싶어합니다; 다른 말로, 여기서 각 f와 g에 대해, f(a) = φ(g(a))를 만족하는 S의 교란 φ가 존재합니다.

또 다른 일반화는 다음 문제입니다:

주어진 단어의 고정된 문자가 없는 애너그램은 몇 개 있습니까?

예를 들어, 오직 두 다른 문자, 말하자면 n 문자 A와 m 문자 B로 이루어진 단어에 대해, 그 대답은, 물론, n = m인지 아니지 여부에 따라 1 또는 0이며, 고정된 문자없이 애너그램을 형성하는 유일한 방법은 모든 A를 B로 교환하는 것이며, 이것이 가능한 것과 n = m이 같은 것은 필요충분 조건입니다. 일반적인 경우에 대해, n₁ 문자 X₁, n₂ 문자 X₂, ..., n_r 문자 X_r을 가진 단어에 대해, (포함-제외(inclusion-exclusion) 공식의 적절한 사용 후) 그 답은 다항식 P_n의 특정 수열에 대해 다음 형식을 가짐을 밝혀집니다:

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

여기서 P_n은 차수 n을 가집니다. 그러나 r = 2 경우에 대해 위의 답은 직교 관계를 제공하며, 그것으로부터 P_n'은 (쉽게 결정되는 부호까지(up to)) 라게르 다항식(Laguerre polynomials)입니다.^[9]

File:Complex plot for derangement real between -1 to 11.png

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

in the complex plane.

특히, 고전적 교란에 대해

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

Computational complexity

주어진 순열 그룹(permutation group) (그것을 생성하는 순열의 주어진 집합에 의해 설명됨)이 임의의 교란을 포함하는지 여부를 결정하는 것은 NP-완전(NP-complete)입니다.^[10]

References

^ The name "subfactorial" originates with William Allen Whitworth; see Cajori, Florian (2011), A History of Mathematical Notations: Two Volumes in One, Cosimo, Inc., p. 77, ISBN 9781616405717.
^ 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.
^ Scoville, Richard (1966). "The Hat-Check Problem". American Mathematical Monthly. 73 (3): 262–265. doi:10.2307/2315337. JSTOR 2315337.
^ Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1–8, 2003
^ Weisstein, Eric W. "Nearest Integer Function". MathWorld.
^ Weisstein, Eric W. "Subfactorial". MathWorld.
^ See the notes for (OEIS에서 수열 A000166).
^ Even, S.; J. Gillis (1976). "Derangements and Laguerre polynomials". Mathematical Proceedings of the Cambridge Philosophical Society. 79 (1): 135–143. doi:10.1017/S0305004100052154. Retrieved 27 December 2011.
^ Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600. Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", Handbook of combinatorics, Vol. 1, 2 (PDF), Amsterdam: Elsevier, pp. 1447–1540, MR 1373683, A surprising result of Anna Lubiw asserts that the following problem is NP-complete: Does a given permutation group have a fixed-point-free element?.

External links

Baez, John (2003). "Let's get deranged!" (PDF).
Bogart, Kenneth P.; Doyle, Peter G. (1985). "Non-sexist solution of the ménage problem".
Dickau, Robert M. "Derangement diagrams". Mathematical Figures Using Mathematica.
Hassani, Mehdi. "Derangements and Applications". Journal of Integer Sequences (JIS), Volume 6, Issue 1, Article 03.1.2, 2003.
Weisstein, Eric W. "Derangement". MathWorld–A Wolfram Web Resource.

[1] The name "subfactorial" originates with William Allen Whitworth; see Cajori, Florian (2011), A History of Mathematical Notations: Two Volumes in One, Cosimo, Inc., p. 77, ISBN 9781616405717.

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

[4] Scoville, Richard (1966). "The Hat-Check Problem". American Mathematical Monthly. 73 (3): 262–265. doi:10.2307/2315337. JSTOR 2315337.

[5] Hassani, M. "Derangements and Applications." J. Integer Seq. 6, No. 03.1.2, 1–8, 2003

[Mathworld-NearestIntegerFunction-6] Weisstein, Eric W. "Nearest Integer Function". MathWorld.

[Mathworld-Subfactorial-7] Weisstein, Eric W. "Subfactorial". MathWorld.

[8] See the notes for (OEIS에서 수열 A000166).

[9] Even, S.; J. Gillis (1976). "Derangements and Laguerre polynomials". Mathematical Proceedings of the Cambridge Philosophical Society. 79 (1): 135–143. doi:10.1017/S0305004100052154. Retrieved 27 December 2011.

[10] Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600. Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", Handbook of combinatorics, Vol. 1, 2 (PDF), Amsterdam: Elsevier, pp. 1447–1540, MR 1373683, A surprising result of Anna Lubiw asserts that the following problem is NP-complete: Does a given permutation group have a fixed-point-free element?.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]