Derangement
Table of values | |||
---|---|---|---|
Permutations, | Derangements, | ||
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 94412 |
조합론적(combinatorial) 수학(mathematics)에서, 교란(derangement)은, 어떤 원소도 그것의 원래 위치에 나타나지 않음을 만족하는, 집합(set)의 원소들의 순열(permutation)입니다. 달리 말해서, 교란은 고정 점(fixed points)을 가지지 않는 순열입니다.
크기 n의 집합에 대한 교란의 숫자는 n의 서브팩토리얼(subfactorial) 또는 n-번째 교란 숫자(derangement number) 또는 n-번째 드 몽모르 숫자(de Montmort number)로 알려져 있습니다. 공통 사용에서 서브팩토리얼에 대해 표기법은 !n, Dn, dn, 또는 n¡를 포함합니다.[1][2]
우리는 !n이 n!/e에 가장 가까운 정수와 같음을 보일 수 있으며, 여기서 n!은 n의 팩토리얼(factorial)을 나타내고 e는 오일러의 숫자(Euler's Number)입니다.
교란을 세는 것의 문제는 1708년 피에르 레몽 드 몽모르(Pierre Raymond de Montmort)에 의해 처음으로 고려되었습니다;[3] 그는 1713년에 그것을 해결했으며, 거의 같은 시기에 니콜라우스 베르누이(Nicholas Bernoulli)도 그것을 풀었습니다.
Example
선생님이 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 모자 (h1부터 hn까지 부름)는 어떤 모자도 소유자에게 돌려주지 않는 것을 만족하는 n 명 (P1부터 Pn까지)에게 돌려줄 수 있는 방법의 숫자를 고려합니다.
각 개인은 자신의 것이 아닌 n − 1의 임의의 모자를 받을 수 있습니다. P1이 받는 모자를 hi라고 부르고 hi의 소유자를 생각해 보십니다: Pi는 P1의 모자, h1을 받거나 다른 모자를 받습니다. 그것에 따라서, 문제는 두 가지 가능한 경우로 나뉩니다:
- Pi는 h1 이외의 모자를 받습니다. 이 경우는 n − 1 명과 n − 1 모자를 갖는 문제를 해결하는 것과 동일한데 왜냐하면 P1 이외에 n − 1 명의 각 사람에 대해 그들이 돌려받지 않아야 하는 남아있는 n − 1 모자 중에서 정확히 하나의 모자가 있기 때문입니다 (Pi 이외에 임의의 Pj에 대해, 받을 수 없는 모자는 hj이지만, Pi에 대해 그것은 h1입니다).
- Pi는 h1을 받습니다. 이 경우에서 문제는 n − 2 명과 n − 2 모자로 줄어듭니다.
P1이 받을 수 있는 n − 1 모자 각각에 대해, P2, … ,Pn이 모두 모자를 받을 수 있는 방법의 숫자는 두 경우에 대한 셈의 합입니다. 이것은 우리에게 모자-검사 문제에 대한 해결책을 제공합니다; 대수적으로 말하면, n-원소 집합의 교란의 숫자 !n는 다음입니다:
- ,
여기서 !0 = 1 및 !1 = 0입니다. !n의 처음 몇 개의 값은 다음입니다:
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]
(여기서 는 가장-가까운 정수 함수(nearest integer function)이고[6] 는 바닥 함수(floor function)입니다)
임의의 정수 n ≥ 1에 대해,
따라서, 임의의 정수 n ≥ 1에 대해, 및 임의의 실수 r ∈ [1/3, 1/2]에 대해,
그러므로, e = 2.71828…, 1/e ∈ [1/3, 1/2]일 때, 다음입니다:[7]
다음 반복 상등은 역시 유지됩니다:[8]
Derivation by inclusion–exclusion principle
n-집합의 교란의 숫자에 대해 (동등한) 공식의 또 다른 유도는 다음 처럼입니다. 에 대해, 우리는 를 k-번째 대상을 고정하는 n 대상의 순열의 집합으로 정의합니다. 이들 집합의 i의 모듬의 임의의 교집합은 i 대상의 특정 집합을 고정하고 따라서 순열을 포함합니다. 그러한 모음이 있으므로, 포함–제외 원리(inclusion–exclusion principle)는 다음을 산출합니다:
그리고 교란은 고정된 n 대상의 어떤 것 없이 남겨두는 순열이기 때문에, 우리는 다음을 얻습니다:
Limit of ratio of derangement to permutation as n approaches ∞
다음과
다음으로부터
우리는 즉시 x = −1을 사용하여 다음을 얻습니다:
이것은 대상의 많은 숫자의 무작위로 선택된 순열이 교란인 확률(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이 같은 것은 필요충분 조건입니다. 일반적인 경우에 대해, n1 문자 X1, n2 문자 X2, ..., nr 문자 Xr을 가진 단어에 대해, (포함-제외(inclusion-exclusion) 공식의 적절한 사용 후) 그 답은 다항식 Pn의 특정 수열에 대해 다음 형식을 가짐을 밝혀집니다:
여기서 Pn은 차수 n을 가집니다. 그러나 r = 2 경우에 대해 위의 답은 직교 관계를 제공하며, 그것으로부터 Pn'은 (쉽게 결정되는 부호까지(up to)) 라게르 다항식(Laguerre polynomials)입니다.[9]
특히, 고전적 교란에 대해
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.