|
이산수학 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. 개요
complete permutation · 完 全 順 列순열의 일종으로, 일렬로 배열한 대상들의 위치를 재조정했을 때, 모든 대상이 자기 위치에 있지 않도록 하는 배열 방법이다.
예를 들어 4명의 학생 [math(\rm A)], [math(\rm B)], [math(\rm C)], [math(\rm D)]가 시험을 치고, 서로 바꿔서[1] 채점을 한다고 생각해보자. 각각의 시험지를 [math(a)], [math(b)], [math(c)], [math(d)]라 명명했을 때, 수형도를 사용함으로써 그 경우의 수를 구해볼 수 있다.
이러한 배열을 완전 순열이라 한다.
2. 점화식과 일반항
1부터 [math(n)]까지의 자연수를 한 줄에 쓰고, 아랫줄에 한 줄 더 쓴다. 윗줄의 숫자들을 하나하나씩 대응할 때 자기 자신을 제외한 다른 숫자로 대응하면 된다. 이렇게 대응하는 방법의 수를 센 것을 [math(D_{n})]이라 하자.먼저 1을 2부터 [math(n)]까지 총 [math((n-1))]개의 자연수 중 하나로 대응해야 한다. 이때, 1이 [math(k)]에 대응된다고 할 때, 이후의 대응을 다음과 같이 나눌 수 있다.
- [math(k)]가 1에 대응되는 경우
- 1과 [math(k)]는 서로 짝을 이루었으므로 나머지 [math((n-2))]개를 교란하면 되므로 경우의 수는 [math(D_{n-2})]가 된다.
- [math(k)]가 1에 대응되지 않는 경우
- 이때는 1을 [math(k)]로 취급하면 나머지 [math((n-1))]개를 교란하면 되므로 경우의 수는 [math(D_{n-1})]이 된다.
한편, 각 경우에 대하여 [math((n-1))]개의 [math(k)]가 존재하므로
| [math(\begin{aligned} D_{n}=(n-1)(D_{n-1}+D_{n-2} ) \end{aligned})] |
이제 일반항을 구할 것이다. 그 전에 먼저 위 점화식을 아래와 같이 변형한다.
| [math(\begin{aligned} D_n - nD_{n-1} = -1 \times \{D_{n-1} - ( n-1 ) D_{n-2} \}\end{aligned})] |
| [math(\begin{aligned} a_{2}=D_2-2D_{1}=1 \end{aligned})] |
| [math(\begin{aligned} D_n - nD_{n-1} = (-1)^{n} \end{aligned})] |
| [math(\begin{aligned} \frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} = \frac{(-1)^{n}}{n!} \end{aligned})] |
| [math(\begin{aligned} \frac{D_{n}}{n!}=D_{1}+\sum_{k=2}^{n}\frac{(-1)^{k}}{k!} \end{aligned})] |
| [math(\begin{aligned} \frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}=0 \end{aligned})] |
| [math(\begin{aligned} D_{n}=\sum_{k=0}^{n}\frac{(-1)^{k}n!}{k!} \quad (n \geq 1) \end{aligned})] |
| [math(\begin{aligned} D_{n}=\sum_{k=2}^{n}(-1)^{k} {}_{n}{\rm P}_{n-k} \quad (n \geq 2) \end{aligned})] |
한편,
| [math(\begin{aligned} e^{x}=\sum_{k=0}^{\infty} \frac{x^k}{k!} \end{aligned})] |
| [math(\begin{aligned} \lim_{n \to \infty} \frac{D_{n}}{n!}=\frac{1}{e} \end{aligned})] |
위 일반항은 포함·배제의 원리로도 유도가 가능하다. [math(n)]개의 물체를 배열하는 경우의 수가 [math(n!)]이고 이 중 부동점의 개수가 [math(k)]개 이상인 배열의 개수는 [math({n!}/{k!})]개이므로 포함·배제의 원리를 적용하면 원하는 결과를 얻는다.
3. 몇몇의 값
- [math(D_{1}=0)]
- [math(D_{2}=1)]
- [math(D_{3}=2)]
- [math(D_{4}=9)]
- [math(D_{5}=44)]
- [math(D_{6}=265)]
- [math(D_{7}=1854)]
- [math(D_{8}=14833)]
- [math(D_{9}=133496)]
- [math(D_{10}=1334961)]
- [math(D_{11}=14684570)]
4. 예제
|
[문제] 네 사람이 각각 자신의 모자를 쓰고 있다가 벗어놓았다. 네 사람이 모자를 다시 썼을 때, 모두 다른 사람의 모자를 쓸 확률을 구하시오. |
- [풀이 보기]
- -----
네 사람이 다시 모자를 썼을 때, 자신이 받게 되는 것 포함한 모든 경우의 수는 [math(4!)]이다.
한편, 네 사람이 다른 모자를 쓸 경우의 수는 [math(D_4)]이다.
이상에서 구하고자 하는 확률은 다음과 같다.[math(\begin{aligned} \frac{D_{4}}{4!}=\frac{3}{8} \end{aligned})]
|
[추가 문제] 위 상황에서 한 사람만이 자신의 모자를 쓸 확률을 구하시오. |
- [풀이 보기]
- -----
이는 4명 중에 어떤 사람이 자신의 모자를 쓸 것인지 결정하고, 나머지 모자에 대해 완전 순열을 적용하면 된다. 따라서 구하는 경우의 수는[math(\begin{aligned} _{4}{\rm C}_{1} \times D_{3}=8 \end{aligned})]
이상에서 구하는 확률은[math(\begin{aligned} \frac{8}{4!}=\frac{1}{3} \end{aligned})]
5. 쓰면 안 되는 경우
|
|
| 2009학년도 10월 학평 수리 영역 25번 |
| 5명의 야구선수가 자신의 글러브와 배트를 각각 하나씩 상자에 넣은 후, 글러브와 배트를 하나씩 꺼낸다. 다음 두 조건을 모두 만족하도록 꺼내는 경우의 수를 구하시오. |
| 2010년 KMO 고등부 1차 수행평가 19번[정답] |
그러나 완전 순열은 2그룹에 대해서는 쓰는 것이 빠르고 편하지만. 3그룹 이상일 경우에는 함부로 쓰면 안 된다. 정확하게 말하면 두 번째 그룹까지는 완전 순열로 접근하는 것이 맞으나, 세 번째 그룹부터는 완전 순열의 cycle 조합에 대해서도 경우를 나누어야 한다. 대표적인 예시가 위 두 문제이다.
우선 학평 문제의 올바른 풀이를 검토해보자.
|
{{{#!folding【올바른 풀이】 모자걸이의 첫 번째 행에 거는 모자를 순서대로 [math(A - B - C - D)]로 하자. 이 경우 두 번째 행의 첫 번째 열에 거는 모자를 [math(B)]라 하면 두 번째 행에 올 수 있는 모자의 나열은 |
<table width=100%> [math(\begin{cases} B - A - D - C \\ B - C - D -A \\ B - D - A - C \end{cases})] |
[i] [math(B -D - A - C)]를 넣는 경우
세 번째 행에 올 수 있는 모자의 나열은
| [math(\begin{cases} C - A - D - B \\ D - C - B -A \end{cases})] |
[ii] [math(B - C - D -A)]를 넣는 경우
세 번째 행에 올 수 있는 모자의 나열은
| [math(\begin{cases} C - D - A - B \\ D - A - B -C \end{cases})] |
[iii] [math(B - A - D - C)]를 넣는 경우
세 번째 행의 앞의 2열은 [math(C)]와 [math(D)]가, 뒤의 2열은 [math(A)]와 [math(B)]가 올 수 있기 때문에
| [math(\begin{cases} C - D - A - B \\ C - D - B - A \end{cases} \quad \sf{or} \quad \begin{cases} D - C - A - B \\ D - C - B -A \end{cases})] |
따라서 두 번째 행의 첫 번째 열에 거는 모자를 [math(B)]라 할 때 올 수 있는 경우의 수는 [math(4+2+2=8)]가지가 된다.
두 번째 행의 첫 번째 열에는 [math(B)], [math(C)], [math(D)]가 올 수 있으므로 [math(3)]가지, 첫 번째 행에 거는 모자의 순열은 [math(4!=24)]
따라서 정답은 [math(8⋅3⋅4!=576)]가지이다.}}} ||
올바른 풀이를 통해 알 수 있겠지만, 완전 순열을 통해 풀 때 놓치는 부분이 하나의 순열에서 나오는 완전 순열에 대해 3번째 순열이 무조건 2가지가 나오는 것이 아니라는 점이다. 따라서, 3그룹 이상일 경우에는 함부로 완전 순열을 써서는 안 되고 올바른 풀이의 [iii]에 해당하는 부분을 잡아낼 수 있어야 한다.
경시대회를 접하여 Permutation cycle을 알고 있는 부류들은 왜 [iii]만 다른지를 눈치챌 수 있다. 두 번째 행에 거는 모자를 첫 번째 행에 거는 모자의 전단사함수, 즉 치환으로 판단하면 [i]과 [ii]는 하나의 4-cycle이 존재하는 경우이고, [iii]은 두 개의 2-cycle이 존재하는 경우이며, 고정점이 없는 관계로 1-cycle은 존재할 수 없으므로 4개짜리 완전 순열에서 발생할 수 있는 cycle 조합은 이 두 개가 전부이다.
cycle 조합이 같고 사이클에 들어가는 원소만 다른 두 순열에 대해서 대해서 세 번째 열에 올 수 있는 순열의 개수가 동일한 이유는 사이클 내부에 들어갈 원소만 다르게 해서 다시 생각해보면 결국 똑같은 경우가 되어 버리기 때문이다. 실제로 이 문제는 Permutation cycle을 고려하여 접근하는 것이 정석이고, 이는 확률과 통계 및 조합론에서 [math(f^n(x))]가 항등함수가 되는 일대일대응 [math(f)]의 개수 찾기’와 같이 permutation cycle을 사용하는 대표적인 예제로 자리잡았다.
6. 기타
- 완전 순열을 다루는 문제에서는, 그냥 [math(\boldsymbol{D_5})]까지는 외워두자. [math(D_5=44)]마저도 너무 많다고 하여 잘 나오지 않으며 [math(D_6=265)]부터는 경우의 수가 너무 많아지고 계산이 복잡해져 사실상 다루지 않는다고 보면 된다.
6.1. 언어별 명칭
| 한국어 | 한자 | 영어 |
| 완전 순열 | 完 全 順 列 | complete permutation |
| 교란 (순열) | 攪 亂( 順 列) | derangement |
| 교란수 | 攪 亂 數 | derangement number |
| 드몽모르 수 | - 數 | de Montmort number |
| 준계승 | 準 階 乘 | subfactorial |