확률·통계염주순열#338

염주순열

Necklace Permutations

염주순열은 회전하거나 뒤집어 일치하는 목걸이 배열을 같은 것으로 센다. 서로 다른 구슬이 세 개 이상이면 원순열의 수를 둘로 나누며, 그 이유를 뒤집기 짝과 일렬로 읽는 2n가지로 보인다. 이웃 조건, 반복색과 작은 개수의 예외를 구별한다.

읽는 시간
약 7분
선수 개념
원순열

직관 — 목걸이의 앞뒤를 바꿔 놓는다

직관

잠금장치와 방향 표시가 없는 구슬 고리를 탁자 위에 놓아 보자. 고리를 들어 뒤집으면 시계 방향으로 읽히던 구슬 순서가 거꾸로 된다. 앞뒤를 구별하지 않는 목걸이라면 같은 물건이다.

구슬은 대상, 들어 돌리기와 뒤집기는 같은 것으로 볼 움직임이다. 이 글은 실제 제품 자료가 아닌 가상 구슬 배열을 다룬다. 원순열의 회전 조건에 뒤집기 조건을 더한다. 목걸이·팔찌·염주처럼 손에 들고 뒤집을 수 있는 고리가 모두 이 셈에 해당한다.

염주순열은 회전과 뒤집기를 모두 같게 센다

염주순열은 원형 배열에서 회전하거나 뒤집어 일치하면 같은 결과로 보는 순열이다. 먼저 서로 다른 구슬 nn개를 모두 한 번씩 쓰고 n≥3n\ge3인 정수인 경우를 다룬다. 잠금장치처럼 시작점을 구별하는 표시는 없다.

교과서도 목걸이처럼 돌리거나 뒤집어 일치하는 배열을 같게 보는 순열을 염주순열이라 하고, n≥3n\ge3일 때 그 수를 (n−1)!2\dfrac{(n-1)!}{2}로 나타낸다. 이 글은 이 수를 BnB_n이라 한다.

Bn=(n−1)!2(n≥3)(1)B_n=\frac{(n-1)!}{2}\qquad(n\ge3) \tag{1}

여기서 반사는 고리를 뒤집어 시계 방향의 순서를 반대로 읽는 움직임이다.

정의
기호이름원어뜻
nn구슬의 수number of beads공식에서는 서로 다른 구슬 n≥3n\ge3개
CnC_n원순열의 수circular permutation count회전만 같게 세는 수
BnB_n염주순열의 수bracelet count회전과 뒤집기를 같게 세는 수
A, B, C, D구슬 이름bead labels서로 다른 네 구슬

영어 자료는 회전만 구별하지 않는 배열을 necklace라고 부르기도 한다. 여기서는 국내 교과의 ‘염주순열’처럼 뒤집기도 같은 것으로 본다는 조건을 명시한다.

염주순열에서는 왜 정확히 두 원순열이 한 쌍일까?

서로 다른 구슬이 세 개 이상이면, 원순열 하나와 그것을 뒤집은 원순열은 서로 다르며 다시 뒤집으면 처음으로 돌아온다. 따라서 빠짐없이 두 개씩 짝지을 수 있다.

한 구슬 A를 위에 고정해 보자. A의 시계 방향 바로 옆 구슬과 반시계 방향 바로 옆 구슬은 서로 다르다. 뒤집으면 이 둘이 바뀌므로 A를 기준으로 읽은 순서가 원래와 같을 수 없다. 이때 다른 회전을 허용해도 A가 있는 위치를 다시 맞추면 같은 비교가 된다. 결국 염주 하나에 서로 다른 원순열이 정확히 두 개씩 대응하여 식 (1)이 성립한다.

네 구슬이면 원순열은 3!=63!=6가지이고, 다음처럼 셋으로 짝지어진다.

B4=3!2=62=3.(2)B_4=\frac{3!}{2}=\frac{6}{2}=3. \tag{2}
A를 위에 고정한 네 구슬 원순열 여섯 개를 세 쌍으로 배치했다. 각 줄의 오른쪽 고리는 왼쪽 고리를 가운데 점선에 비춘 모양이라 뒤집으면 일치하고, 서로 다른 세 줄은 다른 염주순열이다.
그림 1 A를 위에 고정한 네 구슬 원순열 여섯 개를 세 쌍으로 배치했다. 각 줄의 오른쪽 고리는 왼쪽 고리를 가운데 점선에 비춘 모양이라 뒤집으면 일치하고, 서로 다른 세 줄은 다른 염주순열이다. figures/reflection_pairs.py

그림 1의 점선이 뒤집는 거울이다. 첫 줄에서 A의 오른쪽에 있던 B가 비춘 고리에서는 왼쪽으로 가고, 왼쪽에 있던 D는 오른쪽으로 간다. 임의의 서로 다른 n≥3n\ge3개에 대해서는 A 양옆이 다르다는 앞 문단의 논증이 짝의 크기를 보장한다.

염주순열은 일렬 배열을 2n가지씩 묶어서도 센다

서로 다른 nn개의 일렬 배열 n!n!가지를 고리로 만들면, 염주 하나는 일렬 배열 2n2n가지로 읽힌다. 출발 구슬을 고르는 nn가지와 읽는 방향 2가지를 곱한 수다.

Bn=n!2n=(n−1)!2(n≥3)(3)B_n=\frac{n!}{2n}=\frac{(n-1)!}{2}\qquad(n\ge3) \tag{3}
서로 다른 네 구슬 염주 하나를 일렬로 읽은 여덟 가지. 윗줄은 각 구슬에서 시작해 시계 방향, 아랫줄은 같은 구슬에서 반시계 방향으로 읽었다. 일렬 배열 4!=24가지가 8개씩 묶여 염주는 3가지다.
그림 2 서로 다른 네 구슬 염주 하나를 일렬로 읽은 여덟 가지. 윗줄은 각 구슬에서 시작해 시계 방향, 아랫줄은 같은 구슬에서 반시계 방향으로 읽었다. 일렬 배열 4!=244!=24가지가 8개씩 묶여 염주는 3가지다. figures/reading_directions.py

그림 2의 여덟 기록은 모두 다르다. 출발 구슬이 다르면 첫 글자가 다르고, 출발이 같으면 둘째 글자가 출발 구슬의 양옆 두 구슬로 갈린다. 그래서 4!=244!=24를 8로 나눈 3이 식 (2)와 같다. 구슬이 두 개면 두 방향으로 읽은 기록이 같아져 묶음이 4개가 아니라 2개이므로, 식 (3)을 쓸 수 없다.

nn이 커지면 세 셈의 차이는 다음과 같다. n≥3n\ge3에서 염주순열은 원순열의 정확히 절반이다.

nn일렬 배열 n!n!원순열 CnC_n염주순열 BnB_n
1111
2211
3621
42463
51202412
672012060

염주순열은 구슬을 먼저 고른 뒤 배열할 수 있다

서로 다른 일곱 구슬에서 네 개를 골라 고리를 만든다고 하자. 구슬을 고르는 단계는 조합이고, 선택한 네 구슬의 고리를 만드는 단계는 식 (2)다. 서로 다른 구슬 집합은 같은 완성 고리가 될 수 없다.

7C4×3!2=7×6×53×2×1×3=35×3=105.(4){}_7C_4\times\frac{3!}{2} =\frac{7\times6\times5}{3\times2\times1}\times3 =35\times3=105. \tag{4}

이렇게 곱의 법칙을 쓰려면 어느 네 구슬을 골라도 같은 수의 배열이 가능한지 확인한다. 구슬별 방향이나 연결 금지 조건을 더하면 식 (4)를 그대로 쓸 수 없다.

염주순열에 이웃 조건이 있으면 뒤집어도 조건이 남는지 본다

이웃한다는 조건은 뒤집어도 그대로 남으므로, 조건을 만족하는 원순열끼리 다시 둘씩 짝지을 수 있다. 서로 다른 여섯 구슬로 A와 B가 이웃하는 염주를 만들면 24가지다.

A와 B를 한 묶음으로 보면 원순열은 묶음과 C·D·E·F의 다섯 단위에서 4!4!가지이고, 묶음 안 순서가 2!2!가지라 48가지다. 그림 3처럼 뒤집으면 묶음 안의 AB가 BA로 바뀌고 나머지 순서도 거꾸로 되지만, A와 B는 여전히 이웃한다. 그래서 48가지가 둘씩 짝지어진다.

4!×2!2=482=24.(5)\frac{4!\times2!}{2}=\frac{48}{2}=24. \tag{5}
A·B 묶음과 C·D·E·F로 만든 여섯 구슬 염주(왼쪽)와 그것을 점선에 비춘 모양(오른쪽). 묶음 안 순서와 나머지 순서가 함께 거꾸로 되지만 A와 B는 계속 이웃하므로, 이웃 조건을 만족하는 원순열 48가지가 둘씩 묶여 24가지다.
그림 3 A·B 묶음과 C·D·E·F로 만든 여섯 구슬 염주(왼쪽)와 그것을 점선에 비춘 모양(오른쪽). 묶음 안 순서와 나머지 순서가 함께 거꾸로 되지만 A와 B는 계속 이웃하므로, 이웃 조건을 만족하는 원순열 48가지가 둘씩 묶여 24가지다. figures/adjacent_block_flip.py

이웃하지 않는 염주는 전체 5!/2=605!/2=60가지에서 빼서 60−24=3660-24=36가지다. 반면 ‘B가 A의 시계 방향 바로 다음’ 같은 조건은 뒤집으면 반시계 방향이 되어 염주에서는 뜻이 정해지지 않는다. 방향이 들어간 조건은 원순열로 센다.

염주순열에서 같은 색이 반복되면 먼저 짝의 크기를 확인한다

반복색이 있으면 원순열을 무조건 둘로 나눌 수 없다. A색 두 개와 B색 두 개가 있고 같은 색의 구슬을 구별하지 않을 때, 회전만 같은 것으로 보면 AABB형과 ABAB형 두 가지다. 그림 4의 점선처럼 두 형은 각각 뒤집어도 자기 자신과 겹친다. 따라서 뒤집기를 허용한 뒤에도 두 가지가 남는다.

같은 색을 같은 문자로 적은 AABB형(위)과 ABAB형(아래). 오른쪽은 고리를 돌려 가며 위에서부터 시계 방향으로 읽은 서로 다른 기록으로 각각 4개와 2개다. 점선은 각 고리를 자기 자신과 겹치게 하는 뒤집기 축이다.
그림 4 같은 색을 같은 문자로 적은 AABB형(위)과 ABAB형(아래). 오른쪽은 고리를 돌려 가며 위에서부터 시계 방향으로 읽은 서로 다른 기록으로 각각 4개와 2개다. 점선은 각 고리를 자기 자신과 겹치게 하는 뒤집기 축이다. figures/repeated_bead_boundary.py

그림 4에서 2÷2=12\div2=1이라고 계산하면 틀린다. 같은 것이 있는 순열의 수 4!2! 2!=6\dfrac{4!}{2!\,2!}=6을 먼저 4로 나누는 것도 틀린다. 일렬 기록 6개가 4개와 2개로 나뉘어 묶음의 크기가 같지 않기 때문이다. 나누기로 세려면 모든 묶음의 크기가 같아야 하고, 반복색의 작은 경우는 회전 기록을 직접 나열해 센다.

핵심

염주순열은 서로 다른 n≥3n\ge3개를 모두 쓰고 회전과 뒤집기를 같게 볼 때 (n−1)!/2(n-1)!/2가지다. 뒤집기로 서로 다른 원순열이 정확히 두 개씩 짝지어진다는 조건이 나누기 2의 근거다.

염주순열에서 구슬이 한 개나 두 개면 어떻게 세나요?

구슬이 한 개 또는 서로 다른 두 개면 각각 한 가지다. 둘의 경우 A의 양옆이 서로 다른 구슬이라는 증명 조건이 성립하지 않으므로 식 (1)을 적용하지 않는다. 0!/20!/2나 1!/21!/2라는 반쪽 개수를 답으로 쓰지 않는다.

염주순열에서 잠금장치가 있으면 같은 공식을 쓰나요?

아니다. 잠금장치가 시작 위치를 정하면 회전을 같게 볼 수 없으므로 일렬 배열에서 출발한다. 서로 다른 네 구슬이면 일렬 배열 4!=244!=24가지다. 목걸이를 뒤집을 수 있으면 양쪽 끝에서 읽은 두 배열이 같아 24÷2=1224\div2=12가지이고, 앞뒤가 구별되면 24가지다.

팔찌를 만드는 경우의 수도 염주순열로 세나요?

그렇다. 돌리고 뒤집을 수 있는 고리라면 팔찌·목걸이·염주는 모두 염주순열로 센다. 서로 다른 구슬 20개를 모두 꿴 팔찌는 식 (1)에서 19!2\dfrac{19!}{2}가지다. 시작점을 정하는 표시가 있으면 앞의 잠금장치처럼 따로 센다.

염주순열의 흔한 오해

  • 원탁에 앉는 문제도 뒤집어 절반으로 세면 된다 — A를 기준으로 B가 시계 방향 이웃인지 반대쪽 이웃인지 다른 자리 배치다. 네 명의 원탁은 6가지이며, 염주 조건의 3가지와 구별한다.
  • 서로 다른 구슬 일곱 개 중 네 개를 고르는 수만 세면 끝이다 — 구슬을 고른 뒤에도 배열 조건을 확인해야 한다. 선택은 35가지이지만 각 선택에서 배열이 3가지이므로 식 (4)의 결과는 105가지다.

직접 해보기

모두 설명용 구슬 모형이며, 방향 표시와 잠금장치는 없다.

  1. 서로 다른 여덟 구슬을 모두 쓰는 염주순열의 수를 식 (1)과 식 (3)으로 각각 구하라.
  2. 서로 다른 여섯 구슬에서 네 개를 골라 만드는 염주순열은 몇 가지인가?
  3. 서로 다른 일곱 구슬을 모두 꿴 염주에서 A와 B가 이웃하는 경우와 이웃하지 않는 경우를 각각 구하라.
  4. 서로 다른 여섯 구슬을 같은 간격으로 꿴 염주에서 A와 B가 마주 보는 경우는 몇 가지인가?
  5. A색 두 개, B색 한 개, C색 한 개가 있다. 같은 색은 구별하지 않을 때 회전만 허용한 배열과 뒤집기도 허용한 배열을 각각 세어라. 나누기 2를 적용할 수 있는가?
답과 풀이
  1. 식 (1)로 7!/2=5040/2=25207!/2=5040/2=2520가지다. 식 (3)으로 8!/(2×8)=40320/16=25208!/(2\times8)=40320/16=2520으로도 같다.
  2. 6C4=15{}_6C_4=15로 구슬을 고르고, 네 구슬의 염주는 3!/2=33!/2=3가지다. 곱하면 15×3=4515\times3=45가지다.
  3. A·B 묶음과 나머지 다섯 구슬, 모두 여섯 단위의 원순열은 5!=1205!=120가지이고 묶음 안 순서가 2가지라 240가지다. 뒤집어도 이웃 조건이 남으므로 둘씩 짝지어 240÷2=120240\div2=120가지다. 전체 염주 6!/2=3606!/2=360가지에서 빼면 이웃하지 않는 경우는 360−120=240360-120=240가지다.
  4. A를 기준 자리에 두면 B는 맞은편 한 자리에 오고, 남은 네 구슬은 나머지 네 자리에 4!=244!=24가지로 놓인다. 마주 보는 조건도 뒤집어서 그대로 남으므로 24÷2=1224\div2=12가지다.
  5. 같은 것이 있는 일렬 배열은 4!/2!=124!/2!=12가지이고, 각 배열의 회전 기록은 서로 다른 4개씩이다. 회전만 허용하면 12÷4=312\div4=3가지(AABC, AACB, ABAC)다. 뒤집으면 AABC와 AACB가 겹치고 ABAC는 자기 자신과 겹쳐 염주는 2가지다. 3÷23\div2는 정수가 아니므로 나누기 2를 적용할 수 없다.

더 읽기

영상 노트

영상 노트
  • 00:00 고리를 뒤집고 시계 방향 순서가 바뀌는 것을 확인한다.
  • 00:30 A의 양옆을 비교해 서로 다른 두 원순열의 짝을 보인다.
  • 01:10 그림 1의 점선에 비춰 식 (1)을 네 구슬에 적용한 식 (2)를 확인한다.
  • 01:45 그림 2의 여덟 가지 읽기로 식 (3)을 유도하고 비교표를 읽는다.
  • 02:40 먼저 고르고 배열하여 식 (4)를 계산한다.
  • 03:15 그림 3에서 뒤집어도 이웃이 남는 것을 보이고 식 (5)를 계산한다.
  • 04:00 그림 4의 회전 기록 4개와 2개로 반복색 반례를 설명한다.

지도에서의 위치

순열확률·통계원순열확률·통계염주순열지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 일렬 배열을 2n가지씩 묶는 두 번째 유도와 n=1~6 원순열 비교표, 뒤집어도 남는 이웃 조건과 방향 조건의 구별, 반복색의 회전 기록 수가 4와 2로 다름을 보이는 도식 추가, 잠금장치 답을 뒤집기 허용 여부로 나눔, 반복색과 겹치던 질문을 팔찌 질문으로 교체, 연습을 여덟 구슬·이웃·마주 보기·반복색 새 유형 5문항으로 (에이전트 수정, 그림 2→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림