교란순열(derangement)에 대하여

이번 글에서는 아래와 같은 형태의 문제에 대해서 생각해 볼 것이다.

목욕탕에 $n$명의 사람이 있다고 하자. 이 때, 몇 사람씩 그룹을 만들어 동그랗게 서서 서로가 앞사람의 등을 밀어주는 경우의 수 $D_n$은 얼마인가? 단, 혼자서 자기 등을 밀 수는 없다.

예를 들어 1, 2, 3, 4 네 사람이 있는 경우를 생각해 보자. 말을 줄이기 위해 기호를 하나 정의한다. 예를 들어, (213)와 같이 표현하는 것은 이라는 것은 2는 1의 등을 밀고, 1는 3의 등을 밀고, 3은 2의 등일 밀어 주는 것을 의미한다고 하자. 그러면 1,2,3,4 네 명이서 서로 등을 밀어 주는 경우의 수는 다음과 같이 셀 수 있다.

$$(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23)$$

따라서 모두 9가지 경우가 있다.

똑같은 문제로 다음과 같은 상황을 들 수 있다.

$n$명의 사람이 있고, 그들의 이름이 써진 모자 $n$개가 있다. 모자를 모두 회수한 뒤 다시 무작위로 돌려 줬을 때, 단 한 사람도 자기 자신의 모자를 돌려 받지 않는 경우의 수 $D_n$은 얼마인가?

위 두 문제를 자세히 살펴보면, 위 두 문제 모두 고정점을 갖지 않는 순열의 개수를 묻는 문제임을 알 수 있다. 이 수열 $D_n$에는 교란순열(derangement)이라는 이름이 붙여져 있는데, 첫 몇개의 항은 아래와 같다.

$$D_0=1,D_1=0,D_2=1,D_3=2,D_4=9,D_5=44,D_6=265,\dots$$

교란순열의 점화식과 일반항

이제 위 교란순열의 점화식을 구해보자. 먼저 각각의 사람들을 $p_1,\dots ,p_n$이라 하고, 그들의 모자를 각각 $h_1,\dots ,h_n$이라 하자. 그러면 $p_1$은 $h_2$부터 $h_n$ 중 하나의 모자를 가져가야만 한다. (따라서 총 $n-1$개의 경우의 수가 생긴다.) 이제 $p_1$이 모자 $h_k$를 가져갔다고 가정하자. 그러면 두 가지 경우를 고려해 볼 수 있다.

1. 만약 $p_k$가 $h_1$을 돌려 받았다고 해보자. 그러면 $p_1$과 $p_k$가 서로 모자를 교환한 것과 마찬가지이므로, 이제 문제는 나머지 $n-2$명의 사람들이 $n-2$개의 모자를 (자기 자신의 모자를 제외하고) 나누어 가지는 문제로 바뀐다. 즉, $D_{n-2}$를 구하는 문제와 같다.
2. 이제 $p_k$가 $h_1$을 돌려 받지 않았다고 해보자. 이제 편의상 $h_1$과 $h_k$를 잠시 바꾸어 주기로 하자. 그러면 $p_1$은 $h_1$을 가지고 있고, $p_k$는 $h_k$를 돌려 받지 않았다고 할 수 있다. 따라서 이제 문제는 $p_1$을 제외한 나머지 $n-1$명의 사람들이 $h_1$를 제외한 나머ㄱ지 $n-1$개의 모자를 (자기 자신의 모자를 제외하고) 나누어 가지는 문제로 바뀐다. (물론, 모든 모자를 돌려 받은 뒤, 마지막에 다시 $h_1$과 $h_k$를 바꾸어 주어야 한다.) 즉, $D_{n-1}$을 구하는 문제와 같다.

이 때 사건 (1)과 사건 (2)는 동시에 발생할 수 없으므로, 다음을 얻는다.

정리 1. 교란순열의 점화식

임의의 정수 $n\ge 2$에 대하여, 교란순열 $D_n$은 다음의 점화식을 만족한다.

$$D_n=(n-1)(D_{n-1}+D_{n-2}),D_0=1,D_1=0.$$

위 점화식을 살펴보면 재미있는 사실을 하나 발견할 수 있다. $P_n$을 $n$개의 항으로 만들 수 있는 순열의 개수라 하자. 즉, $P_n=n!$이라 정의하자. 그러면 (물론 위와 같이 경우의 수를 나누어 조합론적으로 증명할 수도 있지만) 아래와 같이 간단한 계산을 통해 $P_n$의 점화식을 구할 수 있다.

$$\begin{array}{rl}{P}_n& =n!\\ & =n(n-1)!\\ & =(n-1)(n-1)!+(n-1)!\\ & =(n-1)(n-1)!+(n-1)(n-2)!\\ & =(n-1)((n-1)!+(n-2)!)\\ & =(n-1)(P_{n-1}+P_{n-2})\end{array}$$

이제 $P_0=1$이고 $P_1=1$이므로, 아래의 점화식을 얻는다.

$$P_n=(n-1)(P_{n-1}+P_{n-2}),P_0=1,P_1=1.$$

따라서 수열 $P_n$과 교란순열 $D_n$ 둘 다 동일한 점화식으로 표현할 수 있음을 알 수 있다. 이와 같은 이유로 $D_n=!n$으로 나타내고 준계승(subfactorial)이라 부르기도 한다.

포함배제의 원리를 이용한 일반항 계산

교란순열 $D_n$의 일반항은 다음과 같이 주어진다.

정리 2. 교란순열의 점화식

임의의 음이 아닌 정수 $n$에 대하여, 교란순열 $D_n$의 일반항은 다음과 같이 주어진다.

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

증명. 위 일반항은 포함배제의 원리(inclusion–exclusion principle)를 이용하면 간단히 구할 수 있다. 교한순열의 개수는 포함배제의 원리에 의해 전체 순열의 개수 $n!$에서 하나의 항을 선택하여 고정하고 나머지를 무작위로 배열한 순열의 개수를 빼고, 다시 두개의 항을 선택하여 고정하고 나머지를 무작위로 배열한 순열의 개수를 더하고, 다시 세개의 항을 고정하고 나머지를 무작위로 배열한 순열의 개수를 더하고 하는 과정을 마지막까지 반복하여 구할 수 있다. 이 때, $n$개의 원소에 대하여 먼저 $k\le n$개의 항을 선택하여 고정하고 나머지 $n-k$개의 원소를 무작위로 배열하는 방법의 수는

$$D_n^k:=(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$$

와 같이 구할 수 있으므로,

$$D_n=\sum _{k=0}^n(-1{)}^k{D}_n^k=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}$$

를 얻는다.

이제 $n$개의 항을 무작위로 배열했을 때, 이 배열의 교란순열이 되는 경우의 수는 $D_n/n!$으로 나타낼 수 있는데, 이 값의 극한값을 구해보면 뜬금없이 오일러 상수가 등장하게 된다.

$$\underset{n\to \mathrm{\infty }}{lim}\frac{D_n}{n!}=\underset{n\to \mathrm{\infty }}{lim}\sum _{k=0}^n\frac{(-1{)}^k}{k!}=\frac{1}{e}$$

이 때, 위 식의 우변의 값은 $e^x$의 맥클로린 전개에서 $x=-1$을 대입한 값과 같음을 이용하였다. 즉,

($n$이 충분히 크다면) $n$명의 사람이 있고, 그들의 이름이 써진 모자 $n$개가 있다. 모자를 모두 회수한 뒤 다시 무작위로 돌려 줬을 때, 단 한 사람도 자기 자신의 모자를 돌려 받지 않을 확률은 $1/e$와 비슷하다.

좀 더 자세하게, 임의의 $n\ge 1$에 대하여 다음이 성립함이 알려져 있다.

$$D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$$

지수생성함수를 이용한 일반항의 유도

이번에는 교란순열 $D_n$의 일반항을 지수생성함수(exponential generating function)를 이용하여 계산해 보자. 먼저 교란순열의 점화식을 변형하면 다음을 얻을 수 있다.

$$\begin{array}{rl}{D}_n-n{D}_{n-1}& =(n-1)(D_{n-1}+D_{n-2})-n{D}_{n-1}\\ & =-[D_{n-1}-(n-1)D_{n-2}]\end{array}$$

따라서, 위 등식을 반복 적용하면 최종적으로 $D_n-n{D}_{n-1}=(-1{)}^n$를 얻는다. 이제 이 수열에 대한 지수생성함수는 다음과 같이 정의된다.

$$f(x)=\sum _{n=0}^{\mathrm{\infty }}\frac{D_n}{n!}{x}^n$$

이제 위에서 얻은 점화식을 사용하면,

$$\sum _{n=0}^{\mathrm{\infty }}\frac{D_n-n{D}_{n-1}}{n!}{x}^n=\sum _{n=0}^{\mathrm{\infty }}\frac{(-1{)}^n}{n!}{x}^n=\frac{1}{e}$$

좌변을 계산하면,

$$\text{LHS}=\sum _{n=0}^{\mathrm{\infty }}\frac{D_n}{n!}{x}^n-\sum _{n=0}^{\mathrm{\infty }}\frac{n{D}_{n-1}}{n!}{x}^n=f(x)-\sum _{n=1}^{\mathrm{\infty }}\frac{D_{n-1}}{(n-1)!}{x}^n=f(x)-xf(x)$$

따라서,

$$f(x)=\frac{e^{-x}}{1-x}=\left(\sum _{k=0}^{\mathrm{\infty }}{x}^k\right)\left(\sum _{k=0}^{\mathrm{\infty }}\frac{(-1{)}^k}{k!}{x}^k\right)$$

그러므로 우변의 곱을 계산해주면, $D_n$의 일반항은 다음과 같이 주어진다.

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

마지막으로 양변에 $n!$을 곱해주면, 앞에서 얻었던 $D_n$의 일반항과 같음을 확인할 수 있다.