순열의 일종.

완전순열 또는 교란순열[1]은 사람들이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데, 모든 사람이 자기 것이 아닌 모자를 쓰는 순열이라 할 수 있고, 이는 곧 치환에서 부동점[2]이 없는 경우를 가리킨다.[3] 그리고 모든 완전 순열의 수를 준계승 또는 교란수라고 하며, 이 개념을 처음 제시한 프랑스의 수학자 피에르 레몽 드몽모르(Pierre Raymond de Montmort)의 이름을 따 드몽모르 수라고도 한다.

기호로는 '교란'을 뜻하는 영단어 derangement의 머리글자를 따서 [math(D_n)], [math(d_n)] 또는 준계승을 의미하는 [math(!n)] 등으로 나타낸다.

[math(1)]부터 [math(n)]까지의 자연수를 한 줄 써 놓고, 아랫줄에도 한 줄 더 쓴다. 윗줄의 숫자들을 아랫줄의 숫자들로 하나하나씩 대응할 때 자기 자신을 제외한 다른 숫자로 대응을 하면 된다. 이렇게 대응하는 방법의 수를 센 것이 [math(D_n)]이다.

먼저 [math(1)]을 [math(2)]부터 [math(n)]까지 총 [math((n-1))]개의 자연수 중 하나로 대응해야 한다. 이때 [math(1)]이 [math(k)]에 대응된다고 하면 이후의 대응을 아래의 두 가지 경우로 나눌 수 있다.

[math(k)]로 가능한 수는 [math(1)]을 제외한 [math((n-1))]가지가 있으므로 전체 경우의 수는 [math(D_n= (n-1) left( D_{n-1}+D_{n-2} right))]

점화식을 얻으면 일반항에 한 걸음 다가간 것이다. 매우 교묘하게도, 적절히 이항해서 위 점화식을 다음과 같이 변형해주고

[math(D_n - nD_{n-1} = - left{D_{n-1} - left( n-1 right) D_{n-2} right})]
좌변을 [math(a_n)]으로 놓으면, 우변은 [math(-a_{n-1})]이 되므로 수열 [math(a_n)]은 공비가 [math(-1)]인 등비수열이다. [math(a_2 = D_2 -2D_1 = 1)]이므로 [math(a_n= left( -1 right)^n)]이다. 따라서

[math(D_n - nD_{n-1} = left( -1 right)^n)]
로 정리할 수 있다.

이제 양변을 [math(n!)]로 나누면

[math(dfrac{D_n}{n!} - dfrac{D_{n-1}}{(n-1)!} = dfrac{left( -1 right)^n}{n!})]
[math(dfrac{D_n}{n!} = b_n)]라 놓으면 식은 [math(b_n - b_{n-1} = dfrac{left( -1 right)^n}{n!})]이 되며 이는 전형적인 점화식 꼴이다. 하나씩 대입하면서 더해나가면
[math(displaystyle b_n = b_1 + sum_{k=2}^n frac{left( -1 right)^k}{k!})]
[math(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!})]
이 되는데 [math(dfrac{left( -1 right)^0}{0!} + dfrac{left( -1 right)^1}{1!} = 0)]이므로 [math(k=0)]부터 더해나가도 된다. 결과적으로 일반항은 다음과 같다.

[math(dfrac{n!}{k!} = {}_n{rm P}_{n-k})]이므로 위 식은 [math(displaystyle sum_{k=0}^n {}_n{rm P}_{n-k} left( -1 right)^k)]로도 나타낼 수 있으며 [math(n ge 2)]일 경우 [math(k=0)]인 항과 [math(k=1)]인 항을 더한 값이 [math(0)]이 되므로 순열을 이용한 표기로는

가 된다.
또한 [math(displaystyle e^x = sum_{k=0}^infty frac{x^k}{k!})]이므로 [math(displaystyle lim_{n to infty} frac{D_n}{n!} = frac 1e)]이며 이를 통해 [math(D_n)]은 [math(dfrac{n!}{e})]의 반올림 값임을 알 수 있다.

위 일반항은 포함·배제의 원리로도 유도가 가능하다. [math(n)]개의 물체를 배열하는 경우의 수가 [math(n!)]이고 이 중 부동점의 개수가 [math(k)]개 이상인 배열의 개수는 [math(dfrac{n!}{k!})]개이므로 포함·배제의 원리를 적용하면 원하는 결과를 얻는다.

앞서 말했듯이 완전순열은 '자기 모자 안 쓰는 경우의 수'라고 할 수 있다. 점화식으로 항을 구하기 위하여 처음의 두 항을 직접 구해 보자.

사람이 하나이면 자기 모자를 자기가 쓰는 경우밖에 없으므로 당연히 [math(D_1=0)]이다.
사람이 둘이면 서로가 모자를 바꿔 쓰는 방법이 유일하므로 [math(D_2=1)]이다.

이제 점화식 [math(D_n= (n-1) left( D_{n-1}+D_{n-2} right))]를 이용하여 각 항을 구하면 된다.

[math(D_3=2(1+0)=2)]
[math(D_4=3(2+1)=9)]
[math(D_5=4(9+2)=44)]
[math(D_6=5(44+9)=265)]
[math(D_7=6(265+44)=1854)]
⋮

이처럼 [math(D_n)]의 값은 갈수록 급격히 커진다.

완전순열을 다루는 문제에서는, 그냥 [math(D_5)]까지는 외워두자. 차례대로 [math(0, 1, 2, 9, 44)]이다. 그마저도 [math(D_5=44)]도 너무 많다고 하여 잘 나오지 않으며, [math(D_6=265)]부터는 경우의 수가 너무 많아져 절대 나오지 않는다.

#!folding【풀이】
사람과 모자를 대응하는 경우의 수를 생각해야 한다. 개별의 사람과 개별의 모자가 '''모두 구별'''되므로, 순서를 고려하여 네 사람의 모자를 배열하는 경우의 수를 구하면 [math(4!=24)]
네 사람이 모두 다른 사람의 모자를 쓰는 경우의 수는 [math(D_4=9)]

따라서 구하고자 하는 확률은
[math(\dfrac{9}{24}=\dfrac{3}{8})]

이걸 좀 더 업그레이드하면 다음과 같다.

#!folding【풀이】
사람과 모자를 대응하는 경우의 수를 생각해야 한다. 개별의 사람과 개별의 모자가 '''모두 구별'''되므로, 순서를 고려하여 네 사람의 모자를 배열하는 경우의 수를 구하면 [math(4!=24)]
먼저 자신의 모자를 쓰는 사람을 선택하는 경우의 수는 [math({}_4\rm{C}_{1}=4)]
나머지 세 사람이 모두 다른 사람의 모자를 쓰는 경우의 수는 [math(D_3=2)]
따라서 한 사람만 자신의 모자를 쓰는 경우의 수는 [math(4⋅2=8)]

따라서 구하고자 하는 확률은
[math(\dfrac{8}{24}=\dfrac{1}{3})]