|
이산수학 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. 개요
순열의 일종.완전순열 또는 교란순열[1]은 사람들이 각각 자신의 모자를 벗었다가 아무 모자나 다시 쓰는데, 모든 사람이 자기 것이 아닌 모자를 쓰는 순열이라 할 수 있고, 이는 곧 치환에서 부동점[2]이 없는 경우를 가리킨다.[3] 그리고 모든 완전 순열의 수를 준계승 또는 교란수라고 하며, 이 개념을 처음 제시한 프랑스의 수학자 피에르 레몽 드몽모르(Pierre Raymond de Montmort)의 이름을 따 드몽모르 수라고도 한다.
기호로는 '교란'을 뜻하는 영단어 derangement의 머리글자를 따서 [math(D_n)], [math(d_n)] 또는 준계승을 의미하는 [math(!n)], [math(nchar161)] 등으로 나타낸다.
2. 언어별 명칭
| 한국어 | 한자 | 영어 |
| 완전순열 | 完 全 順 列 | complete permutation |
| 교란(순열) | 攪 亂( 順 列) | derangement |
| 교란수 | 攪 亂 數 | derangement number |
| 드몽모르 수 | - 數 | de Montmort number |
| 준계승 | 準 階 乘 | subfactorial |
3. 점화식과 일반항
[math(1)]부터 [math(n)]까지의 자연수를 한 줄 써 놓고, 아랫줄에도 한 줄 더 쓴다. 윗줄의 숫자들을 아랫줄의 숫자들로 하나하나씩 대응할 때 자기 자신을 제외한 다른 숫자로 대응을 하면 된다. 이렇게 대응하는 방법의 수를 센 것이 [math(D_n)]이다.먼저 [math(1)]을 [math(2)]부터 [math(n)]까지 총 [math((n-1))]개의 자연수 중 하나로 대응해야 한다. 이때 [math(1)]이 [math(k)]에 대응된다고 하면 이후의 대응을 아래의 두 가지 경우로 나눌 수 있다.
- [math(k)]가 [math(1)]에 대응되는 경우, [math(1)]과 [math(k)]는 서로 짝을 이루었고 나머지 [math((n-2))]개를 교란하면 되므로 그 경우의 수는 [math(D_{n-2})].
- [math(k)]가 [math(1)]에 대응되지 않는 경우, [math(k)]와 [math(1)]을 같은 것으로 취급해서 [math((n-1))]가지를 교란하는 경우와 같으므로 그 경우의 수는 [math(D_{n-1})].
점화식을 얻으면 일반항에 한 걸음 다가간 것이다. 매우 교묘하게도, 적절히 이항해서 위 점화식을 다음과 같이 변형해주고
[math(D_n - nD_{n-1} = - \left\{D_{n-1} - \left( n-1 \right) D_{n-2} \right\})]
좌변을 [math(a_n)]으로 놓으면, 우변은 [math(-a_{n-1})]이 되므로 수열 [math(a_n)]은 공비가 [math(-1)]인 등비수열이다. [math(a_2 = D_2 -2D_1 = 1)]이므로 [math(a_n= \left( -1 \right)^n)]이다. 따라서
[math(D_n - nD_{n-1} = \left( -1 \right)^n)]
로 정리할 수 있다.
이제 양변을 [math(n!)]로 나누면
[math(\dfrac{D_n}{n!} - \dfrac{D_{n-1}}{(n-1)!} = \dfrac{\left( -1 \right)^n}{n!})]
[math(\dfrac{D_n}{n!} = b_n)]라 놓으면 식은 [math(b_n - b_{n-1} = \dfrac{\left( -1 \right)^n}{n!})]이 되며 이는 전형적인 점화식 꼴이다. 하나씩 대입하면서 더해나가면
[math(\displaystyle b_n = b_1 + \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!})]
[math(\displaystyle \frac{D_n}{n!} = \frac{D_1}{1!} + \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!} = \sum_{k=2}^n \frac{\left( -1 \right)^k}{k!})]
이 되는데 [math(\dfrac{\left( -1 \right)^0}{0!} + \dfrac{\left( -1 \right)^1}{1!} = 0)]이므로 [math(k=0)]부터 더해나가도 된다. 결과적으로 일반항은 다음과 같다.
| [math(\displaystyle\ D_n = \sum_{k=0}^n \frac {n! \left( -1 \right)^k}{k!} \ (n \ge 1))] |
| [math(\displaystyle D_n = \sum_{k=2}^n {}_n{\rm P}_{n-k} \left( -1 \right)^k \ (n \ge 2))] |
또한 [math(\displaystyle e^x = \sum_{k=0}^\infty \frac{x^k}{k!})]이므로 [math(\displaystyle \lim_{n \to \infty} \frac{D_n}{n!} = \frac 1e)]이며 이를 통해 [math(D_n)]은 [math(\dfrac{n!}{e})]의 반올림 값임을 알 수 있다.
위 일반항은 포함·배제의 원리로도 유도가 가능하다. [math(n)]개의 물체를 배열하는 경우의 수가 [math(n!)]이고 이 중 부동점의 개수가 [math(k)]개 이상인 배열의 개수는 [math(\dfrac{n!}{k!})]개이므로 포함·배제의 원리를 적용하면 원하는 결과를 얻는다.
4. 항
앞서 말했듯이 완전순열은 '자기 모자 안 쓰는 경우의 수'라고 할 수 있다. 점화식으로 항을 구하기 위하여 처음의 두 항을 직접 구해 보자.사람이 하나이면 자기 모자를 자기가 쓰는 경우밖에 없으므로 당연히 [math(D_1=0)]이며, 사람이 둘이면 서로가 모자를 바꿔 쓰는 방법이 유일하므로 [math(D_2=1)]이다.
이제 점화식 [math(D_n= (n-1) \left( D_{n-1}+D_{n-2} \right))]를 이용하여 각 항을 구하면 된다.
[math(D_3=2(1+0)=2)]
[math(D_4=3(2+1)=9)]
[math(D_5=4(9+2)=44)]
[math(D_6=5(44+9)=265)]
[math(D_7=6(265+44)=1854)]
[math(D_8=7(1854+265)=14833)]
[math(D_9=8(14833+1854)=133496)]
[math(D_{10}=9(133496+14833)=1334961)]
[math(D_{11}=10(1334961+133496)=14684570)]
이처럼 [math(D_n)]의 값은 갈수록 급격히 커진다.
5. 예제
완전순열을 다루는 문제에서는, 그냥 [math(D_5)]까지는 외워두자. 차례대로 [math(0, 1, 2, 9, 44)]이다. [math(D_5=44)]마저도 너무 많다고 하여 잘 나오지 않으며 [math(D_6=265)]부터는 경우의 수가 너무 많아지고 계산이 복잡해져 사실상 다루지 않는다고 보면 된다.| 문제1: 네 사람이 각각 자신의 모자를 쓰고 있다가 벗어놓았다. 네 사람이 모자를 다시 썼을 때, 모두 다른 사람의 모자를 쓸 확률을 구하시오. |
|
| 문제2: 네 사람이 각각 자신의 모자를 쓰고 있다가 벗어놓았다. 네 사람이 모자를 다시 썼을 때, 한 사람만 자신의 모자를 쓸 확률을 구하시오. |
|
6. 쓰면 안 되는 경우
그러나 완전순열은 2그룹에 대해서는 쓰는 것이 빠르고 편하지만. 3그룹 이상일 경우에는 함부로 쓰면 안 된다. 정확하게 말하면 두 번째 그룹까지는 완전순열로 접근하는 것이 맞으나, 세 번째 그룹부터는 완전순열의 cycle 조합에 대해서도 경우를 나누어야 한다. 대표적인 예시가 2009년 10월 고3 학력평가 수리영역 가, 나형 공통 25번과 2010 KMO 고등부 1차 19번이다.이 문제에 대한 올바른 풀이는 다음과 같다.
|
올바른 풀이를 통해 알 수 있겠지만, 완전순열을 통해 풀 때 놓치는 부분이 하나의 순열에서 나오는 완전순열에 대해 3번째 순열이 무조건 2가지가 나오는 것이 아니라는 점이다. 따라서, 3그룹 이상일 경우에는 함부로 완전순열을 써서는 안 되고 올바른 풀이의 3)에 해당하는 부분을 잡아낼 수 있어야 한다.
경시대회를 접하여 Permutation cycle을 알고 있는 부류들은 왜 3)만 다른지를 눈치챌 수 있다. 두 번째 행에 거는 모자를 첫 번째 행에 거는 모자의 전단사함수, 즉 치환(Permutation)으로 판단하면 1)과 2)는 하나의 4-cycle이 존재하는 경우이고, 3)은 두 개의 2-cycle이 존재하는 경우이며, 고정점이 없는 관계로 1-cycle은 존재할 수 없으므로 4개짜리 완전순열에서 발생할 수 있는 cycle 조합은 이 두 개가 전부이다.
cycle 조합이 같고 사이클에 들어가는 원소만 다른 두 순열에 대해서 대해서 세 번째 열에 올 수 있는 순열의 개수가 동일한 이유는 사이클 내부에 들어갈 원소만 다르게 해서 다시 생각해보면 결국 똑같은 경우가 되버리기 때문이다. 실제로 이 문제는 Permutation cycle을 고려하여 접근하는 것이 정석이고, 이는 확률과 통계 및 조합론에서 ‘fn(x)가 항등함수가 되는 일대일대응 f의 개수 찾기’와 같이 Permutation cycle을 사용하는 대표적인 예제로 자리잡았다.
위의 방법에 주의를 기울여서 다음 문제도 풀어보도록 하자. 이 문제는 2010년 KMO 고등부 1차 수행평가 문제이며, 고려해야 할 대상이 4개에서 5개로 늘어났다는 것만 빼면 윗 문제와 차이점은 사실상 없다.[정답]
|
19. 5명의 야구선수가 자신의 글러브와 배트를 각각 하나씩 상자에 넣은 후, 글러브와 배트를 하나씩 꺼낸다. 다음 두 조건을 모두 만족하도록 꺼내는 경우의 수를 구하시오. (a) 누구도 자신의 물건은 하나도 꺼내지 않는다, (b) 각 선수가 꺼낸 글러브와 배트의 주인은 서로 다르다. |
[1]
그냥 '교란'이라고도 한다.
[2]
자기 자신으로 짝지어지는 경우
[3]
군론적으로 서술하자면, 집합 X의 치환군의 어떤 부분군 H가 X위에 충실한 작용(faithful action)을 가질 경우, H의 원소는 X의 완전순열이 된다.
[정답]
정답은 552이다.