1. 문제 상황
갑자기 재밌는 문제가 떠올랐습니다.
\(n\)명의 사람들이 자리를 바꿔 앉으려고 합니다. 이 때 모두가 자기의 자리에는 앉지 않으면서, 자리를 바꿔 앉는 경우의 수를 \(a_{n}\)이라고 할 때, \(a_{n}\)은 얼마일까요?
2. 사람 수가 적을 때부터 생각해보기
\(n\)이 \(\mathbf{1}\)이면 바꿔 앉을 의자가 없기 때문에 0가지 입니다. (\(a_{1}=0\))
\(n\)이 \(\mathbf{2}\)이면 두 명이 서로 바꿔 앉는 방법 밖에 없기 때문에 1가지 입니다. (\(a_{2}=1\))
\(n\)이 \(\mathbf{3}\)일 때를 생각해봅시다. 일단 세 명이서 자리에 앉는 모든 경우를 생각해봅시다.
\(\left\{1, 2, 3\right\}\), \(\left\{1, 3, 2\right\}\), \(\left\{2, 1, 3\right\}\), \(\left\{2, 3, 1\right\}\), \(\left\{3, 1, 2\right\}\), \(\left\{3, 2, 1\right\}\)으로 총 6가지(\(3!\))입니다.
이 중 자기 자리에 있는 숫자를 찾아보면 다음과 같습니다.
\(\left\{{\color{red} 1}, {\color{Red} 2}, {\color{Red} 3}\right\}\), \(\left\{{\color{Red} 1}, 3, 2\right\}\), \(\left\{2, 1, {\color{Red} 3}\right\}\), \(\left\{2, 3, 1\right\}\), \(\left\{3, 1, 2\right\}\), \(\left\{3, {\color{Red} 2}, 1\right\}\)
남는 경우는 2가지 입니다. (\(a_{3}=2\))
\(n\)이 \(\mathbf{4}\)일 때는 어떨까요?
\(\left\{{\color{Red} 1}, {\color{Red} 2}, {\color{Red} 3}, {\color{Red} 4}\right\}\), \(\left\{{\color{Red} 1}, {\color{Red} 2}, 4, 3\right\}\), \(\left\{{\color{Red} 1}, 3, 2, {\color{Red} 4}\right\}\), \(\left\{{\color{Red} 1}, 3, 4, 2\right\}\), \(\left\{{\color{Red} 1}, 4, 2, 3\right\}\), \(\left\{{\color{Red} 1}, 4, {\color{Red} 3}, 2\right\}\),
\(\left\{2, 1, {\color{Red} 3}, {\color{Red} 4}\right\}\), \(\left\{2, 1, 4, 3\right\}\), \(\left\{2, 3, 1, {\color{Red} 4}\right\}\), \(\left\{2, 3, 4, 1\right\}\), \(\left\{2, 4, 1, 3\right\}\), \(\left\{2, 4, {\color{Red} 3}, 1\right\}\),
\(\left\{3, 1, 2, {\color{Red} 4}\right\}\), \(\left\{3, 1, 4, 2\right\}\), \(\left\{3, {\color{Red} 2}, 1, {\color{Red} 4}\right\}\), \(\left\{3, {\color{Red} 2}, 4, 1\right\}\), \(\left\{3, 4, 1, 2\right\}\), \(\left\{3, 4, 2, 1\right\}\),
\(\left\{4, 1, 2, 3\right\}\), \(\left\{4, 1, {\color{Red} 3}, 2\right\}\), \(\left\{4, {\color{Red} 2}, 1, 3\right\}\), \(\left\{4, {\color{Red} 2}, {\color{Red} 3}, 1\right\}\), \(\left\{4, 3, 1, 2\right\}\), \(\left\{4, 3, 2, 1\right\}\)
서로 다른 4개를 나열하는 24가지(\(4!\))에서 조건에 해당되지 않는 것들을 제외하면,
위와 같이 총 9가지 입니다. (\(a_{4}=9\))
3. 수가 많을 때는 어떨까?
그렇다면 \(n\)이 커지면 어떻게 해야할까요?
위에서 한 것처럼 \(n!\)에서 조건에 해당되지 않는 것들을 제외해봅시다.
\(a_{n} = n! - \left\{(_{n}C_{1} \times a_{n-1})+(_{n}C_{2}\times a_{n-2}) + \cdots +(_{n}C_{n-2}\times a_{2})+(_{n}C_{n-1}\times a_{1})+(_{n}C_{n}\times a_{0}) \right \}\)
\(_{n}C_{n}\)(모든 수가 자기 자리인 경우)은 1이고, 위 식이 성립하려면 \(a_{0}\)은 1이 되어야 합니다.
너무 복잡합니다. 더 쉬운 방법은 없을까요?
혼자 고민 끝에 인터넷에 검색을 해보았습니다.
이미 잘 정리된 자료들이 많아서 깜짝 놀랐습니다.
\(a_{n}\)은 두 가지 경우로 나눌 수 있습니다.
\(1\)이 \(i\) 번째 자리에 있을 때,
\(i\)가 첫 번째 자리에 있는 경우(\(1\)과 \(i\)가 자리를 바꾼 경우)와, 그렇지 않은 경우입니다.
먼저, \(1\)과 \(i\)가 서로 자리를 바꾼 경우의 수를 구해봅시다.
\(i\)는 \(1\)을 제외한 \((n-1)\)개이고, \(1\)과 \(i\)를 제외한 나머지 숫자들이 서로 다른 자리에 앉아야 합니다.
따라서, \((n-1) \times a_{n-2}\)입니다.
다음으로, \(1\)이 \(i\) 번째 자리에 있으면서 \(i\)가 첫 번째 자리에 있지 않은 경우의 수를 구해봅시다.
처음과 마찬가지로 \(i\)는 \((n-1)\)개입니다.
그리고 \(1\)은 \(i\) 번째 자리에 있지만, \(i\)는 첫 번째 자리에 있으면 안 됩니다.
다시 말해서 \(i\)가 있으면 안 되는 첫 번째 자리를 \(i\) 자신의 자리라고 말하면, \(i\)를 포함한 \(n-1\)개의 숫자들이 자신의 자리에 있지 않은 경우와 같습니다.
따라서, \((n-1) \times a_{n-1}\)입니다.
이 두 경우를 제외한 경우는 없으므로, \(a_{n} = (n-1) \times a_{n-2} + (n-1) \times a_{n-1}\)입니다.
4. 완전순열
이 문제를 풀기 위해 검색을 해보니 이 순열을 완전순열 또는 교란(순열)이라고 합니다.
그리고 완전순열의 수는 준계승, 영어로는 subfactorial(서브팩토리얼)이라고 합니다.
\(n\)개의 원소를 가진 완전순열의 준계승은 기호로 \(\mathbf{!n}\)으로 표현합니다.
\(!n\)의 점화식은 위에서 알아본 것과 같지만, 일반항을 구하는 방법은 저도 이해가 가지 않으므로 검색을 해보시길 추천드립니다.
5. 응용 문제
완전순열을 사용할 수 있는 상황들이 꽤 다양합니다.
제목에서와 마찬가지로 서로 자리를 바꿔 앉는 상황이 대표적입니다.
또 모자를 바꿔 쓰는 경우나 시험지를 바꿔서 채점하는 경우 등도 모두 완전순열을 알고 있다면 쉽게 해결할 수 있습니다.
6. 마치며
혼자서 처음 이 문제를 마주하면 해결을 위한 이런 기발한 아이디어를 떠올리는 것이 매우 어렵거나, 불가능할지도 모릅니다.
검색을 통해 완전순열이라는 것을 알았을 때, 제가 고민하는 것은 과거의 위대한 사람들이 이미 해결해두었을 것이라는 당연한 사실을 다시 떠올리게 되었습니다.
동시에 나는 난쟁이에 불과하지 않다는 사실을 다시금 깨달았습니다.
우리는 멀리 보기 위해, 거인이 되기보다 거인의 어깨 위에 서려는 자세가 필요합니다.
참고
https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4
