트로츠키 ➤ 교란순열
수치표
수치표
n\\vert D_n\\vertn!\\vert D_n\\vert/n!
1010.0000000000
2120.5000000000
3260.3333333333
49240.3750000000
5441200.3666666667
62657200.3680555556
7185450400.3678571429
814833403200.3678819444
91334963628800.3678791887
10133496136288000.3678794643
1114684570399168000.3678794392
121762148414790016000.3678794413
13229079293262270208000.3678794412
1432071101049871782912000.3678794412
1548106651573413076743680000.3678794412

교란순열(Derangement), 교란, 또는 완전순열(Complete permutation)은 집합의 어떤 원소도 원래 자리에 있지 아니한 순열이다.

목차

1. 정의
2. 예시
3. 교란의 계산
3.1. 점화식
3.2. 일반항 표현
3.2.1. 포함-배제 원리를 이용한 방법
3.2.2. 생성함수를 이용한 방법
3.2.3. 기타 공식
4. 교란순열과 순열의 비율
5. 일반화
6. 외부
7. 참고 문헌
8. 영상

1. 정의 ✎ ⊖

집합 S=\\{a_1,a_2,\\cdots,a_n\\} 위의 순열 \\sigma:S\\to S에 대해 \\sigma(a_1)\\ne a_1, \\sigma(a_2)\\ne a_2,\\cdots, \\sigma(a_n)\\ne a_n이면 \\sigma를 a_1,a_2,\\dots, a_n의 교란순열이라고 한다.

2. 예시 ✎ ⊖

집합 S=\\{1,2,3,4\\}에 대해 \\sigma(1)= a_1, \\sigma(2)=a_2, \\sigma(3)=a_3, \\sigma(4)=a_4인 순열 \\sigma:S \\to S를 a_1a_2a_3a_4로 표기하자. 이때 순열 중에서 교란순열인 것은

2143, 2341, 2413
3142, 3412, 3421
4123, 4312, 4321

로 총 아홉 개이다.

집합 S=\\{a_1,a_2,\\cdots,a_n\\}에 대해 모든 교란의 집합을 D_n이라 하자. 1\\le n \\le 4일 때 S_n과 D_n을 나타낸 표는 다음과 같다.

nS_nD_n
1\\{1\\}\\emptyset
2\\{1,2\\}\\{21\\}
3\\{1,2,3\\}\\{231, 312\\}
4\\{1,2,3,4\\}\\{2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321\\}

3. 교란의 계산 ✎ ⊖

3.1. 점화식 ✎ ⊖

사람 1,2,\\dots,n이 1,2,\\dots,n으로 지정된 비행기 좌석에 앉는 상황을 가정하자. 이때 누구도 자신에게 할당된 수와 같지 않은 자리에 앉는 경우의 수를 구하고자 한다. 누구도 자신에게 할당된 수와 같지 않은 자리에 앉는 경우의 집합을 D_n이라 하면, |D_n|을 구하면 된다. 사람 1이 좌석 k에 앉는다고 하자. 그러면 사람 1은 좌석 1에 앉지 않으므로, 사람 1이 좌석에 앉는 경우의 수는 n-1이다. 그러면 다음 두 가지의 가능성이 존재한다.

1. 사람 k가 좌석 1에 앉지 않는다고 하자. 그러면 이 경우는 금지된 선택이 단 하나(사람 k가 좌석 1을 고르지 않는다)이므로, n-1명이 n-1개의 좌석에 앉는 문제와 동일하다.
2. 사람 k가 좌석 1에 앉는다고 하자. 그러면 나머지 n-2명은 n-2개 좌석에 앉는다.

따라서 다음 식이 성립한다.

|D_n|=(n-1)(|D_{n-1}|+|D_{n-2}|)

한편, |D_n|=(n-1)(|D_{n-1}|+|D_{n-2}|)의 양변에 -n|D_{n-1}|을 더하면 |D_n|-n|D_{n-1}|=-(|D_{n-1}|-(n-1)|D_{n-2}|)이다. 따라서 다음 식이 성립한다.

|D_n|=n|D_{n-1}|+(-1)^n

3.2. 일반항 표현 ✎ ⊖

3.2.1. 포함-배제 원리를 이용한 방법 ✎ ⊖

순열 f에 대해 f(i)=i인 순열 전체의 집합을 A_i라 하자. 그러면 D_n의 원소는 순열 중 f(i)=i인 i가 존재하는 순열들을 모두 제외한 것과 같으므로

\\displaystyle |D_n|=n!-|A_1 \\cup A_2\\cup \\cdots \\cup A_n|

이다. 포함-배제 원리에 의해

\\displaystyle |D_n|=n!-\\left(\\sum_{\\alpha}|A_\\alpha|-\\sum_{\\alpha<\\beta}|A_\\alpha\\cap A_\\beta|+\\sum_{\\alpha<\\beta<\\gamma}|A_{\\alpha}\\cap A_{\\beta} \\cap A_{\\gamma}|-\\cdots+(-1)^{n+1}|A_1 \\cap A_2 \\cap \\cdots \\cap A_n |\\right)

이다. 이때,

|A_{i_1}\\cap A_{i_2}\\cap \\cdots \\cap A_{i_k}|=(n-k)!

이고 n개의 서로 다른 집합 중 k개를 고르는 경우의 수는 \\dbinom{n}{k}이므로,

\\displaystyle |D_n|=n!-\\sum_{k=1}^n (-1)^{k+1}(n-k)!\\binom{n}{k}=n!-\\sum_{k=1}^n \\frac{n!(-1)^{k+1}}{k!}

이다. 따라서 다음 식을 얻는다.

\\displaystyle |D_n|=n!\\sum_{k=0}^n \\dfrac{(-1)^k}{k!}

n=0부터 시작하는 수열 \\{|D_n|\\}은 다음과 같다.

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... (OEIS의 수열 A166)

3.2.2. 생성함수를 이용한 방법 ✎ ⊖

수열 \\{|D_n|\\}의 지수 생성함수를 G(x)라고 하자. 이때 점화식 |D_n|=n|D_{n-1}|+(-1)^{n}의 양변에 \\dfrac{x^n}{n!}을 곱하고 \\sum을 취하면, |D_0|=1이므로

\\displaystyle\\sum_{n=0}^{\\infty}|D_n|\\dfrac{x^n}{n!}=\\sum_{n=1}^{\\infty}|D_{n-1}|\\dfrac{x^n}{(n-1)!}+\\sum_{n=0}^{\\infty}(-1)^{n}\\dfrac{x^n}{n!}

이다. 이 식을 정리하면

G (x)=xG (x)+e^{-x}

이므로

G(x)=\\dfrac {e^{-x}}{1-x}

이다. 그러면

\\displaystyle G(x)=\\left(\\sum_{n=0}^{\\infty}\\frac{(-1)^nx^n}{n!}\\right)\\left(\\sum_{n=0}^{\\infty}x^n\\right)=\\sum_{n=0}^{\\infty}\\left(\\sum_{k=0}^n \\frac{(-1)^k}{k!} \\right)x^n

이므로

\\displaystyle |D_n|=n!\\sum_{k=0}^n \\frac{(-1)^k}{k!}

을 얻는다.

3.2.3. 기타 공식 ✎ ⊖

\\displaystyle \\left\\vert |D_n|-\\frac{n!}{e} \\right\\vert <\\frac{1}{n+1}

이므로, n\\ge 1이면 다음 공식을 얻는다. 이때 \\lfloor x \\rfloor는 최대정수함수이다.

\\displaystyle |D_n|=\\left\\lfloor \\frac{n!}{e}+\\frac{1}{2}\\right\\rfloor,\\quad n\\ge 1

다음 식이 알려져 있다.(1)

\\displaystyle |D_n|=\\int_{0}^{\\infty}(t-1)^ne^{-t}dt

4. 교란순열과 순열의 비율 ✎ ⊖

대칭군 S_n의 원소를 하나 선택했을 때 그것이 교란순열일 확률을 p_n이라 하자. 그러면

\\displaystyle p_n=\\frac{|D_n|}{n!}=\\sum_{k=0}^n \\frac{(-1)^k}{k!}

이다. n이 충분히 크면, 순열의 수에 대한 교란순열의 수의 비율은 1/e에 수렴한다. 즉, 다음 식이 성립한다.

\\displaystyle \\lim_{n\\to \\infty}\\frac{|D_n|}{n!}=\\lim_{n\\to \\infty}\\sum_{k=0}^n \\dfrac{(-1)^k}{k!}=\\frac{1}{e}\\approx 0.3678794

5. 일반화 ✎ ⊖

  • n개의 원소를 일렬로 나열할 때 고정점이 k개인 경우: 부분교란으로 경우의 수는 \\dbinom {n}{k}|D_{n-k}|이다.
  • 서로 다른 n종류의 물건이 각각 n_1,n_2,\\cdots,n_k개 있을 때, 재배치해서 모두가 다른 자리에 있게 되는 경우의 수는

\\displaystyle P_{n_1,\\cdots,n_k}=(-1)^{n_1+\\cdots+n_k}\\int_0^{\\infty}L_{n_1}(x)L_{n_2}(x)\\cdots L_{n_k}(x)e^{-x}dx

로 나타낼 수 있다. 이때 L_{n_i}(x)는 라게르 다항식이다.(2)

6. 외부 ✎ ⊖

  • Weisstein, Eric W. "Derangement." From MathWorld--A Wolfram Web Resource.

7. 참고 문헌 ✎ ⊖

  • 박승안(2012). 『이산수학』 (제3판). 경문사. ISBN 9788961055345

8. 영상 ✎ ⊖



이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.
(1) P. Mark Kayll. "Integrals Don’t Have Anything to Do with Discrete Math, Do They?". Mathematics Magazine 01/2011; 84(2):108-119. DOI: 10.4169/math.mag.84.2.108
(2) Even, S.; J. Gillis (1976). "Derangements and Laguerre polynomials". Mathematical Proceedings of the Cambridge Philosophical Society 79 (01): 135–143. doi:10.1017/S0305004100052154.