염주순열

이산수학 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. 예제

3.1. 정육면체에 숫자 쓰기3.2. 직육면체에 숫자 쓰기

1. 개요

念珠順列 / norm of dihedral group

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

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

2. 공식

어떤 원순열을 뒤집으면 하나의 새로운 모양이 나온다. 다시 말해 원래 모양과 뒤집은 모양이 쌍을 이룬다. 곧, 뒤집어서 나오는 모양을 모두 같은 것으로 보는 염주순열에서는 한 쌍이 한 가지 경우의 수가 되므로 경우의 수는 원순열의 절반이다.

[math(n)]개의 서로 다른 구슬로 염주를 만드는 경우의 수는 [math(\dfrac{(n-1)!}2\;(n\geq 3))]이다.

그러나 위 식대로라면 [math(n=1)], [math(n=2)]인 경우에는 염주순열의 값이 [math(\boldsymbol{1/2})]이 되어 버리는 이상한 상황이 나온다. 실제로는 한 개 혹은 두 개의 구슬로 염주를 만드는 경우의 수는 [math(1)]임을 직관적으로 알 수 있는데, [math(1/2)]보다 크거나 같은 정수의 최솟값은 [math(1)]이기에 위 식에 최소 정수 함수를 취하면 하나의 예외도 없이 일반화되어 이 문제는 해결된다.

[math(n)]개의 서로 다른 구슬로 염주를 만드는 경우의 수는 [math(\left\lceil\dfrac{(n-1)!}2\right\rceil)]이다.

3. 예제

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

3.1. 정육면체에 숫자 쓰기

[문제]

정육면체의 각 면에 1, 2, 3, 4, 5를 적어도 한 번 쓰는 경우의 수를 구하시오.

[풀이 보기]: 다섯 개의 숫자를 적어도 한 번 쓴다면 어느 한 숫자는 두 번 써야 한다. 그렇다면 1을 두 번 쓰는 경우의 수를 구하고 5배를 하면 된다.

[1] 두 밑면에 1을 쓰는 경우
위아래로 뒤집어도 같으므로 염주순열로 간주하면 [math({(4-1)!}/2=3)]

[2] 인접한 두 면에 1을 쓰는 경우
1을 쓴 뒤 2를 쓰는 경우의 수는 1을 쓴 두 면과 모서리 하나를 공유하는 면에 쓰는 경우와 모서리 둘을 공유하는 면에 쓰는 경우 두 가지이다. 각 경우마다 나머지 숫자 3개를 배치하는 경우의 수 [math(3!)]이 있으므로 총 [math(2\times 3!=12)]

따라서 1을 두 번 쓰는 경우의 수는 [math(3+12=15)]이므로 구하는 전체 경우의 수는 [math(15\times 5=75)]

3.2. 직육면체에 숫자 쓰기