1708년, 프랑스 수학자 Pierre de Montmort는 모자를 맡겨둔 손님들이 돌아갈 때 모두 다른 사람의 모자를 받게 되는 경우의 수를 구하는 문제를 제시하고 본인이 해결했습니다. 이 문제는 arrangement와 상반되는 개념으로 derangement라고 합니다.(한국어로는 완전순열 또는 교란이라 합니다.) $n$개의 대상에 대한 derangement를 기호로 $D_n$, $d_n$, $!n$, $n¡$이라고도 쓰며, 함수 $n \mapsto !n$을 subfactorial이라고도 합니다.
점화식
subfactorial symbol은 가독성이 떨어지므로 여기서는 편의상 $d_n$이라는 기호를 사용하겠습니다. 그리고, 설명의 편의를 위해 배열할 대상을 $1$, $2$, $\cdots$, $n$이라는 숫자라고 가정하고, 이 숫자를 $(X_1, X_2, \cdots, X_n)$꼴의 순서쌍 모양의 칸에 넣는다고 하겠습니다. 그러면 우리가 원하는 배열은 $i= 1$, $2$, $\cdots$, $n$에 대해 $X_i \neq i$를 만족해야 합니다.
우선 $X_1 = k$의 $k$ 값으로 정할 수 있는 것은 $(n=1)$가지입니다. 그러면 $X_k = 1$ 또는 $X_k \neq 1$의 두 가지로 다음 상황을 분류할 수 있습니다.
Case 1: $X_k =1$인 경우
이 경우는 다음과 같이 그림으로 나타낼 수 있습니다.
그러면 나머지 $(n-2)$개의 숫자가 $X_i \neq i$를 만족하면 됩니다. 즉, 이 상황에서는 $d_{n-2}$가지의 경우가 생깁니다.
Case 2: $X_k \neq 1$인 경우
이 경우를 그림으로 나타내면 다음과 같습니다. $1$이 $k$번째 자리보다 왼쪽에 표시되어 있지만, 한 장의 그림으로 표시하기 위한 설정으로 $k$ 번째 자리가 아니라는 의미 이상을 가지지 않습니다.
그러면 $k$가 Case1, Case2로 구분하기 전에 설정된 수이므로 $k$와 관계된 부분을 삭제하고 다음과 같이 바꿔도 같은 문제를 푸는 상황이 됩니다.
즉, 이 상황에서는 $1 \le i \le n$, $i \neq k$에 대해 $X_i \neq i$를 만족하는 경우의 수를 구하는 것과 같습니다. 즉, $d_{n-1}$가지 경우가 생깁니다.
이 경우를 종합하면 다음과 같은 점화식이 얻어집니다. ($d_1 =0$, $d_2=1$) $$d_n = (n-1) \left( d_{n-1} + d_{n-2} \right) \quad n >2$$
일반항
이 수열의 일반항은 포함배제의 원리를 이용하여 직접 유도할 수도 있고(컴비네토릭스 또는 조합론 책에 유도가 되어 있습니다.), 수학적 귀납법을 이용해서 확인할 수도 있습니다. 다음 식은 모두 같은 것을 표현합니다.
- $\displaystyle{d_n = \sum_{i=0}^n {}_n {\mathrm C}_i (-1)^i (n-i)!}$
- $\displaystyle{d_n = \sum_{i=0}^n {}_n {\mathrm C}_i i! (-1)^{n-i}}$
- $\displaystyle{d_n = \sum_{i=0}^n {}_n {\mathrm P}_i (-1)^{n-i}}$
- $\displaystyle{d_n = n! \sum_{i=0}^n \frac {(-1)^i}{i!}}$
- $\displaystyle{ d_n = \left\langle \frac {n!} e \right\rangle = \left[ \frac{n!} e + \frac 1 2 \right]}$ ($n \ge 1$)
- $\displaystyle{d_n = \left[ \left( e + \frac 1 e \right) n! \right] - [en!] }$ ($n \ge 2$)
확률과의 관계
오일러가 작성했던 논문 중에는 이 derangement와 관계있는 것이 있습니다. 원문 그대로는 다르게 해석될 여지가 있어서 좀 바꿔서 정리하면, 일렬로 나열된 $n$개의 물건을 재배열했을 때 그 결과가 derangement가 될 확률의 극한은 $1/e$라는 것입니다. 즉,
