최근 수정 시각 : 2024-11-03 17:46:03

완전 순열

교란순열에서 넘어옴

이산수학
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. 몇몇의 값4. 예제5. 쓰면 안 되는 경우6. 기타
6.1. 언어별 명칭

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)]라 명명했을 때, 수형도를 사용함으로써 그 경우의 수를 구해볼 수 있다.

파일:namu_완전순열_예제.png
이러한 배열을 완전 순열이라 한다.

2. 점화식과 일반항

1부터 [math(n)]까지의 자연수를 한 줄에 쓰고, 아랫줄에 한 줄 더 쓴다. 윗줄의 숫자들을 하나하나씩 대응할 때 자기 자신을 제외한 다른 숫자로 대응하면 된다. 이렇게 대응하는 방법의 수를 센 것을 [math(D_{n})]이라 하자.

먼저 1을 2부터 [math(n)]까지 총 [math((n-1))]개의 자연수 중 하나로 대응해야 한다. 이때, 1이 [math(k)]에 대응된다고 할 때, 이후의 대응을 다음과 같이 나눌 수 있다.
  1. [math(k)]가 1에 대응되는 경우
    • 1과 [math(k)]는 서로 짝을 이루었으므로 나머지 [math((n-2))]개를 교란하면 되므로 경우의 수는 [math(D_{n-2})]가 된다.
  2. [math(k)]가 1에 대응되지 않는 경우
    • 이때는 1을 [math(k)]로 취급하면 나머지 [math((n-1))]개를 교란하면 되므로 경우의 수는 [math(D_{n-1})]이 된다.

파일:namu_완전순열_설명.png

한편, 각 경우에 대하여 [math((n-1))]개의 [math(k)]가 존재하므로
[math(\begin{aligned} D_{n}=(n-1)(D_{n-1}+D_{n-2} ) \end{aligned})]
가 그 점화식이 된다.[2]

이제 일반항을 구할 것이다. 그 전에 먼저 위 점화식을 아래와 같이 변형한다.
[math(\begin{aligned} D_n - nD_{n-1} = -1 \times \{D_{n-1} - ( n-1 ) D_{n-2} \}\end{aligned})]
이때 좌변을 [math(a_{n})]이라 놓으면, 우변은 [math(-1 \times a_{n-1})]이 되므로 수열 [math(\{a_{n}\})]은 공비가 [math(-1)]인 등비수열이다. 그런데
[math(\begin{aligned} a_{2}=D_2-2D_{1}=1 \end{aligned})]
이므로 [math(a_{n}=(-1)^{n})]이다. 이상에서
[math(\begin{aligned} D_n - nD_{n-1} = (-1)^{n} \end{aligned})]
양변을 [math(n!)]으로 나누면
[math(\begin{aligned} \frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} = \frac{(-1)^{n}}{n!} \end{aligned})]
이 점화식은 [math(b_{n}-b_{n-1}=f(n))] 꼴이므로 쉽게 일반항을 구할 수 있고, 이는 다음과 같다.
[math(\begin{aligned} \frac{D_{n}}{n!}=D_{1}+\sum_{k=2}^{n}\frac{(-1)^{k}}{k!} \end{aligned})]
한편, [math(D_{1}=0)]임을 기억하고,
[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(D_n)]은 [math({n!}/{e})]의 반올림 값임을 알 수 있다.

위 일반항은 포함·배제의 원리로도 유도가 가능하다. [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. 쓰면 안 되는 경우

파일:200910수리25번.jpg
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})]
3가지가 된다.


[i] [math(B -D - A - C)]를 넣는 경우
세 번째 행에 올 수 있는 모자의 나열은
[math(\begin{cases} C - A - D - B \\ D - C - B -A \end{cases})]
2가지가 된다.

[ii] [math(B - C - D -A)]를 넣는 경우
세 번째 행에 올 수 있는 모자의 나열은
[math(\begin{cases} C - D - A - B \\ D - A - B -C \end{cases})]
2가지가 된다.

[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})]
4가지가 된다.

따라서 두 번째 행의 첫 번째 열에 거는 모자를 [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


[1] 즉, 자신의 시험지는 채점하지 않늗다.[2] 여담으로, 팩토리얼도 위 점화식을 만족한다.[정답] 552

파일:CC-white.svg 이 문서의 내용 중 전체 또는 일부는 문서의 r119에서 가져왔습니다. 이전 역사 보러 가기
파일:CC-white.svg 이 문서의 내용 중 전체 또는 일부는 다른 문서에서 가져왔습니다.
[ 펼치기 · 접기 ]
문서의 r119 (이전 역사)
문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)

문서의 r (이전 역사)