여러 가지 순열과 중복조합

다섯 친구가 일렬로 서는 방법은 120가지인데, 둥근 탁자에 둘러앉는 방법은 24가지라고 한다. 같은 다섯 명인데 왜 다섯 배나 적을까? 또 서로 다른 구슬 다섯 개를 줄에 꿰어 목걸이를 만들면 12가지밖에 나오지 않는다. 한편 똑같은 사탕 6개를 세 사람에게 나누어 주는 방법은, 한 개도 못 받는 사람이 있어도 된다면 28가지이다. 같은 것끼리 바꾸어도 똑같아지는 경우를 어떻게 세면 이런 수가 나올까?

3.1.1돌려서 같으면 하나로 센다

원탁에는 첫째 자리와 마지막 자리가 없어서, 모두가 한 칸씩 옆으로 옮겨 앉아도 누가 누구 옆에 앉았는지는 그대로이다. 그래서 일렬로 선 120가지 배열을 원탁에 앉히면, 한 칸씩 돌린 다섯 배열이 모두 같은 앉음새가 된다. 따라서 원탁에 앉는 방법은 \(120/5 = 24\)가지이다. 다르게 생각하면, 한 사람을 먼저 아무 자리에 앉혀 기준으로 삼고 나머지 네 명을 그 사람에게서 시계 방향으로 일렬로 앉히는 것과 같아 \(4! = 24\)이다.

목걸이는 원탁과 달리 뒤집을 수도 있다. 목걸이를 뒤집으면 시계 방향의 배열이 시계 반대 방향의 배열로 바뀌지만 같은 목걸이이므로, 원순열 \(4! = 24\)가지를 다시 둘씩 묶어 \(12\)가지가 된다. 그래서 같은 것으로 보는 변환이 많아질수록 가짓수는 그 변환의 수로 나누어 줄어든다. 다만 뒤집어도 자기 자신과 같은 배열이 있으면 이렇게 나눌 수 없어 더 조심해서 세야 한다.¹

3.1.2사탕과 칸막이

똑같은 사탕 6개를 세 사람에게 나누는 방법은, 사탕 6개를 일렬로 놓고 그 사이에 칸막이 2개를 끼워 세 칸으로 나누는 방법과 하나씩 대응한다. 첫째 칸의 사탕은 첫째 사람, 둘째 칸은 둘째 사람, 셋째 칸은 셋째 사람이 받는다. 칸막이가 맨 앞이나 붙어 있으면 그 사람은 하나도 받지 못한다. 그래서 사탕 6개와 칸막이 2개, 모두 8개의 자리 가운데 칸막이 2개의 자리를 고르면 되므로 \({}_8\mathrm{C}_2 = 28\)가지이다. 이것이 \({}_3\mathrm{H}_6 = {}_{3 + 6 - 1}\mathrm{C}_6\)이다.

3.1.3예제 풀이

먼저 세 사람에게 하나씩 나누어 주면 남은 사탕은 3개이다. 이 3개를 아무 제한 없이 세 사람에게 나누는 방법은 \({}_3\mathrm{H}_3 = {}_5\mathrm{C}_3 = 10\)가지이다. 그래서 모두 적어도 하나씩 받는 방법은 10가지이다.

\(x + y + z = 6\)의 음이 아닌 정수해는 세 사람이 받는 사탕의 수와 같으므로 \({}_3\mathrm{H}_6 = 28\)개이다. 양의 정수해만 세면 위와 같은 10개이다. 즉 똑같은 것을 나누거나 중복을 허락해 고르는 경우는 칸막이를 놓을 자리를 고르는 조합으로 바뀌고, 돌리거나 뒤집어 같아지는 배열은 그 변환의 수로 나누어 센다. 그래서 무엇을 같은 것으로 보느냐를 먼저 정해야 가짓수를 바르게 셀 수 있다.

아래 탐구 카드에서 원탁에 앉는 방법을 일렬로 서는 방법과 비교하고, 목걸이와 사탕 나누기의 가짓수를 직접 세어 보자.

1. 돌리거나 뒤집어서 같아지는 배열을 정확히 세는 일반적인 방법은 번사이드 보조정리라 한다. 화학에서 분자의 이성질체를 세거나, 여러 색으로 칠한 정육면체가 몇 종류인지 셀 때 쓴다.