|
이산수학 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. 개요
permutation · 順 列어떤 집합의 원소들을 특정한 순서로 배열하는 것.
2. 종류
이 문서에서는 순열의 표기법으로 한국 수학 교육과정에서 차용한 [math({}_{n} \mathrm{P}_{r})](직순열), [math({}_{n}{\Pi}_{r})](중복 순열)을 사용하였다.2.1. 직순열
서로 다른 [math(n)]개의 원소에서 [math(r)](단, [math(0 < r \leq n)])개를 뽑아 순서에 상관있게 배열하는 것을 의미한다.예를 들어 1, 2, 3, 4, 네 가지 숫자들을 한 번 씩 사용하여 만들 수 있는 세 자리수 자연수의 개수를 구한다고 하자. 그럼 첫째 자리에는 4가지의 숫자가 올 수 있고, 둘째 자리에는 3가지의 숫자가, 셋째 자리에는 2가지 숫자가 올 수 있다. 이들을 뽑는 것은 잇달아 일어나는 일이므로 곱의 법칙을 사용하면, 그 경우의 수는 [math(4 \times 3 \times 2=24)]로 구할 수 있다.
이를 일반화하면, 서로 다른 [math(n)]개의 원소에서 [math(r)](단, [math(0 < r \leq 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} \mathrm{P}_{r} = {}_{n-1} \mathrm{P}_{r} + r \times {}_{n-1} \mathrm{P}_{r-1} )]
- [math({}_{n} \mathrm{P}_{r} = (n-r+1) \times {}_{n} \mathrm{P}_{r-1} \quad )](단, [math(1<r \leq n)])
자연수 범위에서 팩토리얼이 감마 함수와 동치[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)]이 된다.
따라서 이를 일반화하여 [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)]개의 원소를 순서에 상관있게 나열하는 것이다. 같포순(같은 것을 포함한 순열)[3], 동자 순열, 부분 중복 순열이라고도 부른다.예를 들어 세 개의 문자 [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})] |
2.4. 원순열
서로 다른 [math(n)]개의 원소를 원형으로 배열하는 것을 의미한다. 단, 회전하여 상태가 같다면, 같은 것으로 본다.[4]예를 들어 갑, 을, 정, 병, 네 사람이 원탁에 앉는 경우의 수를 구해보자. 얼핏 보기에는 4사람을 일렬로된 좌석에 앉히는 경우의 수 [math(4!)]과 같다고 생각할 수도 있다. 하지만 첫 문단에 주의를 준 바와 같이 회전하여 상태가 같다면 같은 것으로 취급을 하기 때문에 회전 대칭을 고려해주어야 한다.
위 문제에서는 다음과 같이 4가지에 대한 회전 대칭이 있다.
즉, 네 가지 경우에 대하여 '갑' 입장에서는 오른쪽에 '정', 왼쪽에 '을'이 앉아 있는 것이므로 이것은 같게 취급한다.
따라서 우리가 찾는 경우의 수는 [math(4!/4=6)]이 되는 것이다.
일반화 하여 [math(n)]개의 서로 다른 원소를 원형으로 나열하는 방법의 수는 다음과 같다.
| [math(\begin{aligned} \frac{n!}{n}=(n-1)! \end{aligned})] |
2.5. 같은 것이 있는 원순열[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. 염주 순열
2.7. 완전 순열
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 |
이후 상한과 하한을 찾는 문제로 변화하게 된다. 상한은
| [math(S_n\leq n!+(n-1)!+(n-2)!+(n-3)!+n-3)] |
| [math(S_n\geq n!+(n-1)!+(n-2)!+n-3)] |
하한을 증명하게 된 계기가 상당히 특이하다. 스즈미야 하루히의 우울 TVA(1기) 방영 당시 화수가 이리저리 뒤섞여 있었고, 바로 이 1기의 14화를 상상할 수 있는 순서대로 나열한 모든 방법으로 전부 볼 수 있는 최소의 열람수를 알고 싶어하는 질문이 4ch의 sci에 올라온 것에서 시작된 것이었다. 그래서 별명은 하루히 문제(Haruhi problem). 현재 하루히 문제의 원형에 해당하는 답([math(S_{14})])은 알려져 있지 않으나, 위에서 증명된 상한과 하한을 고려하면 938.8억회 이상 939.25억회 이하라는 것은 확실하다.
증명 과정에는 치환과 그래프 이론이 사용되었다. 초순열을 조금 변형하면 가중치를 부여한 그래프 형태로 환원이 가능하기 때문에 그래프 이론을 사용할 수 있었던 것.
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\cdots + i1.1049\cdots\cdots)]이 나온다.
# 그러나 이걸 직접 풀기는 매우 어려운데 링크에 나온 항등식 중 하나를 꼽아보면
[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] 특히 대학수학능력시험에서 원순열을 주제로 문제가 출제될 경우 이 조건을 문제에 명시한다. [5] 동자 원순열이라고도 한다. [6] [math(n^{\underline{r}})], [math((n)_r)]은 하강 계승이라는 이름으로 주로 불린다. [7] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다. 지수 꼴로 간략하게 표현할 수 있으니 세계적으로는 굳이 기호를 만들 필요성을 못 느낀 것. [8] 초등학교 때 한번쯤은 "[math(\left<0,\,1,\,2,\,3\right>)]중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다. 그래서 레이튼 시리즈에 수학 확통 문제가 난무하지만 초등학생이나 유치원생도 충분히 풀 수 있다.
[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] 특히 대학수학능력시험에서 원순열을 주제로 문제가 출제될 경우 이 조건을 문제에 명시한다. [5] 동자 원순열이라고도 한다. [6] [math(n^{\underline{r}})], [math((n)_r)]은 하강 계승이라는 이름으로 주로 불린다. [7] 일본에서도 쓰이는 걸 보면 일본에서 유래된 듯하다. 지수 꼴로 간략하게 표현할 수 있으니 세계적으로는 굳이 기호를 만들 필요성을 못 느낀 것. [8] 초등학교 때 한번쯤은 "[math(\left<0,\,1,\,2,\,3\right>)]중 [math(3)]개를 골라서 만들 수 있는 [math(3)]자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다. 그래서 레이튼 시리즈에 수학 확통 문제가 난무하지만 초등학생이나 유치원생도 충분히 풀 수 있다.