3.3 영국인의 모자 문제(교란순열)

"파티에 참석한 $n$명의 영국인들이 모두 모자를 쓰고 왔다. 파티를 시작하기 전에 모자걸이에 모자를 걸어두었다. 참석자들은 다시 집으로 돌아갈 때, 쓰고 온 모자를 다시 쓰지 않는 경우는 몇 가지나 될까?" 

---

이 문제는$n$개의 숫자 $1, 2, \cdots, n$을 일렬로 나열한 것을 

   $a(1), a(2), \cdots, a(n)$

이라 할 때, $a(k)≠k$을 만족하는 경우의 수를 구하는 문제와 같다. 그리고, 이러한 순열을 '교란순열($D(n)$)'이라 하는데 좀 더 '일반화된 교란순열'은 다음과 같이 표현된다.

   $D(n,r,k), \ (0\leq k\leq r)$ 

 

$1\leq r\leq n$에 대하여 $r-$순열은 $1, 2, \cdots, n$에서 $r$개를 선택하여 배열한 것이다.

   $a(1), a(2), \cdots, a(r)$

이때, $a(i)=i \ (i=1,2\cdots,r)$이면 $i$에서 고정점을 갖는다고 말한다. 즉, $D(n,r,k)$는 정확히 $k$개의 고정점을 갖는 $r-$순열의 개수를 나타낸다. 

정의에 의해 

   $D(n)=D(n,n,0)$

으로 쓸 수 있다. '일반화된 포함과 배제의 원리'를 이용하여 $D(n,r,k)$에 대한 공식을 얻을 수 있으나, 여기서는 간단히 $D(n,n,0)$에 대해서만 생각해 본다. 

---

포함과 배제의 원리에 의해 기본적인 절차는 다음과 같다.

전체 순열의 개수 $n!$에서 하나의 항을 선택하여 고정하고 나머지를 무작위로 배열한 순열의 개수를 빼고, 다시 두 개의 항을 선택하여 고정하고 나머지를 무작위로 배열한 순열의 개수를 더하고, 다시 세 개의 항을 고정하고 나머지를 무작위로 배열한 순열의 개수를 더하고 하는 과정들을 마지막까지 반복하여 구할 수 있다.

 

이때, $S$를 '$r-$순열'들의 집합이라 하자. $S$의 원소들에 대한 $r$개의 성질들은 다음과 같이 정의된다.

 

"$S$의 원소 $a(1) a(2) \cdots a(n)$는 $a(i) = i (i=1,2,\cdots,n)$인 경우

그리고 오직 이 경우에만, [성질$(i)$]를 갖는다." 

 

그러면 정의에 의해 

   $D(n,n,0)=E(0)$

이다. 이때, 
   $\omega(t)=C(n,t)\cdot(n-t)!, \ (0\leq t\leq n)$
이다. 

따라서 
     $\begin{align} D(n) &= D(n,n,0) \\ \\ &= E(0) \\ \\ &= \omega(0)-\omega(1)+\omega(2)-\omega(3)+\cdots \\ \\&= n! - C(n,1)\cdot(n-1)! + C(n,2)\cdot(n-2)! - C(n,3)\cdot(n-3)!+ \cdots \\ \\ &= n! \left(1-\left(\frac{1}{1!}\right)+\left(\frac{1}{2!}\right)-\left(\frac{1}{3!}\right)+\cdots \right) \end{align}$
임을 알 수 있다.  

[참고] 

$n$개의 항을 무작위로 배열했을 때, 이 배열이 교란순열이 되는 확률은 $\displaystyle \frac{D(n)}{n!}$이다. 이 값의 극한$(n\rightarrow \infty)$의 구해보면 
  $\displaystyle lim_{n \rightarrow \infty} \frac{D(n)}{n!} = \frac{1}{e}$
로 알려져 있다. 위 식의 우변의 값은 $e^x$의 맥클로린 전개에서 $x=-1$을 대입한 값과 같음을 이용하였
다. 즉, $n$이 충분히 크다면 $n$명의 사람이 있고, 자신이 쓰고 온 모자를 쓰지 않을 확률은 근사적으로 $\frac{1}{e}$와 같다. 

이 장의 마지막 예제로 '부부 문제'를 소개한다. 
"남자와 여자가 교대로 앉고 임의의 아내는 자신의 남편 옆에는 앉지 않도록, $n(\geq3)$쌍의 결혼한 부부들을 원탁에 둘러앉히는 방법의 수를 구하여라." 

포함과 배제의 원리를 이용하여 심심할 때 풀어보자! 이것에 대한 풀이는 이 3장의 마지막 절에 첨부한다.