염주 순열

이산수학 Discrete Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all"	이론
<colbgcolor=#3CC> 기본 대상	수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률
다루는 대상과 주요 토픽
수열	등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수
조합	경우의 수(공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론
그래프	수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제

기타	P-NP 문제^미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설^미해결 · 콜라츠 추측^미해결 · 시행착오 (예상과 확인) · 불 논리 · 브라에스 역설
관련 문서	논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학	}}}}}}}}}

1. 개요2. 선수 지식3. 상세4. 같은 것이 있는 염주 순열5. 교육과정6. 기타

1. 개요

norm of dihedral group · 念珠順列

원순열을 그대로 뒤집었을 때, 같은 것은 하나로 보는 순열.

회전하는 것뿐 아니라 뒤집어서 나오는 모양까지 모두 같은 것으로 보아 경우의 수를 세는 순열이다. '목걸이 순열'이라고도 하는데, 염주, 목걸이, 팔찌 등은 뒤집는다고 하여 그 대상의 본질이 변하지는 않으므로 이러한 이름이 붙었다.

2. 선수 지식

염주 순열을 이해하려면 원순열에 대한 이해가 필요하다.

원순열은 회전하여 같은 것을 하나로 보는, 즉 회전 대칭성을 고려해줘야 하며, 서로 다른 [math(n)]개를 원형으로 배열하는 경우의 수는 다음과 같음을 해당 문서에서 논의했다.

[math(\begin{aligned} \frac{n!}{n}=(n-1)! \end{aligned})]

좌변의 분자의 [math(n!)]은 자리에 배치하는 경우의 수이고, 분모의 [math(n)]은 회전 대칭의 개수이다.

3. 상세

염주 순열에서는 위와 같이 뒤집어서 상태가 같다면, 하나로 취급한다.

따라서 이것을 구하려면, 원순열의 수를 구한 뒤 반전 대칭의 개수인 2를 나눠주면 된다. 즉, 어떤 원순열을 뒤집으면 하나의 새로운 모양이 나온다. 다시 말해 원래 모양과 뒤집은 모양이 쌍을 이룬다. 곧, 뒤집어서 나오는 모양을 모두 같은 것으로 보는 염주 순열에서는 한 쌍이 한 가지 경우의 수가 되므로 경우의 수는 원순열의 절반이다.

이상에서 서로 다른 [math(n)]개를 원형으로 배열하는데, 회전하거나 뒤집어서 같은 상태면 하나로 볼 때, 그 경우의 수는 다음과 같다.

[math(\begin{aligned} \frac{(n-1)!}{2} \quad (n \geq 3) \end{aligned})]

다만, [math(n=1)]이나 [math(n=2)]인 경우 그 경우의 수는 [math(1/2)]인데, 실제로 한 개 혹은 두 개의 구슬로 염주를 만드는 경우의 수는 1개임을 직관적으로 알 수 있다. 따라서 해당 경우까지 포괄하기 위해서 최소 정수 함수를 씌워 모든 [math(n)]에 대한 염주 순열 공식을 얻는다.

[math(\begin{aligned} \left\lceil\dfrac{(n-1)!}2\right\rceil \end{aligned})]

4. 같은 것이 있는 염주 순열

순열 문서로 부터 '같은 것이 있는 원순열'을 다뤘다. 이와 유사하게 염주 순열에도 '같은 것이 있는 염주 순열'이 있다.

'같은 것이 있는 원순열'과 같이 이 문제가 간단하지 않는다는 것을 예제를 통해 알아보자. 적색 구슬 4개와 청색 구슬 2개로 염주를 만든다고 하자. 그러면 다음의 과정을 거칠 것이다.

'같은 것이 있는 원순열'을 사용하여 구슬을 배치하는 경우의 수를 구한다: 3
2개의 반전 대칭의 수를 나눠준다: [math(\dfrac{3}{2})]

안타깝지만 이 예제에서도 자연수가 나오지 않는다.

이제 [math(\rm A)] 1개와 [math(\rm B)] 2개, [math(\rm C)] 2개에 대한 염주 순열의 개수를 구해보자.

같은 것이 있는 염주 순열은 위 그림의 (a)와 같이 선대칭인 경우와 (b)와 같이 선대칭이 아닌 경우 두 가지가 있다. (a)는 뒤집기 전과 후가 완전히 같으므로 반전 대칭이 1이다. 반대로 (b)는 반전 대칭이 2이다.

따라서 같은 것이 있는 염주 순열의 경우는 선대칭인 것의 경우(이하 '대칭')엔 2로 나눠주며, 선대칭이 아닌 경우(이하 '반대칭')엔 1로 나눠줘야 한다. 이상에서 그 경우의 수는 다음과 같다.

[math( \dfrac{\small{(\textsf{\# of antisymmetric cases})}}{2}+\small{(\textsf{\# of symmetric cases})} )]

우선 위 경우 가능한 원순열의 개수는 같은 것이 있는 원순열을 적용하는데, [math(\gcd{(1,\,2,\,2)}=1)]이므로 이것은 회전 대칭이 5인 것밖에 없으므로 그 경우의 수를

[math( \displaystyle \frac{5!}{1! \times 2! \times 2!}\times{1}{5}=6 )]

이다. 이는 대칭인 경우와 반대칭의 경우가 섞여 있을 것인데, 일반적으로 반대칭인 것의 개수가 세기 힘드므로 대칭인 경우를 먼저 센다. 이 예제에서 대칭인 경우는 아래와 같이 2개 나온다.

이에 따라서 반대칭인 개수는 [math(6-2=4)]이다. 이상에서 구하는 경우의 수는 아래와 같이 나오게 된다.

[math( \dfrac{4}{2}+2=4 )]

5. 교육과정

〈교육부 고시 제2015-74호 [별책 8] 수학과 교육과정〉 p. 97에서 ''염주순열'과 '같은 것이 있는 원순열'은 다루지 않는다.'로 명시하고 있으나 '간접적으로'는 다루고 있다. 그 대표적인 예는 '정(직)육면체에 숫자 쓰기(색칠하기)'이다. 일부 참고서와 교과서를 제외하면 해당 유형 문제는 거의 보이지 않는다.

6. 기타

'뒷면'을 고려한다는 점에서 이면군과 관계가 있다.