교란순열

다음 문제를 생각해보자.

이 Hatcheck Problem은 굉장히 오래된 문제이다(출입구에 모자를 맡기다니!). 그래도 재미있다. \(n\)개의 양의 정수 \(1, 2, 3, \ldots, n\)을 배열할 때, '자신의 위치'에 있는 정수가 하나도 없도록 배열한 것을 \(n\)개의 정수의 교란순열(derangement)이라 한다.¹ \(1, 2, 3, \ldots, n \)의 모든 교란순열의 개수를 \(D_{n}\)으로 나타낸다. 일반적으로 서로 다른 원소들로 만든 string의 교란순열이란 그 원소들의 배열 중 원래 위치에 있는 원소가 하나도 없는 배열을 일컫는다. Hatcheck Problem의 답은 물론 \(D_{n}\)이다. 이제 \(D_{n}\)을 나타내는 식을 찾아보자.

\(\{1, 2, 3, \ldots, n\}\)의 배열 중 \(i\)가 \(i\)번째 위치에 있는 배열을 모두 모아 놓은 집합을 \(A_{i}\)라 하자. 그러면 어느 \(A_{i}\)에도 속하지 않는 배열의 개수를 구하는 것이 곧 \(D_{n}\)을 구하는 것이 된다. PIE의 보조정리에 의해 \begin{align*} D_{n}&= n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\binom{n}{3}(n-3)!+\cdots+(-1)^{n}\binom{n}{n}0! \\ &=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\cdots+(-1)^{n}\frac{1}{n!}\right) \end{align*} 를 얻는다.

실수 \(x\)에 대하여 \(e^{x}=\sum_{k=0}^{\infty}\frac{1}{k!}x^{k}\)임을 상기해보자. (이를 그냥 \(e^{x}\)의 정의로 여겨도 된다.) 그러면 \[ \frac{1}{e}=e^{-1}=\sum_{k=0}^{\infty}(-1)^{k}\frac{1}{k!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\cdots+(-1)^{k}\frac{1}{k!}+\cdots \] 로부터 \(D_{n}/n!\)이 \(1/e\)와 상당히 유사한 값을 취할 것임을 추측할 수 있다. 사실, 임의의 \(n\)에 대하여 \(D_{n}\)은 \(n!/e\)와 가장 가까운 정수이며, 대략 \(D_{n}\approx n!\times 0.367679441171442\ldots\)로 쓸 수 있다.

만일 서로 다른 하나씩의 주소를 갖고 있는 사람들이 편지를 한 통씩 쓴 후 이들을 모두 회수하고 다시 각자에게 회수한 편지를 임의로 한 통씩을 나눠줄 때, 자신의 편지를 받은 이가 한 명도 없을 확률은 (사람이 아무리 많더라도) \(1/e\) 근처일 것이다.

두 개의 수 \(D_{n}/n!, D_{n-1}/(n-1)!\)를 비교하여, 이들의 차가 얼마나 작은 값인지를 살펴보자. 식 \[ \frac{D_{n}}{n!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\cdots+(-1)^{n}\frac{1}{n!} \] 에서 \[ \frac{D_{n-1}}{(n-1)!}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\cdots+(-1)^{n-1}\frac{1}{(n-1)!} \] 를 빼면 \[ \frac{D_{n}}{n!}-\frac{D_{n-1}}{(n-1)!}=(-1)^{n}\frac{1}{n!} \] 라는 흥미로운 식을 얻는다. 그런데 이 식의 양변에 \(n!\)을 곱하여 얻은 식 \[ D_{n}=nD_{n-1}+(-1)^{n}\quad\mbox{for \(n\geq\)2} \] 는 더 멋지다.

다음의 사소한 내용은 흥미로울 수 있는 내용이다. 때때로 기호 “\(n\style{display: inline-block; transform: rotate(180deg)}{!}\)”를 \[ n\style{display: inline-block; transform: rotate(180deg)}{!}=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)!=n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!} \] 로 정의하고 이를 “\(n\) subfractorial”이라 읽는다. 즉 \(n\style{display: inline-block; transform: rotate(180deg)}{!} =D_{n}\)으로 정의한다.

PIE Problems Ⅲ.

1. 검은색 공 \(12\)개, 하얀색 공 \(12\)개, 주황색 공 \(8\)개, 초록색 공 \(8\)개에서 \(20\)개의 공을 택하는 경우의 수는?
2. \(0\)부터 \(9\)까지의 \(10\)개의 숫자를 이용하여 만든 길이 \(12\)짜리 수열 중 \(10\)개의 숫자 모두를 사용하지 않은 수열은 몇 개인가?
3. \(1\)학년 한 명과 \(2\)학년 한 명으로 이루어진 조가 세 개 있다고 하자. 이 여섯 명의 사람을 모두 원탁에 앉힐 때, 같은 조원끼리는 이웃하지 않도록 앉히는 경우의 수는?
4. COMBINATORICS의 글자들을 배열할 때, 두 개의 C가 모두 두 개의 O보다 왼쪽에 있거나, 두 개의 O가 모두 두 개의 I보다 왼쪽에 있거나, 두 개의 I가 모두 두 개의 C보다 왼쪽에 있는 경우의 수는?
5. COMBINATORICS의 글자들을 배열할 때, 두 개의 C가 모두 두 개의 O보다 왼쪽에 있거나, 두 개의 O가 모두 두 개의 I보다 왼쪽에 있거나, 두 개의 I가 모두 S보다 왼쪽에 있는 경우의 수는?

PIE Problems Ⅳ.

1. 여덟개의 정수 \(1, 2, 3, \ldots, 8\)를 재배열할 때, \(i(=1, 2, 3, \ldots, 8)\) 바로 뒤에 \(i+1\)가 오지 않도록 배열하는 경우의 수는?
2. 회전목마를 탄 \(8\)명의 어린이가 있을 때, 각각의 어린이 앞에 새로운 사람이 오도록 자리를 재배치하는 경우의 수는? (단, 회전목마엔 총 \(8\)마리의 말이 원형으로 일정한 간격으로 놓여 있으며 이 말들은 서로 구별되지 않는다.)
3. 어린이 \(23\)명에게 서로 구별되는 \(37\)권의 책을 분배할 때, 책을 받지 못한 어린이가 없도록 분배하는 경우의 수는?
4. 방정식 \[ x_{1}+x_{2}+x_{3}+x_{4}=40 \] 의 정수해 중 조건 \[ 1\leq x_{1}\leq 5,\quad 2\leq x_{2}\leq 7,\quad 3\leq x_{3}\leq 9,\quad 5\leq x_{4} \] 를 만족시키는 것은 몇 개인가?
5. 구별되지 않는 \(3\)개의 상자에 서로 구별되는 \(10\)개의 공을 담는 경우의 수는?
6. 알파벳 \(26\)글자를 임의로 배열할 때, 자연스러운 위치에 놓인 알파벳이 있을 확률은? (여기서 자연스러운 위치에 놓인 알파벳이 있다는 것은, \(i\)번째에 놓여있는 \(i\)번째 알파벳이 있다는 뜻이다.)
7. 점화관계 \[ D_{n}=(n-1)\left(D_{n-1}+D_{n-2}\right)\quad(n>2) \] 를 증명하여라.

1. 교란순열을 그냥 '교란'이라 부르기도하며, '난순열'이라 부르기도 한다.