목걸이 순열이란?
목걸이 순열(영어로 necklace permutation, 일본어로는 '염주순열·珠順列')은 서로 다른 n개의 물건을 원형으로 배열하는 서로 다른 방법의 수를 세는 것입니다. 단, 한 배열을 원을 돌려서(회전) 또는 목걸이 전체를 뒤집어서(반사) 다른 배열과 일치시킬 수 있다면 둘은 같은 것으로 봅니다. 이는 회전만 같은 것으로 보는 원순열(circular permutation, 일본어 '원순열·円順列')과 구별되는 개념입니다. 목걸이 순열은 특정 국가에 국한된 규칙이 아니라 어디서나 동일하게 성립하는 보편적인 조합론 공식입니다.
계산기 사용법
n의 시작 값과 끝 값(각각 1~100 사이)을 입력하고, 표시할 정밀도를 유효숫자 단위로 선택하세요. 그러면 해당 범위 안의 각 정수 n마다 한 줄씩, 그에 해당하는 목걸이 순열의 개수가 표로 출력됩니다. 이 값은 팩토리얼 형태로 폭발적으로 커지기 때문에, 큰 값은 지정한 유효숫자 자리수에 맞춰 반올림한 지수 표기(과학적 표기법)로 보여주고, 정확히 표현 가능한 값은 전체 숫자 그대로 표시합니다.
공식 풀이
먼저 서로 다른 n개의 물건을 일렬로 늘어놓는 경우의 수는 \(n!\)가지입니다. 이를 원형으로 배치하면 어떤 배열이든 n번의 회전이 모두 같은 배열이 되므로, n으로 나누어 원순열의 수를 구합니다: \(n!/n = (n-1)!\). 그런데 목걸이는 뒤집을 수도 있어서 각 배열이 자신의 거울상과 짝을 이루므로, 여기에 2를 한 번 더 나눕니다:
$$N(n) = \dfrac{(n-1)!}{2}, \quad n = \text{Start } n \;\ldots\; \text{End } n$$n = 1 또는 n = 2일 때는 이 값이 정수가 되지 않으므로, 관례적으로 각각 정확히 1가지로 셉니다.
예제로 살펴보기
n = 3부터 8까지의 범위를 보면 다음과 같습니다. n=3은 \((3-1)!/2 = 2/2 = 1\); n=4는 \(6/2 = 3\); n=5는 \(24/2 = 12\); n=6은 \(120/2 = 60\); n=7은 \(720/2 = 360\); n=8은 \(5040/2 = 2520\). 기본 범위의 위쪽 끝인 n=30의 경우 \(29!/2 = 4{,}420{,}880{,}996{,}869{,}850{,}977{,}271{,}808{,}000{,}000\), 약 \(4.42 \times 10^{30}\) 입니다.
자주 묻는 질문
왜 2로 나누나요? 2로 나누는 것은 반사 대칭을 제거하기 위해서입니다. 목걸이는 뒤집어도 같아 보이므로, 같은 순환 순서를 시계 방향과 반시계 방향으로 본 두 경우를 한 번만 세는 것입니다.
왜 n=1과 n=2는 특별한가요? 일반 공식을 적용하면 두 경우 모두 0.5가 나오는데, 이는 개수로서 성립하지 않습니다. 하지만 기하학적으로는 물건이 1개나 2개일 때 배열 방법이 하나뿐이므로 1로 정합니다.
원순열과는 어떻게 다른가요? 원순열은 회전만 같은 것으로 보아 \((n-1)!\)가 됩니다. 반면 목걸이 순열은 반사(뒤집기)까지 허용하므로 \(n \geq 3\)일 때 \((n-1)!/2\)가 됩니다.
