교란순열

다음 문제를 생각해보자.

The Hatcheck Problem. 안쪽에 자신의 이름이 적힌 모자를 하나씩 쓰고 있는 $n$ 명의 사람이 어떤 공연장에 들어가며 출입구에 모자를 맡겼다고 하자. 이들이 공연장에서 나오며 출입구에 맡겼던 $n$ 개의 모자를 각자 하나씩 받았나왔다고 할 때, 자신의 모자를 돌려 받은 사람이 한 명도 없는 경우의 수는?

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

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

실수 $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!} + \dots + (- 1)^{k} \frac{1}{k!} + \dots$ 로부터 $D_{n} / n!$ 이 $1 / e$ 와 상당히 유사한 값을 취할 것임을 추측할 수 있다. 사실, 임의의 $n$ 에 대하여 $D_{n}$ 은 $n! / e$ 와 가장 가까운 정수이며, 대략 $D_{n} \approx n! \times 0.367679441171442 \dots$ 로 쓸 수 있다.

만일 서로 다른 하나씩의 주소를 갖고 있는 사람들이 편지를 한 통씩 쓴 후 이들을 모두 회수하고 다시 각자에게 회수한 편지를 임의로 한 통씩을 나눠줄 때, 자신의 편지를 받은 이가 한 명도 없을 확률은 (사람이 아무리 많더라도) $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!} + \dots + (- 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!} + \dots + (- 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} = n D_{n - 1} + (- 1)^{n} for n \geq 2$ 는 더 멋지다.

다음의 사소한 내용은 흥미로울 수 있는 내용이다. 때때로 기호 “ $n!$ ”를 $n! = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) (n - k)! = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$ 로 정의하고 이를 “ $n$ subfractorial”이라 읽는다. 즉 $n! = D_{n}$ 으로 정의한다.

PIE Problems Ⅲ.

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

PIE Problems Ⅳ.

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

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

combinatorics counting Derangement Derangements enumerative combinatorics subfactorial 교란 교란순열 난순열 셈하기

PIE Problems Ⅲ.

PIE Problems Ⅳ.

특성함수를 이용한 포함-배제 원리의 증명

자연수의 분할

Leave a Comment Cancel Reply