[퍼즐] 잘못된 주소 또는 엉뚱한 모자 문제

여기에 5개의 목적지가 다른 편지와 각각의 주소가 적힌 편지 봉투 5개가 있다.
실수로 모든 편지를 잘못된 주소로 보낼 경우의 수는 몇인가?

변형된 다른 문제는 7개의 모자와 7명의 모자 주인이 있는데, 모든 모자 주인들이
엉뚱한 모자를 가져갈 경우의 수는 몇인가?

이 문제를 처음 접한 지는 꽤 되었는데,
이것에 교란순열(derangement)이라는 수학용어가 있었다.
(예를 들어 n개가 모두 잘못된 위치로 놓이는 방법은 !n 으로  쓴다.)

이 문제의 답을 스스로 생각해 내는 것은 항상 헷갈린다.



(풀이) 크게 두가지 방법으로 풀수 있다. 1부터 n 까지의 숫자가 쓰인 n 개의 봉투와
편지를 생각하자.

첫번째 방법은 전체 경우의 수에서 하나라도 옳은 위치에 놓이는 경우를 빼는 것이다.
간단히 생각하면,
예를 들어 1번 편지가 옳은 위치에 올 경우, 나머지 편지의 경우의 수는 (n-1)!이 된다.
다른 편지가 옳은 경우를 생각하면, 모두 n 가지 다른 경우를 생각할 수 있다.
따라서, 하나라도 옳은 경우는 모두 n*(n-1)! = n! 이다. ???
뭔가 잘못되었다. 무엇이 잘못된 걸까?
이것은 다른 경우에 대해 n 을 곱해줄때, 겹쳐세는 경우들이 있기 때문이다.
구체적인 예를 들어서 생각해보자. 3개의 편지인 경우, 경우의 수 6가지 중, 1이 옳은 위치에 있는 경우는 (1,2,3)과 (1,3,2) 이다. 이제, 편지 2가 옳은 위치인 경우로 바꿔 생각하면,
(1,2,3)과 (3,2,1) 이 되고, 3이 옳은 위치인 경우는 (1,2,3)과 (2,1,3)이 된다. 따라서,
1이 옳은 위치인 경우의 수에 단순히 3을 곱하는 것은 (1,2,3)을 여러번 세는 셈이 된다.
이런식으로 여러개 옳은 위치에 있을 경우에 대해 겹쳐 세는 경우를 고려하면,

n! - (n! - (n!/2! - ( n!/3! - (n!/4! - .....  (n!/(n-1)! - n!/n!) ) ...))

을 계산해 주어야 한다. 결과는

!n = n! * sum_{k=0}^n (-1)^k/k!


두번째 방법은 교란 수열 D_n 을 가정하고, 일종의 귀납식을 만드는 것이다.

n 개의 편지가 있을 때,
이렇게 모두 잘못된 봉투에 들어가는 경우의 수를 D_n 이라고 하자.
여기서 하나의 A번째 편지를 정하고
이 편지가 잘못 들어간 봉투를 B 번째 봉투라고 하자.
그러면, 여기서 2가지 경우가 생긴다.

(1) B번째 편지도 A 번째 봉투에 들어가 있는 경우(서로 교차되는  경우)와
(2) B번째 편지는 A번째 봉투에 들어가지 않는 경우.

(1) 첫번째 경우에는 A번째와 B 번째 편지와 봉투가 서로 교차되어 있으므로,
나머지 n-2개 편지들이 잘못된 봉투에 들어갈 경우의 수는 D_{n-2} 라고 생각할 수 있다.

(2) 한편, A편지는 B 봉투에 이미 잘못 들어가 있고, B 편지는 A 봉투에 들어가지 않으므로,
A봉투를 이름을 바꿔서 B봉투라고 부르고, 남은 n-1개의 편지가 모두 잘못 들어갈
경우를 생각하는 것과 같으므로, D_{n-1}이 된다. (즉, 이 경우 n-1개의 편지에 대해 각각
정확히 하나의 봉투에는 들어가면 완되는 것과 같다. B편지는 A봉투에 들어가면 안된다.)

그러면,  처음에 A편지가 들어갈 수 있는 봉투의 경우는 n-1 이므로, 전체 경우의 수는

D_n = (n-1)*[ D_{n-1} +D_{n-2}]

라고 쓸 수 있다.
D_1=0, D_2=1 임을 쉽게 알 수 있다.

D_3=2*(0+1)=2
D_4=3*(2+1)=9
D_5=4*(9+2)=44
D_6=5*(44+9)=265
D_7=6*(265+44)=1854
..

가 된다.

이러한 수열을 교란 수열이라고 하고, 일반적으로

D_n=n! * sum_{k=0}^n (-1)^k/k!

로 구할 수 있다.
( 이를 증명하는 한가지 방법은 n 개의 수를 늘어 놓을 때 교란 순열이 되는 확률
P_n = D_n/ n! 을 생각하는 것이다. P_n 이 만족해야하는 귀납식을 구하여,
P_n = sum_{k=0}^n (-1)^k/k! 임을 보이면 된다.)