※본 글에는 수식이 사용되었습니다. 모바일에서는 수식이 깨져 보이지 않을 수 있는 점 참고 바랍니다. 만일 수식이 깨져 보일 경우 데스크톱 모드를 사용하여 주시길 부탁드립니다.
본문에서 다룰 순열은 앞서 다루었던 순열들과 약간 다른 순열이다. 학생들이 이 순열을 부르는 이름은 상당히 다양하다. 본문에서는 완전순열이라는 이름을 사용할 것이다. 자, 지금부터 이 순열에 대해 알아보자.
완전순열
완전순열이란 모든 원소의 위치를 바꾸는 순열, 다시 말해 각 원소가 본래 있던 자리가 아닌 자리로 옮겨주는 순열이라는 뜻이다. 이 순열의 수를 구하려고 하면 정말 귀찮다. 필자는 이 순열의 수를 구할 때, 주로 단순한 노가다로 구하는 편이다. 모든 경우를 적어서. 시간도 오래 걸리고 귀찮은 작업이지만 꽤나 높은 정확도로 구할 수 있다. 필자는 이 방법으로 구하지만 본문에서는 원소가 2, 3, 4, 5개인 경우의 완전순열의 수를 각각 구해볼 것이다. 각 경우별로 노가다를 통해 구하는 방법은 접은 글에서 확인하기 바란다.
원소가 2개인 경우
원소가 2개인 경우에는 둘의 자리를 바꾸는 경우 뿐이므로 구하는 경우의 수는 1이다.
의자 a, b에 각각 세 사람 A, B가 앉아 있고, 이를 순서쌍 (A, B)로 나타낸다고 하자.
| (B, A) |
원소가 3개인 경우
먼저 A가 의자 a에 앉지 않으면서 세 사람 A, B, C가 앉을 수 있는 경우의 수를 구해주면
$$ {}_{2}\mathrm{C}_{1} \times 2! = 4 $$
이 중 B가 b에 앉거나 C가 c에 앉는 경우의 수는 2이므로 구하는 경우의 수는 4-2=2이다. 이 경우의 수를 다른 방법으로도 구할 수 있다. 필자 개인적으로는 이 방법이 훨씬 간편하고 빠르다고 생각한다.
위 그림을 보며 구하는 방법에 대해 알아보자. 먼저 이 경우는 다음 조건을 만족하는 함수 f의 개수를 구하는 방법과 동일하다.
| $$ f \text{: } X \to X $$ $$ X = \left\{ 1 \text{, } 2 \text{, } 3 \right\} $$ $$ f(x_{1}) = f(x_{2}) \to x_{1} = x_{2} $$ $$ \text{모든 } a \in A \text{에 대하여 } f(a) \ne a $$ |
먼저 다음과 같은 순환을 생각해보자.
1→2→3→1
이와 같이 순환시켜주면 함수 f는 항상 모든 a∈A에 대하여 f(a)≠a를 만족한다. 자, 지금 이 설명이 뭔 소린지 알아듣지 못하는 독자들이 있을 수 있다. 필요한 설명을 상당히 생략했기에 당연한 결과다. 여기서 알아들었으면 당신의 사고력은 정말 뛰어난 것이다. 이제 제대로 설명해 보겠다. 이 순환에서 화살표는 함수에서 말하는 정의역의 원소와 치역의 원소의 대응을 의미한다. 즉, 1은 2로, 2는 3으로, 3은 다시 1로 대응된다는 뜻이다. 이렇게 각 원소를 하나씩만 사용해서 순환을 유지해주면 결국 이 함수 f의 정의역의 부분집합 중 어떤 집합을 정의역으로 택하여 함수를 만들어도 절대로 항등함수는 나올 수 없게 된다. 따라서 이 순환의 개수가 곧 조건을 따르면서 우리가 만들 수 있는 함수의 개수라고 볼 수 있다. 자, 이 정도면 설명이 충분할 듯 싶다. 이 순환의 개수는 원순열에 의하여 결정되므로 구하는 경우의 수는
$$ \frac{3!}{3} = 2! = 2 $$
이후에도 동일한 방법을 사용하여 경우의 수를 구할 것이다.
이 경우의 수를 노가다를 통해 구하는 과정을 다음의 표로 정리할 수 있다. 먼저 의자 a, b, c에 각각 세 사람 A, B, C가 앉아 있고, 이를 순서쌍 (A, B, C)로 나타낸다고 하자.
| (C, A, B) | ||
| (B, C, A) |
따라서 구하는 경우의 수는 2이다.
접은 글을 보면 알겠지만 이 경우에는 노가다로 구하는 것도 꽤나 빠르다. 다만 아래에도 나오겠지만 원소의 숫자가 커질수록 노가다로 구하는 속도는 압도적으로 작아져 매우 비효율적이라 할 수 있다.
원소가 4개인 경우
위 그림을 보며 구하는 방법에 대해 알아보자. 이 경우는 다음 조건을 만족하는 함수 f의 개수를 구하는 방법과 동일하다.
| $$ f \text{: } X \to X $$ $$ X = \left\{ 1 \text{, } 2 \text{, } 3\text{, } 4 \right\} $$ $$ f(x_{1}) = f(x_{2}) \to x_{1} = x_{2} $$ $$ \text{모든 } a \in A \text{에 대하여 } f(a) \ne a $$ |
case 1)
이는 다음과 같은 순환으로 나타낼 수 있다.
1→2→1, 3→4→3
먼저 두 묶음을 분할하는 경우의 수를 구하면
$$ {}_{4}\mathrm{C}_{2} \times {}_{2}\mathrm{C}_{2} \times \frac{ 1 }{ 2! } = 3 $$
두 묶음 모두 경우의 수가 1이므로 (case 1)에서 구하는 경우의 수는 3이다.
case 2)
이는 다음과 같은 순환으로 나타낼 수 있다.
1→2→3→4→1
이 순환의 수는
$$ \frac{4!}{4} = 3! = 6 $$
따라서 구하는 경우의 수는 (case 1), (case 2)에 의하여 3+6=9이다.
먼저 의자 a, b, c, d에 각각 세 사람 A, B, C, D가 앉아 있고, 이를 순서쌍 (A, B, C, D)로 나타낸다고 하자. 이 경우의 수를 노가다를 통해 구하는 과정을 다음의 표로 정리할 수 있다.
| (D, A, B, C) | |||
| (B, A, D, C) | (C, A, D, B) | ||
| (B, C, D, A) | |||
| (B, D, A, C) | (C, D, A, B) | (D, C, A, B) | |
| (C, D, B, A) | (D, C, B, A) |
따라서 구하는 경우의 수는 9이다.
원소가 5개인 경우
위 그림을 보며 구하는 방법에 대해 알아보자. 이 경우는 다음 조건을 만족하는 함수 f의 개수를 구하는 방법과 동일하다.
| $$ f \text{: } X \to X $$ $$ X = \left\{ 1 \text{, } 2 \text{, } 3\text{, } 4 \text{, } 5 \right\} $$ $$ f(x_{1}) = f(x_{2}) \to x_{1} = x_{2} $$ $$ \text{모든 } a \in A \text{에 대하여 } f(a) \ne a $$ |
$$ \frac{3!}{3} = 2 $$
case 1)
이는 다음과 같은 두 순환으로 나타낼 수 있다.
1→2→3→1, 4→5→4
위 그림과 같이 두 그룹으로 분할하는 경우의 수를 구하면
$$ {}_{5}\mathrm{C}_{3} \times {}_{2}\mathrm{C}_{2} = 10 $$
3개가 묶여있는 그룹을 돌리는 경우의 수를 구하면
$$ \frac{3!}{3} = 2! = 2 $$
따라서 (case 1)에서 구하는 경우의 수는 10×2=20이다.
case 2)
이는 다음과 같은 순환으로 나타낼 수 있다.
1→2→3→4→5→1
이 순환의 수는
$$ \frac{5!}{5} = 4! = 24 $$
따라서 구하는 경우의 수는 (case 1), (case 2)에 의하여 20+24=44이다.
먼저 의자 a, b, c, d, e에 각각 세 사람 A, B, C, D, E가 앉아 있고, 이를 순서쌍 (A, B, C, D, E)로 나타낸다고 하자. 이 경우의 수를 노가다를 통해 구하는 과정을 다음의 표로 정리할 수 있다.
| (B, E, A, C, D) | |||
| (B, C, A, E, D) | (B, D, A, E, C) | ||
| (B, A, D, E, C) | (B, C, D, E, A) | ||
| (B, A, E, C, D) | (B, C, E, A, D) | (B, D, E, A, C) | (B, E, D, A, C) |
| (B, D, E, C, A) | (B, E, D, C, A) |
| (C, E, A, B, D) | |||
| (C, A, B, E, D) | (C, D, A, E, B) | ||
| (C, E, B, A, D) | |||
| (C, A, D, E, B) | (C, D, B, E, A) | ||
| (C, A, E, B, D) | (C, D, E, A, B) | (C, E, D, A, B) | |
| (C, D, E, B, A) | (C, E, D, B, A) |
| (D, E, A, B, C) | |||
| (D, A, B, E, C) | (D, C, A, E, B) | (D, E, A, C, B) | |
| (D, E, B, A, C) | |||
| (D, C, B, E, A) | (D, E, B, C, A) | ||
| (D, A, E, B, C) | (D, C, E, A, B) | ||
| (D, A, E, C, B) | (D, C, E, B, A) |
| (E, A, B, C, D) | (E, C, A, B, D) | (E, D, A, B, C) | |
| (E, D, A, C, B) | |||
| (E, C, B, A, D) | (E, D, B, A, C) | ||
| (E, D, B, C, A) | |||
| (E, A, D, B, C) | (E, C, D, A, B) | ||
| (E, A, D, C, B) | (E, C, D, B, A) |
따라서 구하는 경우의 수는 44이다.
글을 읽으며 잘 따라오다 보면 알겠지만 원소의 개수가 커질수록 이 순열의 수를 구하기 위해서 나눠야하는 경우는 점차 커지므로, 이 순열의 수를 구하는 것은 매우 귀찮다. 그래서 완전순열의 몇몇 경우에 대하여 경우의 수 값을 외우는 사람들이 종종 있다.1 이는 순전히 개인의 학습방법에 달린 부분이므로 독자들의 선택에 맡긴다.
나는 문제를 해결할 때
절대 아름다움에 대해 생각하지 않는다.
그러나 내가 일을 마쳤을 때
그 해결책이 아름답지 않으면
그것이 잘못된 것임을 안다.
-리차드 벅민스터 풀러
- 필자는 외우지 않았다. [본문으로]
'수학 > 고등학생을 위한 수학' 카테고리의 다른 글
| 확률과 통계(7) (0) | 2021.03.07 |
|---|---|
| 삼각함수(5) (0) | 2021.03.06 |
| 확률과 통계(5) (0) | 2021.03.04 |
| 확률과 통계(4) (0) | 2021.03.03 |
| 기하와 벡터(26) (0) | 2021.03.02 |
