교란순열(완전순열)

문제

예지반은 매주 저번 주에 배운 내용을 테스트하는 시험을 본다. 시험을 본 후 10명의 학생들은 각자 시험지를 채점하는데, 채점자는 누구여도 좋으나 스스로의 시험지는 채점할 수 없다. 이때 시험지를 채점자에게 나누어주는 경우의 수는 몇 가지일까?

---

문제 이해

$n$명의 사람들에게 작성된 $n$개의 편지를 무작위로 나누어줬을 때 누구도 자신에게 작성된 편지를 받지 못하는 경우의 수를 교란 순열(또는 완전 순열)이라고 해요. 가령 $n=3$인 경우 다음과 같이 2가지 경우가 있어요.

편지	A	B	C
받은 사람	b	c	a

편지	A	B	C
받은 사람	c	a	b

이런 개념 자체는 중학교 2학년에도 나오지만 이때는 $n$이 커봐야 3에서 4 정도로 직접 그 경우의 수를 세도 무리가 없을 정도로 계산량이 크지 않아요. 하지만 $n$이 10 정도로 매우 크다면 어떨까요? 이때는 수형도로 노가다하기 힘들어요. 따라서 이때 교란 순열을 계산하는 수식이 필요해요.

---

교란 순열의 일반항 유도

$n$명이 자신의 이름을 종이에 적어서 무작위로 재분배했을 때 자신의 이름을 받은 사람이 없도록 분배하는 경우의 수를 $D_n$이라고 할게요. 예를 들어 $D_3=2$에요.

 

이때 다음과 같은 생각으로 수열 $D_n$의 점화식을 유도할 수 있어요.

한번 1이 2부터 $n$까지 $n-1$개의 선택지로 향하는 경우의 수를 생각해볼게요. $2 \leq k \leq n$인 정수 $k$에 대해서

• 1이 $k$와 매칭 되는 경우
  1과 $k$는 이미 쌍을 이루었고(1 → $k$, $k$ → 1) 1과 $k$를 제외한 $n-2$개를 교란해주면 돼요. 따라서 $D_{n-2}$가 되요.
• 1이 $k$와 매칭 되지 않는 경우
  1과 $k$가 매칭 되면 안 돼요. 이를 위해 교란 순열을 사용할거에요. 1과 $k$가 같은 것이라고 한 후 교란순열을 돌려주면 그 결과는 항상 1과 $k$가 서로 매칭되지 않는 경우를 세줘요. 따라서 $1=k$로 생각하고 교란순열을 돌리면 $D_{n-1}$이 돼요.

앞서 말했듯 $k$로 가능한 수의 개수는 $n-1$개이니 이상의 과정을 $n-1$번 반복하면 다음과 같은 식이 완성돼요.

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

 

이 식을 적당히 이항 하면 다음과 같이 매우 편안한 꼴로 변형돼요.

$D_n-nD_{n-1}-\left\{D_{n-1}-\left(n-1\right)D_{n-2}\right\}$

 

여기서 새로운 수열을 다음과 같이 정의하면

$S_n=D_n-nD_{n-1}$

 

위 식은 다음과 같이 등비수열을 이루어요.

$S_n=-S_{n-1}$

 

초기 조건을 계산해보면 $D_1=0$, $D_2=1$ 이니 다음과 같지요.

$S_2=D_2-2D_1=1$

 

이것으로 수열 $S_n$의 일반항을 구하면 다음과 같아요.

$S_n=(-1)^{n-2}$

 

수열 $S_n$을 $D_n$으로 되돌리면 다음과 같아요.

$D_n-nD_{n-1}=(-1)^{n-2}$

 

적당히 이항 하고 -1의 지수를 조금 올려주면(이렇게 처리하면 뒤의 계산에서 지수의 -2를 고려하지 않아도 돼서 좋아요.)

$D_n=nD_{n-1}+(-1)^{n}$

 

이 식을 매번 적당히 변형해서 축차대입하면 다음과 같아요.

$D_n=nD_{n-1}+(-1)^{n}$

$nD_{n-1}=n(n-1)D_{n-2}+n(-1)^{n-1}$

$n(n-1)D_{n-2}=n(n-1)(n-2)D_{n-3}+n(n-1)(-1)^{n-2}$

$\vdots$

$n(n-1)\cdots(4)D_3=n(n-1)\cdots(4)(3)D_2+n(n-1)\cdots(4)(-1)^{3}$

$n(n-1)\cdots(3)D_2=n(n-1)\cdots(3)(2)D_1+n(n-1)\cdots(3)(-1)^{2}$

 

좌우변을 동시에 더해버리면 상쇄되는 부분이 많죠? 그 부분을 모두 날린 후 정리하면 다음과 같아요.

$D_n=n!D_1+\displaystyle\sum_{k=2}^{n}\frac{n!(-1)^k}{k!}$

 

이것이 교란 순열 $D_n$의 일반항이지만 아직은 식이 더러워요. 이것을 깔끔하게 하기 위하여 다음과 같은 조작을 할게요.

• $D_1=0$ 이니 해당 항 소거.
• 시그마 속에서 $n!$ 빼내기
• $\frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}=0$이므로 $k=0$부터 계산하도록 조정

그럼 다음과 같은 식이 돼요.

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

 

그래서 교란 순열 $D_n$의 일반항은 다음과 같아요.

$n$명이 자신의 이름을 종이에 적어서 무작위로 재분배했을 때 자신의 이름을 받은 사람이 없도록 분배하는 경우의 수는
$D_n=n!\displaystyle\sum_{k=0}^{n}\frac{(-1)^k}{k!}$
이다.

한편 시그마를 활용한 식이 난해하다면 다음과 같이 펼쳐서 적을 수도 있지요.

$D_n=n!\left(\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^{n}}{n!}\right)$

물론 맨 마지막 항의 부호는 $n$의 기우성에 따라 적당히 붙어야겠죠.

---

정리

$D_1$부터 $D_5$까지의 값은 다음과 같아요.

$n$	1	2	3	4	5
$D_n$	0	1	2	9	44

교란 순열의 일반항을 쓰기 힘든 상황에는 점화식을 사용할 수도 있지요. 점화식은 앞서 살펴보았듯

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

이에요. 여기에 대입하면 정수 계산 안에 교란 순열의 값을 계산할 수 있어요.

 

교란순열의 일반항과 점화식을 구하긴 했지만 컴퓨터를 사용하지 않는다면 식이 너무 복잡해져서 $D_6$까지만 해도 계산이 힘들어져요. 그래서 처음 제시한 문제는 사실 좀 오버에요. 그래도 답을 낸다면 $D_{10}=1334961$이에요.