#!if 넘어옴1 != null
''''''{{{#!if 넘어옴2 == null
{{{#!if 넘어옴1[넘어옴1.length - 1] >= 0xAC00 && 넘어옴1[넘어옴1.length - 1] <= 0xD7A3
{{{#!if ((넘어옴1[넘어옴1.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴1[넘어옴1.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴1[넘어옴1.length - 1] < 0xAC00 || 넘어옴1[넘어옴1.length - 1] > 0xD7A3
은(는)}}}}}}{{{#!if 넘어옴2 != null
, ''''''{{{#!if 넘어옴3 == null
{{{#!if 넘어옴2[넘어옴2.length - 1] >= 0xAC00 && 넘어옴2[넘어옴2.length - 1] <= 0xD7A3
{{{#!if ((넘어옴2[넘어옴2.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴2[넘어옴2.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴2[넘어옴2.length - 1] < 0xAC00 || 넘어옴2[넘어옴2.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴3 != null
, ''''''{{{#!if 넘어옴4 == null
{{{#!if 넘어옴3[넘어옴3.length - 1] >= 0xAC00 && 넘어옴3[넘어옴3.length - 1] <= 0xD7A3
{{{#!if ((넘어옴3[넘어옴3.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴3[넘어옴3.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴3[넘어옴3.length - 1] < 0xAC00 || 넘어옴3[넘어옴3.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴4 != null
, ''''''{{{#!if 넘어옴5 == null
{{{#!if 넘어옴4[넘어옴4.length - 1] >= 0xAC00 && 넘어옴4[넘어옴4.length - 1] <= 0xD7A3
{{{#!if ((넘어옴4[넘어옴4.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴4[넘어옴4.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴4[넘어옴4.length - 1] < 0xAC00 || 넘어옴4[넘어옴4.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴5 != null
, ''''''{{{#!if 넘어옴6 == null
{{{#!if 넘어옴5[넘어옴5.length - 1] >= 0xAC00 && 넘어옴5[넘어옴5.length - 1] <= 0xD7A3
{{{#!if ((넘어옴5[넘어옴5.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴5[넘어옴5.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴5[넘어옴5.length - 1] < 0xAC00 || 넘어옴5[넘어옴5.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴6 != null
, ''''''{{{#!if 넘어옴7 == null
{{{#!if 넘어옴6[넘어옴6.length - 1] >= 0xAC00 && 넘어옴6[넘어옴6.length - 1] <= 0xD7A3
{{{#!if ((넘어옴6[넘어옴6.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴6[넘어옴6.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴6[넘어옴6.length - 1] < 0xAC00 || 넘어옴6[넘어옴6.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴7 != null
, ''''''{{{#!if 넘어옴8 == null
{{{#!if 넘어옴7[넘어옴7.length - 1] >= 0xAC00 && 넘어옴7[넘어옴7.length - 1] <= 0xD7A3
{{{#!if ((넘어옴7[넘어옴7.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴7[넘어옴7.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴7[넘어옴7.length - 1] < 0xAC00 || 넘어옴7[넘어옴7.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴8 != null
, ''''''{{{#!if 넘어옴9 == null
{{{#!if 넘어옴8[넘어옴8.length - 1] >= 0xAC00 && 넘어옴8[넘어옴8.length - 1] <= 0xD7A3
{{{#!if ((넘어옴8[넘어옴8.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴8[넘어옴8.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴8[넘어옴8.length - 1] < 0xAC00 || 넘어옴8[넘어옴8.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴9 != null
, ''''''{{{#!if 넘어옴10 == null
{{{#!if 넘어옴9[넘어옴9.length - 1] >= 0xAC00 && 넘어옴9[넘어옴9.length - 1] <= 0xD7A3
{{{#!if ((넘어옴9[넘어옴9.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴9[넘어옴9.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴9[넘어옴9.length - 1] < 0xAC00 || 넘어옴9[넘어옴9.length - 1] > 0xD7A3
은(는)}}}}}}}}}{{{#!if 넘어옴10 != null
, ''''''{{{#!if 넘어옴10[넘어옴10.length - 1] >= 0xAC00 && 넘어옴10[넘어옴10.length - 1] <= 0xD7A3
{{{#!if ((넘어옴10[넘어옴10.length - 1] - 0xAC00) % 28) == 0
는}}}{{{#!if ((넘어옴10[넘어옴10.length - 1] - 0xAC00) % 28) != 0
은}}}}}}{{{#!if 넘어옴10[넘어옴10.length - 1] < 0xAC00 || 넘어옴10[넘어옴10.length - 1] > 0xD7A3
은(는)}}}}}} 여기로 연결됩니다. #!if 설명 == null && 리스트 == null
{{{#!if 설명1 == null
다른 뜻에 대한 내용은 아래 문서를}}}{{{#!if 설명1 != null
{{{#!html 후한의 인물 순열}}}에 대한 내용은 [[순열(후한)]] 문서{{{#!if (문단1 == null) == (앵커1 == null)
를}}}{{{#!if 문단1 != null & 앵커1 == null
의 [[순열(후한)#s-|]]번 문단을}}}{{{#!if 문단1 == null & 앵커1 != null
의 [[순열(후한)#|]] 부분을}}}}}}{{{#!if 설명2 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단2 == null) == (앵커2 == null)
를}}}{{{#!if 문단2 != null & 앵커2 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단2 == null & 앵커2 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명3 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단3 == null) == (앵커3 == null)
를}}}{{{#!if 문단3 != null & 앵커3 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단3 == null & 앵커3 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명4 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단4 == null) == (앵커4 == null)
를}}}{{{#!if 문단4 != null & 앵커4 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단4 == null & 앵커4 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명5 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단5 == null) == (앵커5 == null)
를}}}{{{#!if 문단5 != null & 앵커5 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단5 == null & 앵커5 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명6 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단6 == null) == (앵커6 == null)
를}}}{{{#!if 문단6 != null & 앵커6 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단6 == null & 앵커6 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명7 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단7 == null) == (앵커7 == null)
를}}}{{{#!if 문단7 != null & 앵커7 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단7 == null & 앵커7 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명8 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단8 == null) == (앵커8 == null)
를}}}{{{#!if 문단8 != null & 앵커8 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단8 == null & 앵커8 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명9 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단9 == null) == (앵커9 == null)
를}}}{{{#!if 문단9 != null & 앵커9 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단9 == null & 앵커9 != null
의 [[#|]] 부분을}}}}}}{{{#!if 설명10 != null
, {{{#!html }}}에 대한 내용은 [[]] 문서{{{#!if (문단10 == null) == (앵커10 == null)
를}}}{{{#!if 문단10 != null & 앵커10 == null
의 [[#s-|]]번 문단을}}}{{{#!if 문단10 == null & 앵커10 != null
의 [[#|]] 부분을}}}}}}#!if 설명 == null
{{{#!if 리스트 != null
다른 뜻에 대한 내용은 아래 문서를}}} 참고하십시오.#!if 리스트 != null
{{{#!if 문서명1 != null
* {{{#!if 설명1 != null
후한의 인물 순열: }}}[[순열(후한)]] {{{#!if 문단1 != null & 앵커1 == null
문서의 [[순열(후한)#s-|]]번 문단}}}{{{#!if 문단1 == null & 앵커1 != null
문서의 [[순열(후한)#|]] 부분}}}}}}{{{#!if 문서명2 != null
* {{{#!if 설명2 != null
: }}}[[]] {{{#!if 문단2 != null & 앵커2 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단2 == null & 앵커2 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명3 != null
* {{{#!if 설명3 != null
: }}}[[]] {{{#!if 문단3 != null & 앵커3 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단3 == null & 앵커3 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명4 != null
* {{{#!if 설명4 != null
: }}}[[]] {{{#!if 문단4 != null & 앵커4 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단4 == null & 앵커4 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명5 != null
* {{{#!if 설명5 != null
: }}}[[]] {{{#!if 문단5 != null & 앵커5 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단5 == null & 앵커5 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명6 != null
* {{{#!if 설명6 != null
: }}}[[]] {{{#!if 문단6 != null & 앵커6 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단6 == null & 앵커6 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명7 != null
* {{{#!if 설명7 != null
: }}}[[]] {{{#!if 문단7 != null & 앵커7 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단7 == null & 앵커7 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명8 != null
* {{{#!if 설명8 != null
: }}}[[]] {{{#!if 문단8 != null & 앵커8 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단8 == null & 앵커8 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명9 != null
* {{{#!if 설명9 != null
: }}}[[]] {{{#!if 문단9 != null & 앵커9 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단9 == null & 앵커9 != null
문서의 [[#|]] 부분}}}}}}{{{#!if 문서명10 != null
* {{{#!if 설명10 != null
: }}}[[]] {{{#!if 문단10 != null & 앵커10 == null
문서의 [[#s-|]]번 문단}}}{{{#!if 문단10 == null & 앵커10 != null
문서의 [[#|]] 부분}}}}}}| 이산수학 Discrete Mathematics | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <bgcolor=#46786a> 이론 | |
| <colbgcolor=#46786a> 기본 대상 | 수학기초론(수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열(뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의(점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수(/공식) · 순열(완전 순열 · 염주 순열) · 치환 · 분할(분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기(해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리(파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오(예상과 확인) · 불 논리(격자) · 브라에스 역설 · 차분 · 포함-배제의 원리 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
順列 / permutation어떤 집합의 원소들을 각각 특정한 순서로 배열하는 것.
2. 종류
이 문서에서는 순열의 표기법으로 한국 수학 교육 과정에서 차용한 [math({}_n {\rm P}_r)](직순열), [math({}_n\Pi_r)](중복 순열)을 사용하였다.2.1. 직순열
서로 다른 [math(n)]개의 원소에서 [math(r)]개를 뽑아 순서에 상관있게 배열하는 것을 의미한다(단, [math(0 < r \le n)]).예를 들어 1, 2, 3, 4 네 가지 숫자들을 한 번씩 사용하여 만들 수 있는 세 자릿수 자연수의 개수를 구한다고 하자. 그럼 첫째 자리에는 4가지의 숫자가 올 수 있고, 둘째 자리에는 3가지의 숫자가, 셋째 자리에는 2가지 숫자가 올 수 있다. 이들을 뽑는 것은 잇달아 일어나는 일이므로 곱의 법칙을 사용하면, 그 경우의 수는 [math(4 \times 3 \times 2=24)]로 구할 수 있다.
이를 일반화하면, 서로 다른 [math(n)]개의 원소에서 [math(r)]개를 뽑아 순서에 상관있게 배열하는 방법의 수는(단, [math(0 < r \le n)])
| [math(\begin{aligned} n \times (n-1) \times (n-2) \times \cdots \times (n-r+1) \equiv {}_{n} \mathrm{P}_{r} \end{aligned})] |
| [math(\begin{aligned} {}_{n} \mathrm{P}_{r} = \frac{n!}{(n-r)!} \end{aligned})] |
순열의 경우 다음과 같은 성질이 있다.
- [math({}_{n} \mathrm{P}_{r} = n \times {}_{n-1} \mathrm{P}_{r-1} )]
- [증명]
[math(n \times {}_{n-1}P_{r-1} = n \times \frac{n-1!}{n-r!})]
[math(= \frac{n \cdot n-1!}{n-r!})]
[math(= \frac{n!}{n-r!})]
[math(= {}_nP_r)]
ii. [math({}_{n} \mathrm{P}_{r} = {}_{n-1} \mathrm{P}_{r} + r \times {}_{n-1} \mathrm{P}_{r-1} )]
- [증명]
[math(r \times {}_{n-1}P_{r-1} = r \times \frac{n-1!}{n-r!})]
[math(= \frac{r \cdot n-1!}{n-r!})]
[math({}_{n-1}P_r = \frac{n-r \cdot n-1!}{n-r!})]
[math({}_{n-1}P_r + r \times {}_{n-1}P_{r-1} = \frac{n-r \cdot n-1! + r \cdot n-1!}{n-r!})]
[math(= \frac{n \cdot n-1!}{n-r!})]
[math(= \frac{n!}{n-r!})]
[math(= {}_nP_r)]
iii. [math({}_{n} \mathrm{P}_{r} = (n-r+1) \times {}_{n} \mathrm{P}_{r-1} \quad )](단, [math(1<r \leq n)])
- [증명]
[math(n-r+1 \times {}_nP_{r-1} = n-r+1 \times \frac{n!}{n-r+1!})]
[math(= \frac{n-r+1 \cdot n!}{n-r+1!})]
[math(= \frac{n!}{n-r!})]
[math(= {}_nP_r)]
자연수 범위에서 팩토리얼이 감마 함수와 동치[1]라는 것을 이용해서
| [math({}_n{\rm P}_r = \dfrac{\Gamma ( n+1 )}{\Gamma ( n-r+1 )})] |
2.2. 중복 순열
서로 다른 [math(n)]개의 원소에 대하여 중복을 허용하여 [math(r)]개를 뽑아 순서 있게 나열하는 것을 의미한다. 여기서는 [math(n<r)]일 수 있다.예를 들어 4명의 학생이 분식점에 갔고, 사정상 라면과 우동 두 종류 중 하나만을 선택할 수 있다고 할 때, 이 학생들이 시켜 먹는 음식의 경우의 수는 라면과 우동 2종류를 중복을 허락하여 4개 뽑은 뒤 순서 있게 나열하는 경우의 수와 같다. 따라서 학생마다 2종류의 음식 선택권이 있으므로 그 경우의 수는 [math(2^4=16)]이 된다.
또 다른 예시로 MBTI도 있다. E vs I, N vs S, T vs F, J vs P순서로 양자택일을 네 번 하며 16가지 경우의 수가 있다. 즉 A와 B를 순서를 정해 네 번 고르는 것이므로 전형적인 중복순열 문제가 된다.
따라서 이를 일반화하여 [math(n)]종류의 원소에 대하여 중복을 허용하여 [math(r)]개를 뽑아 순서 있게 나열하는 경우의 수는 다음과 같다.
| [math(\begin{aligned} n^r \equiv {}_{n} \Pi_{r} \end{aligned})] |
[math(n<r)]의 경우를 허용하기 때문에 [math(n)]이 무엇인지, [math(r)]이 무엇인지 정확하게 판단할 필요가 있다. 이는 일반적으로 [math(n^r \neq r^n)]이기 때문이다.
0의 0제곱 문서에서도 다루지만, [math({}_0\Pi_0 = 0^0 = 1)]이다.
2.3. 동자 순열(부분 중복 순열)
용어 개정으로 현재는 '같은 것이 있는 순열'로 표기하며, 말 그대로 같은 것이 있는 [math(n)]개의 원소를 순서에 상관있게 나열하는 것이다. 속어로서 일명 같포순(같은 것을 포함한 순열)이라고도 한다.예를 들어 세 개의 문자 [math(a)], [math(a)], [math(b)]를 일렬로 나열하는 경우의 수를 찾아보자. 우선 같은 [math(a)]를 처리하기 위해 각각 [math(a_1)], [math(a_2)]라 명명하자. 그럴 경우 서로 다른 3개의 문자를 일렬로 나열하는 것이 되므로 [math(3!)]이 된다. 그러나, 실제로는 [math(a_1)], [math(a_2)]은 같기 때문에 구분 불가하다. 따라서 이것을 나열해 주는 경우의 수만큼 나눠주어야 우리가 찾는 경우의 수를 찾을 수 있다. 따라서 [math(3!/2!=3)]이 된다.
중복되는 것이 다른 종류로 여러 가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다. [math(a_1)]이 [math(P_1)]개, [math(a_2)]가 [math(P_2)]개, [math(\cdots)], [math(a_n)]이 [math({P}_n)]개 있을 때, 이를 일렬로 나열하는 경우의 수는
| [math(\begin{aligned} \frac{\displaystyle \biggl( \sum_{k=1}^{n} {P}_{k} \biggr)!}{\displaystyle \prod_{k=1}^n {P}_k!}=\dfrac{({P}_1 +{P}_2 +\cdots +{P}_n)!}{{P}_1! \times {P}_2! \times \cdots\times {P}_n!} \end{aligned})] |
| [math(\begin{aligned} \binom{\sum_{k=1}^{n} {P}_{k}}{P_1, P_2, \cdots, P_n} \end{aligned})] |
동자 순열은 같은 로마자가 많이 사용된 단어를 애너그램처럼 순서를 뒤섞을 때 가능한 모든 경우의 수를 구하라는 문제에서 주로 사용되며, 미국의 강 혹은 주 미시시피(Mississippi)가 대표적인 예시로 활용된다.
2.4. 원순열
서로 다른 [math(n)]개의 원소를 원형으로 배열하는 것을 의미한다. 단, 회전하여 상태가 같다면, 같은 것으로 본다.[3]예를 들어 갑, 을, 병, 정 네 사람이 원탁에 앉는 경우의 수를 구해보자. 얼핏 보기에는 네 사람을 일렬로 된 좌석에 앉히는 경우의 수 [math(4!)]와 같다고 생각할 수도 있다. 하지만 첫 문단에 주의를 준 바와 같이 회전하여 상태가 같다면 같은 것으로 취급하기 때문에 회전 대칭을 고려해야 한다.
위 문제에는 다음과 같이 4가지 회전 대칭이 있다.
즉, 네 가지 경우에 대하여 '갑'의 입장에서는 오른쪽에 '병', 왼쪽에 '을'이 앉아 있는 것이므로 이것은 같게 취급한다.
따라서 우리가 찾는 경우의 수는 [math(4!/4=6)]이 되는 것이다.
일반화하여 [math(n)]개의 서로 다른 원소를 원형으로 나열하는 방법의 수는 다음과 같다.
| [math(\begin{aligned} \frac{n!}{n}=(n-1)! \end{aligned})] |
2.5. 동자 원순열
같은 것이 있는 원순열이라고도 한다. 이번엔 [math(n)]개의 원소 중 같은 것이 있을 때 원형으로 배열하는 것을 다룬다.현재 '같은 것이 있는 원순열'은 대한민국 교육 과정에 포함돼 있지 않으며, 다른 순열과 달리 '같은 것이 있는 염주 순열'과 같이 난이도급에선 보스급을 자랑한다.
단순하게 생각하여 같은 것이 있는 순열의 원형 버전이라 생각할 수 있는데, 그 생각이 틀림을 증명하는 한 예를 들어보자.
이제 배고픈 여섯 명의 학생들을 위해 같은 종류의 라면 4개와 같은 종류의 우동 2개를 원탁에 배열할 것이다. 이때, 회전하여 같은 상태가 되면 같은 것으로 취급한다. 라면과 우동을 원탁에 배열할 수 있는 경우의 수를 구하자. 이 문제에 대해 깊게 생각하지 않으면 다음 과정을 거쳐 그 경우의 수를 구할 것이다.
- 우선 같은 것이 있는 순열을 적용하여 각 자리에 배치할 수 있는 경우의 수를 구한다: [math(\dfrac{6!}{4! \times 2!}=15)]
- 이제 6개의 회전 대칭이 생기므로 1에서 구한 경우의 수에서 이 수를 나눈다: [math(\dfrac{15}{6}=\dfrac{5}{2})]
이 문제를 다루기 위해선 우선 각각의 종류에 대한 개수의 최대 공약수를 구해보자. 위 경우는 [math(\gcd{(4,\,2)=2})]이다. 이제 이 최대 공약수의 약수를 구해보자. 1, 2로, 이는 회전 대칭이 [math((4+2)/1=6)]인 경우와 [math((4+2)/2=3)]인 경우로 나뉨을 의미한다.
우선 특수한 경우로 이 회전 대칭이 3이 되는 경우를 살펴보자. 라면을 [math(a)], 우동을 [math(b)]로 명명한다면,
| [math(\begin{aligned} aabaab \end{aligned})] |
| [math(\begin{aligned} \small{(\textsf{0 rotation})} \quad & aabaab \\ \small{(\textsf{1 rotation})} \quad & baabaa \\ \small{(\textsf{2 rotation})} \quad & abaaba \\ \small{(\textsf{3 rotation})} \quad & aabaab \\ \end{aligned})] |
따라서 전체 배열 방법의 수 [math(6!/(4! \times 2!))]에서 이 [math(3!/2!)]을 뺀 만큼의 배열은 회전 대칭이 6이고, [math(3!/2!)]만큼은 회전 대칭이 3이다. 따라서 옳게 구한 것은 아래와 같다.
| [math(\begin{aligned} \biggl( \frac{6!}{4! \times 2!}-\frac{3!}{2!} \biggr) \times \frac{1}{6} +\frac{3!}{2!} \times \frac{1}{3}= \mathbf{3} \end{aligned})] |
아주 특수한 경우로 최대 공약수가 1이라 해보자. 이 경우는 회전 대칭이 그 원소의 개수만큼 있는 경우만 있기 때문에 우리가 처음 시도한 방법, 같은 것이 있는 순열을 쓴 뒤 회전 대칭의 수로 나눠주는 방법을 사용해도 된다.
2.6. 염주 순열
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[염주 순열#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[염주 순열#|]] 부분을2.7. 완전 순열
#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[완전 순열#s-|]]번 문단을#!if 문단 == null & 앵커 != null
의 [[완전 순열#|]] 부분을2.8. 초순열
[math(n)]종류의 서로 다른 원소를 1개씩 뽑아내어 순서대로 나열한 순열의 수는 [math(n!)]이다. 그런데, 이렇게 만들어진 [math(n!)]개의 모든 순열을 전부 내포한 순열을, 그리고 그중에서도 길이가 최소인 순열을 생각할 수 있다. 이를 초순열이라고 한다.예를 들어서 3종류의 원소 [math(a)], [math(b)], [math(c)]를 이용한 순열은 [math(abc)], [math(acb)], [math(bac)], [math(bca)], [math(cab)], [math(cba)]의 6개가 된다. 이 여섯 개의 순열을 전부 내포한 최소 순열은 [math(abcabacba)]이고 그 길이는 9이다.
[math(n)]이 1부터 5까지일 때의 초순열의 최소 길이는 각각 다음과 같다. 초순열의 수열은 현재 [math(n=5)]까지만 밝혀져 있다. [math(n=6)]부터는 현재까지 발견된 초순열이 진짜로 최소 길이인지가 불명인데, 아래와 같은 문제가 생겼기 때문이다.
| <colbgcolor=#f2f2f2,#555555> [math(\boldsymbol{n})] | 1 | 2 | 3 | 4 | 5 |
| [math(\boldsymbol{S_{n}})] | 1 | 3 | 9 | 33 | 153 |
이후 상한과 하한을 찾는 문제로 변화하였다. 현재 최선의 상한은 2018년 증명돤 다음 식이다.
| [math(S_n\leq n!+(n-1)!+(n-2)!+(n-3)!+n-3)] |
현재 최선의 하한은 2011년 9월 17일에 증명된 다음 식이다.
| [math(S_n\geq n!+(n-1)!+(n-2)!+n-3)] |
증명 과정에는 치환과 그래프 이론이 사용되었다. 초순열을 조금 변형하면 가중치를 부여한 그래프 형태로 환원이 가능하기 때문에 그래프 이론을 사용할 수 있었던 것.
3. 기타
3.1. 교육 과정
- 대한민국 교육 과정상 다루는 순열은 '직순열', '중복 순열', '같은 것이 있는 순열'이다. '원순열'은 2022 개정 교육과정 이후로 일반계 고등학교 과정에서 제외되었다.
- 일본에서는 수학 A에서 순열과 조합을 배운다.
- 중국에서는 순열과 조합이 선수 2-3에 들어가 있고 선수 2는 이과만 배우는 과정이므로 이과 학생들만 '순열과 조합'을 배운다.
3.2. 기호 관련
- 우리나라에서는 직순열의 경우 [math({}_{n} \mathrm{P}_{r})]을 사용하나, 세계적으로는 [math({\rm P}(n, r))], [math(n^{\underline r})], [math((n)_r)][6] 또한 쓰인다.
- Wolfram Alpha의 경우
nPr과P(n, r)모두 인식한다. - [math({}_{n} \mathrm{P}_{r})]에서 [math(\rm P)]는 순열의 영어 명칭 permutation에서 따왔다.
- [math({}_{n} \mathrm{P}_{r})]을 [math(TeX)]상에서 입력하려면
{}_{n}{\rm P}_{r}을 사용하면 된다. - 중복 순열의 경우 [math({}_n\Pi_r)]이라는 표현을 쓰는데, 순열과 조합에서 쓰이는 비슷한 기호들과는 달리 출처 불명의 기호로[7], 세계적으로는 그냥 [math(n^r)]으로 나타낸다. 2015 개정 교육 과정 기준 교과서와 참고서에서는 두 표현이 같다고 병기하여 표시되어 있지만 해당 표현은 아직 완전히 사라지지 않았다.
3.3. 여담
- 뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다.[8] 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 다음 그림과 같이 5장의 카드에서 3장의 카드를 골라 순서대로 나열해 '세 자리로 된 문자'를 만드는 경우의 수는 몇 가지나 될까를 생각해 보면 풀이법을 간단하게 연상할 수 있다.
4. 관련 문서
[1] 즉, 감마 함수는 팩토리얼을 복소수 범위로 일반화, 엄밀히는 해석적 연속을 적용시킨 것이다. 그러나 실수부가 [math(0)]보다 작거나 같은 정수를 제외한다는 점은 여전히 동일하다.[2] 가령 인수에 각각 원주율과 허수 단위를 넣은 [math({}_\pi{\rm P}_i)]의 값을 구해보면, [math({}_\pi{\rm P}_i = 0.2977\cdots + i \, 1.1049\cdots)]이 나온다.# 그러나 감마 함수가 특수함수이기 때문에 참값을 다르게 표현하기란 불가능에 가깝다. 이 식은 최대한 참값을 구한다 해도 아래와 같은 식으로밖에 표현할 수 없다.
[math(\qquad \dfrac{\Gamma(\pi + 1)}{\Gamma(\pi - i + 1)})]
링크에 나온 항등식 중 하나를 꼽아보면
[math(\displaystyle \qquad {}_\pi{\rm P}_i = \exp\left(\int_0^1 \dfrac{i - ix + x^{1+\pi} - x^{(1-i)+\pi}}{(-1+x) \ln x}\,{\rm d}x\right))]
가 나오는데 이를 수치해로 구한다고 하더라도 어마무시한 계산 노가다를 수반한다. (단, [math(\exp{x} = e^x)].)[3] 특히 대학수학능력시험에서 원순열을 주제로 문제가 출제될 경우 이 조건을 문제에 명시한다.[4] 4chan에 저 공식을 올린 익명의 유저도 논문의 제1 저자 중 한 명으로 올랐다. 다만 신원을 알 길이 없기 때문에 익명으로 올라갔다.[5] 회당 24분쯤 되므로 모두 보는 데는 428만 년 정도 걸린다.[6] [math(n^{\underline{r}})], [math((n)_r)]은 하강 계승이라는 이름으로 주로 불린다.[7] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다. 지수 꼴로 간략하게 표현할 수 있으니 세계적으로는 굳이 기호를 만들 필요성을 못 느낀 것.[8] 초등학교 때 한 번쯤은 "[math(\left<0,\,1,\,2,\,3\right>)] 중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자릿수의 개수를 구하시오" 같은 문제는 풀어봤을 것이다. 그래서 레이튼 시리즈에 수학 확통 문제가 난무하지만 초등학생이나 유치원생도 충분히 풀 수 있다.[9] 추상 대수학의 군론에서 다루는 치환이다. 자기 자신에 대한 일대일 대응 함수를 모은 군을 대칭군이라고 하는데, 그 원소를 '치환'이라고 하며, 그 개수는 순열과 같다. 이는 함수의 일대일 대응이 조합론에서 일컫는 순열과 메커니즘이 동일하기 때문이다.
[math(\qquad \dfrac{\Gamma(\pi + 1)}{\Gamma(\pi - i + 1)})]
링크에 나온 항등식 중 하나를 꼽아보면
[math(\displaystyle \qquad {}_\pi{\rm P}_i = \exp\left(\int_0^1 \dfrac{i - ix + x^{1+\pi} - x^{(1-i)+\pi}}{(-1+x) \ln x}\,{\rm d}x\right))]
가 나오는데 이를 수치해로 구한다고 하더라도 어마무시한 계산 노가다를 수반한다. (단, [math(\exp{x} = e^x)].)[3] 특히 대학수학능력시험에서 원순열을 주제로 문제가 출제될 경우 이 조건을 문제에 명시한다.[4] 4chan에 저 공식을 올린 익명의 유저도 논문의 제1 저자 중 한 명으로 올랐다. 다만 신원을 알 길이 없기 때문에 익명으로 올라갔다.[5] 회당 24분쯤 되므로 모두 보는 데는 428만 년 정도 걸린다.[6] [math(n^{\underline{r}})], [math((n)_r)]은 하강 계승이라는 이름으로 주로 불린다.[7] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다. 지수 꼴로 간략하게 표현할 수 있으니 세계적으로는 굳이 기호를 만들 필요성을 못 느낀 것.[8] 초등학교 때 한 번쯤은 "[math(\left<0,\,1,\,2,\,3\right>)] 중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자릿수의 개수를 구하시오" 같은 문제는 풀어봤을 것이다. 그래서 레이튼 시리즈에 수학 확통 문제가 난무하지만 초등학생이나 유치원생도 충분히 풀 수 있다.[9] 추상 대수학의 군론에서 다루는 치환이다. 자기 자신에 대한 일대일 대응 함수를 모은 군을 대칭군이라고 하는데, 그 원소를 '치환'이라고 하며, 그 개수는 순열과 같다. 이는 함수의 일대일 대응이 조합론에서 일컫는 순열과 메커니즘이 동일하기 때문이다.