수치표
| 수치표 |
n | vert D_nvert | n! | vert D_nvert/n! |
| 1 | 0 | 1 | 0.0000000000 |
| 2 | 1 | 2 | 0.5000000000 |
| 3 | 2 | 6 | 0.3333333333 |
| 4 | 9 | 24 | 0.3750000000 |
| 5 | 44 | 120 | 0.3666666667 |
| 6 | 265 | 720 | 0.3680555556 |
| 7 | 1854 | 5040 | 0.3678571429 |
| 8 | 14833 | 40320 | 0.3678819444 |
| 9 | 133496 | 362880 | 0.3678791887 |
| 10 | 1334961 | 3628800 | 0.3678794643 |
| 11 | 14684570 | 39916800 | 0.3678794392 |
| 12 | 176214841 | 479001600 | 0.3678794413 |
| 13 | 2290792932 | 6227020800 | 0.3678794412 |
| 14 | 32071101049 | 87178291200 | 0.3678794412 |
| 15 | 481066515734 | 1307674368000 | 0.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. 영상
집합 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의 교란순열이라고 한다.
집합
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,
24133142,
3412,
34214123,
4312,
4321로 총 아홉 개이다.
집합
S=\{a_1,a_2,\cdots,a_n\}에 대해 모든 교란의 집합을
D_n이라 하자.
1\le n \le 4일 때
S_n과
D_n을 나타낸 표는 다음과 같다.
n | S_n | D_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. 교란의 계산 ✎
사람 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.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)
수열 \{|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!}
을 얻는다.
\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}dt4. 교란순열과 순열의 비율 ✎
대칭군 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
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)
- Weisstein, Eric W. "Derangement." From MathWorld--A Wolfram Web Resource.
7. 참고 문헌 ✎
- 박승안(2012). 『이산수학』 (제3판). 경문사. ISBN 9788961055345
