교란순열 요령

교란 순열

수(하)에 등장하는 경우의 수 문제에는 다음과 같은 문제가 있다.

네 명의 사람이 각각 자신의 우산을 하나씩 내어놓아 모으고, 하나씩을 가져갈 때, 4명 모두가 다른 사람의 우산을 가져갈 확률을 구하시오.

답은 9다.

선생님들께 여쭈어보니 하나하나 찾으라고 하셨다.

그런데 굉장히 규칙이 있을 것으로 보이기에,필자는 이 규칙을 작년 마지막 시험을 보기 1주일 앞서 찾아냈지만, 막상 시험 볼 때 긴장해서 못 풀었다. 나중에 조금 더 구체적인 공식을 만들어야겠다. 나중이 되어서도 까먹지 않는다는 가정 하에...

정의

한 집합의 원소들로 순열을 여러 번 시행하였을 때, 어떤 원소도 서로 일치하지 않는 순열이라고 볼 수 있다.
즉, 위 문제는 4명의 사람 배열과 우산 배열에서, 어떤 우산도 주인과 같은 위치에 배열되어서는 안 되는 것이다.

규칙

음이 아닌 정수 n, r에 대하여,
전체 선택 가능 경우의 수 : \(nCn*n!\)
- 제외해야 하는 경우의 수 : \(nC(n-1)*(n-1)!\)
+ 중복해서 제외한 경우의 수 : \(nC(n-2)*(n-2)!\)
- 다시 제외해야 하는 경우 : \(nC(n-3)*(n-3)!\)
+ 다시 중복해서 제외한 경우의 수 : \(nC(n-4)*(n-4)!\)
$\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot$    : \(nC(n-r)*(n-r)!\)
$\cdot\cdot\cdot\cdot\cdot\cdot\cdot$ 이렇게 계속해서 \(nC0*0!\) 이 나올 때까지 반복한다.

사실 이러한 요령은 노가다성이 강해서 4 이하의 경우에는 그냥 하나하나 세어보는 게 더 빠르다. 그러나 하나하나 세어보는 것의 복잡도는 O(n!!)처럼 기하급수적이지만, 위 규칙을 이용하면 복잡도는 O(n) 정도이다.