완전순열(교란, subfactorial)을 해결하는 방법

 

4명의 학생이 시험을 치른 후 자신의 시험지가 아닌 서로의 시험지를 채점해 주는 경우의 수는어떻게 될까요?

 

이 경우의 수를 세는 문제는 1708년 피에르 레이몬드(Pierre Raymond de Montmort가 처음으로 고안했습니다. complete permutation 완전순열 또는derangement라고 불리는 이경우의 수는 모든 원소의 위치를 바꾸는 순열입니다. 유한집합 S의 원소의 개수를 n개라했을 때 이 완전순열의 경우의 수를 준계승 영어로 서브팩토리얼이라고 하며 기호로는 다음과 같이 느낌표를 앞에 씁니다.

 

그렇다면 이 경우의수를 어떻게 구할 수 있을까요?

이 경우의 수는 다음과 같이 귀납적으로 정의되어 있습니다.

 

!n = (n-1)(!(n-1)+!(n-2)

 

완전순열의 경우의 수는 X에서 X로 가는 일대일 대응 함수 중에서

모든 x에 대해 f(x)=x가 아닌 함수의 개수와 같습니다.

그래서 함수를 이용해 완전순열을 만들어보겠습니다.

우선 f(1)=x라 하면, x는 1이 되면 안되므로 총 n-1개가 선택가능합니다. 

그 다음 F(x)=1아닐 수도 있고, f(x)=1일 수도 있습니다.

F(x)=1이 아니라하면 1을 제외한 n-1개의 원소들이 완전순열을 이뤄야 하므로 !(n-1)

+추가설명

남은 정의역의 원소는 2부터 x까지 n-1개이고, 치역의 원소는 1부터 n까지 중에 x를 뺀 n-1개이다. 이때, x는 1을 선택하지 못하고 나머지 원소도 자기 자신을 선택하지 못하므로 결국 n-1개 원소가 자기자신으로 가지 못하는 상황과 같다.

 

F(x)=1이라 하면 1과 x를 제외한 남은 n-2개의 원소들의 완전순열은 !(n-2)이므로

다음과 같이 귀납적으로 정의할 수 있습니다.

 

 

그런데 다른 표현 방법은 없을까요?

이 식과 다른 표현식은 다음과 같이 n!과 급수를 이용해 표현합니다.

!n=n!sum (-1)^n/i! i=0 to n

 

아까의 함수를 다시 보면 X에서 X로 가는 일대일 대응함수 중에서 고정 점이 없는 것을 세면 됩니다. 그렇다면 포함배제의 원리 즉, 전체집합에서 고정점이 있는 모든 경우의 합집합을 빼면 됩니다. 한 점이 고정점인 경우는 n개 중에서 고정점이 될 한개를 선택하고 나머지는 일대일 대응함수의 개수를 찾으면 됩니다. 그런데 이때 일대일 대응함수 중에서 고정점이 2개일 수 있으니 이 경우를 빼주면서 모두 더해주면 다음과 같은 식이 성립하며 이를정리하면 급수식이 나옵니다. 이제 여집합의 경우의 수를 구하기 위해 n!에서 식을 빼주게되면 완전순열을 구하는 급수식이 나오게 됩니다.

일반적인 고등학교 수준의 문제에서는 고정점이 5개 이상이 나오는 경우는 없어 !0부터 !5까지의 값을 외우고 계시는 것이 좋습니다.

 

수학적 의미를 잠시 살펴보면

우선 유도한 급수식은 e^x의 테일러 전개에 -1을 대입한 값이므로 lim n!/!n=e

(n!을 !n로 나눈 후 극한을 보내면 자연상수가 된다는 것을) 자명하게 얻을 있습니다.

그리고 이를 통해 식을 응용하면 이상 적분을 이용해서도 나타낼 수 있습니다.

N!을보면 이산수학 말고도 현대대수학에서 치환의 개수를 생각하시는 분들도 계실 것입니다. 이때 치환군 즉 permutation group이 특정한 완전수열 즉 derangement를 포함하는지판단하는 것은 NP-Complete 문제입니다.