목걸이 순열이란?
목걸이 순열(염주 순열, 영어로는 bracelet arrangement, 일본어로는 '주즈(数珠)' 순열이라고도 합니다)은 서로 다른 n개의 물체를 닫힌 고리 모양으로 배열하는 서로 다른 방법의 수를 세는 것입니다. 이때 한 배열을 회전시키거나 또는 뒤집어서(거울 대칭) 다른 배열과 같아지면 둘은 같은 것으로 봅니다. 목걸이 순열은 원순열보다 한 단계 더 나아간 개념입니다. 원순열은 회전 대칭만 제거하지만, 목걸이 순열은 거울(반사) 대칭까지 함께 제거하기 때문입니다.
계산기 사용법
서로 다른 물체의 개수 n(0 이상의 정수)을 입력하면, 서로 다른 목걸이 배열의 수가 계산됩니다. 비교를 위해 일렬 순열의 수(\(n!\))와 원순열의 수(\((n-1)!\))도 함께 보여 줍니다. 팩토리얼은 값이 매우 빠르게 커지므로, 이 계산기는 임의 정밀도 정수 연산으로 정확하게 계산합니다. 따라서 n이 큰 값이어도 결과가 오차 없이 정확히 표시됩니다.
공식 풀이
n개를 일렬로 배열하는 경우의 수는 \(n!\)입니다. 고리 위에서 물체 하나를 고정해 n가지의 동일한 회전을 제거하면 \((n-1)!\)가지의 원순열이 남습니다. 목걸이 순열은 여기에 더해 시계 방향 배열과 그 반시계 방향 거울상을 같은 것으로 보므로, 한 번 더 2로 나눕니다.
$$P = \frac{(n - 1)!}{2}$$ (단, n ≥ 3일 때)
n = 0, 1, 2일 때는 위 공식을 그대로 적용하면 정수가 아니거나 개수가 부족해지므로, 관례적으로 이 세 경우의 답은 모두 1로 둡니다. 즉, 서로 다른 고리가 정확히 하나(또는 빈 고리 하나) 존재한다고 봅니다.
예제 풀이
n = 5일 때: $$\frac{(5 - 1)!}{2} = \frac{4!}{2} = \frac{24}{2} = 12$$ 가지의 서로 다른 목걸이가 됩니다. n = 6일 때: \(\frac{5!}{2} = \frac{120}{2} = 60\). n = 4일 때: \(\frac{3!}{2} = 3\).
자주 묻는 질문
원순열과는 어떻게 다른가요? 원순열은 \((n-1)!\)로, 회전은 같은 것으로 보지만 거울상은 서로 다른 것으로 봅니다. 목걸이 순열은 뒤집기(거울상)까지 같은 것으로 보기 때문에 여기에 2를 더 나눕니다.
n = 2일 때 답이 왜 1인가요? 물체가 두 개뿐이면 만들 수 있는 고리는 하나뿐입니다. 회전하거나 뒤집어도 두 위치가 서로 바뀔 뿐이라 모든 배열이 결국 같아집니다. 이 경우 \(\frac{(2-1)!}{2} = \frac{1}{2}\)라는 공식은 유효하지 않기 때문에 특수한 경우로 따로 처리합니다.
이 공식은 모든 물체가 서로 다르다고 가정하나요? 네. 이 계산기는 n개의 물체가 모두 서로 다르다고 가정합니다. 일부 물체가 같다면 가짓수는 더 줄어들며, 번사이드 보조정리나 폴리아 계산법 같은 다른 방법이 필요합니다.
