완전순열
1. 개요
순열의 일종.
완전순열 또는 교란순열[1]은 사람들이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데, 모든 사람이 자기 것이 아닌 모자를 쓰는 순열이라 할 수 있고, 이는 곧 치환에서 부동점[2]이 없는 경우를 가리킨다.[3] 그리고 모든 완전 순열의 수를 '''준계승''' 또는 '''교란수'''라고 하며, 이 개념을 처음 제시한 프랑스의 수학자 피에르 레몽 드몽모르(Pierre Raymond de Montmort)의 이름을 따 '''드몽모르 수'''라고도 한다.
기호로는 '교란'을 뜻하는 영단어 '''d'''erangement의 머리글자를 따서 $$D_n$$, $$d_n$$ 또는 준계승을 의미하는 $$!n$$ 등으로 나타낸다.
2. 언어별 명칭
3. 점화식과 일반항
$$1$$부터 $$n$$까지의 자연수를 한 줄 써 놓고, 아랫줄에도 한 줄 더 쓴다. 윗줄의 숫자들을 아랫줄의 숫자들로 하나하나씩 대응할 때 자기 자신을 제외한 다른 숫자로 대응을 하면 된다. 이렇게 대응하는 방법의 수를 센 것이 $$D_n$$이다.
먼저 $$1$$을 $$2$$부터 $$n$$까지 총 $$(n-1)$$개의 자연수 중 하나로 대응해야 한다. 이때 $$1$$이 $$k$$에 대응된다고 하면 이후의 대응을 아래의 두 가지 경우로 나눌 수 있다.
- $$k$$가 $$1$$에 대응되는 경우, $$1$$과 $$k$$는 서로 짝을 이루었고 나머지 $$(n-2)$$개를 교란하면 되므로 그 경우의 수는 $$D_{n-2}$$.
- $$k$$가 $$1$$에 대응되지 않는 경우, $$k$$와 $$1$$을 같은 것으로 취급해서 $$(n-1)$$가지를 교란하는 경우와 같으므로 그 경우의 수는 $$D_{n-1}$$.
점화식을 얻으면 일반항에 한 걸음 다가간 것이다. 매우 교묘하게도, 적절히 이항해서 위 점화식을 다음과 같이 변형해주고
$$D_n - nD_{n-1} = - \left\{D_{n-1} - \left( n-1 \right) D_{n-2} \right\}$$
좌변을 $$a_n$$으로 놓으면, 우변은 $$-a_{n-1}$$이 되므로 수열 $$a_n$$은 공비가 $$-1$$인 등비수열이다. $$a_2 = D_2 -2D_1 = 1$$이므로 $$a_n= \left( -1 \right)^n$$이다. 따라서
$$D_n - nD_{n-1} = \left( -1 \right)^n$$
로 정리할 수 있다.
이제 양변을 $$n!$$로 나누면
$$\dfrac{D_n}{n!} - \dfrac{D_{n-1}}{(n-1)!} = \dfrac{\left( -1 \right)^n}{n!}$$
$$\dfrac{D_n}{n!} = b_n$$라 놓으면 식은 $$b_n - b_{n-1} = \dfrac{\left( -1 \right)^n}{n!}$$이 되며 이는 전형적인 점화식 꼴이다. 하나씩 대입하면서 더해나가면
$$\displaystyle b_n = b_1 + \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!}$$
$$\displaystyle \frac{D_n}{n!} = \frac{D_1}{1!} + \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!} = \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!}$$
이 되는데 $$\dfrac{\left( -1 \right)^0}{0!} + \dfrac{\left( -1 \right)^1}{1!} = 0$$이므로 $$k=0$$부터 더해나가도 된다. 결과적으로 일반항은 다음과 같다.
$$\dfrac{n!}{k!} = {}_n{\rm P}_{n-k}$$이므로 위 식은 $$\displaystyle \sum_{k=0}^n {}_n{\rm P}_{n-k} \left( -1 \right)^k$$로도 나타낼 수 있으며 $$n \ge 2$$일 경우 $$k=0$$인 항과 $$k=1$$인 항을 더한 값이 [math(0)]이 되므로 순열을 이용한 표기로는
가 된다.
또한 $$\displaystyle e^x = \sum_{k=0}^\infty \frac{x^k}{k!}$$이므로 $$\displaystyle \lim_{n \to \infty} \frac{D_n}{n!} = \frac 1e$$이며 이를 통해 $$D_n$$은 $$\dfrac{n!}{e}$$의 반올림 값임을 알 수 있다.
위 일반항은 포함·배제의 원리로도 유도가 가능하다. $$n$$개의 물체를 배열하는 경우의 수가 $$n!$$이고 이 중 부동점의 개수가 $$k$$개 이상인 배열의 개수는 $$\dfrac{n!}{k!}$$개이므로 포함·배제의 원리를 적용하면 원하는 결과를 얻는다.
4. 항
앞서 말했듯이 완전순열은 '자기 모자 안 쓰는 경우의 수'라고 할 수 있다. 점화식으로 항을 구하기 위하여 처음의 두 항을 직접 구해 보자.
사람이 하나이면 자기 모자를 자기가 쓰는 경우밖에 없으므로 당연히 $$D_1=0$$이다.
사람이 둘이면 서로가 모자를 바꿔 쓰는 방법이 유일하므로 $$D_2=1$$이다.
이제 점화식 $$D_n= (n-1) \left( D_{n-1}+D_{n-2} \right)$$를 이용하여 각 항을 구하면 된다.
$$D_3=2(1+0)=2$$
$$D_4=3(2+1)=9$$
$$D_5=4(9+2)=44$$
$$D_6=5(44+9)=265$$
$$D_7=6(265+44)=1854$$
⋮
이처럼 $$D_n$$의 값은 갈수록 급격히 커진다.
5. 예제
완전순열을 다루는 문제에서는, '''그냥 $$D_5$$까지는 외워두자.''' 차례대로 $$0, 1, 2, 9, 44$$이다. 그마저도 $$D_5=44$$도 너무 많다고 하여 잘 나오지 않으며, $$D_6=265$$부터는 경우의 수가 너무 많아져 절대 나오지 않는다.
이걸 좀 더 업그레이드하면 다음과 같다.
[1] 그냥 '교란'이라고도 한다.[2] 자기 자신으로 짝지어지는 경우[3] 군론적으로 서술하자면, 집합 X의 치환군의 어떤 부분군 H가 X위에 충실한 작용(faithful action)을 가질 경우, H의 원소는 X의 완전순열이 된다.