순열

순열은 어떤 대상의 집합에서 몇 개를 골라 늘어놓을 때, 고르는 순서가 중요한 경우에 쓴다.

공식 이끌어 내기

순열의 전형적인 문제로 시작하자. 어느 마을에서 해마다 만두 먹기 대회가 열린다. 결승에 오른 선수는 모두 일곱 명이다. 이 일곱 명이 1등부터 3등까지를 차지하는 경우의 수를 구하시오.

이 문제에서는 순서가 중요하다는 것을 알아야 한다. 예를 들어 1등부터 3등까지가 민준, 서연, 지호라는 것을 알면, 이 세 명으로 서로 다른 순위가 모두 여섯 가지 생긴다.

• 민준, 서연, 지호
• 민준, 지호, 서연
• 서연, 민준, 지호
• 서연, 지호, 민준
• 지호, 민준, 서연
• 지호, 서연, 민준

이들은 모두 서로 다른 순위이다. 선수가 7명일 때 서로 다른 순위를 모두 몇 가지 만들 수 있는지 구해 보자.

이를 위해 곱의 법칙을 쓴다. (x₁, x₂, x₃) 꼴의 순서쌍을 고른다고 하자. 여기서 x₁은 1등을 한 선수이고, 나머지도 마찬가지이다. x₁에는 어떤 선수가 올 수 있을까? 모두 올 수 있으므로 x₁에는 선수 7명이 올 수 있다. x₂에는 어떤 선수가 올 수 있을까? 1등 자리에 이미 넣은 선수를 뺀 모두가 올 수 있으므로 x₂에는 7 − 1 = 6명이 올 수 있다. x₃에는 1등이나 2등이 아닌 선수가 올 수 있으므로 7 − 2 = 5가지이다. 곱의 법칙을 적용하면 경우의 수는 모두 7 · 6 · 5 = 210이다.

1등부터 4등까지의 경우의 수를 모두 알고 싶다면 x₄에는 7 − 3 = 4명이 올 수 있으므로 경우의 수는 모두 7 · 6 · 5 · 4 = 840이 된다. 여기서 무엇을 알 수 있을까?

원소가 n개인 집합(이 예에서는 선수 7명)에서 순서를 생각하며 3개를 고르면 결과는 n · (n − 1) · (n − 2)이다. 1등 자리에는 모두 올 수 있고, 그다음 자리에는 한 명 적게 올 수 있고, 나머지도 마찬가지이다. 여기서 원소가 n개인 집합에서 k개를 고를 때의 일반적인 공식을 이끌어 낼 수 있다. 경우의 수는 n · (n − 1) · (n − 2) · … · (n − k + 1)이다.

이 공식을 팩토리얼을 이용해 더 정리해 보자. 7의 팩토리얼 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1과, 메달을 받는 순위의 경우의 수를 구한 식 7 · 6 · 5를 비교하면 닮은 점이 보인다. 끝부분만 없애면 된다. 즉 7!을 4 · 3 · 2 · 1로 나누면 7 · 6 · 5만 남는다. 그러면 4 · 3 · 2 · 1은 얼마일까? 4!이다.

따라서 원소가 n개인 집합에서 순서를 생각하며 모두 k개를 고르는 경우의 수는 다음과 같다고 쓸 수 있다.

$${}_n{\mathrm{P}}_k=\frac{n!}{(n-k)!}$$

만두 먹기 대회의 값을 이 공식에 대입하면 다음과 같다.

$${}_7{\mathrm{P}}_3=\frac{7!}{(7-3)!}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{4\cdot 3\cdot 2\cdot 1}=7\cdot 6\cdot 5=210.$$

계산기

다음 계산기는 주어진 n과 k에 대한 순열의 수를 구해 준다.

풀이가 있는 예제

1. 만두 먹기 대회 이야기를 계속하자. 언제나 1등을 하는 실력자 준호가 대회에 왔다는 것을 안다면 메달을 받는 순위의 경우의 수는 어떻게 달라질까? 즉 선수가 7명이고 준호가 반드시 1등을 할 때 메달을 받는 순위는 몇 가지일까?

이것도 간단한 순열이다. 1등은 정해져 있으므로 나머지 선수 6명이 2등과 3등을 차지하는 방법만 정하면 된다. 즉 원소가 6개인 집합에서 2개를 고르는 순열이다.

$${}_6{\mathrm{P}}_2=\frac{6!}{(6-2)!}=30$$

2. 준호가 아직 그렇게 잘하지 못하던 오래전에는 늘 3등 안에 들었다. 선수가 7명이고 준호가 반드시 메달을 받을 때, 메달을 받는 순위는 몇 가지일까?

   이 예제는 준호가 몇 등을 했는지 모른다는 점에서 앞의 예제와 다르다. 2등을 했을 수도 있고, 지금도 부끄러워하는 3등을 했을 수도 있다. 그래서 준호가 1등을 한 경우, 은메달을 받은 경우, 동메달을 받은 경우의 세 가지 순열을 구해야 한다. 그런데 어느 경우든 다른 선수가 차지할 수 있는 자리는 두 개뿐이다. 예를 들어 준호가 2등이면 다른 선수들은 1등이나 3등을 할 수 있다. 즉 이번에도 6개에서 2개를 고르는 순열을 구하되, 준호의 세 가지 순위에 대해 세 번 구해야 한다. 순위의 경우의 수는 모두 다음과 같다.

   $$3\cdot {}_6{\mathrm{P}}_2=3\cdot \frac{6!}{(6-2)!}=3\cdot 30=90$$

   순열 앞의 3은 {}₃P₁로 쓸 수 있다는 것에 주목하자. 실제로는 원소가 세 개인 집합(메달을 받는 세 자리)에서 원소 하나(정해진 순위 하나)를 고르는 것이기 때문이다.

3. 어느 학교에 선생님이 모두 20명 있다. 곧 면접시험이 있어서 시험관으로 대표 시험관 한 명, 너그러운 시험관 한 명, 깐깐한 시험관 한 명을 정해야 한다. 경우의 수는 모두 몇 가지일까?

   먼저 순서가 중요한지 답해야 한다. 중요하다. 이번에도 선생님 세 명을 여섯 가지로 바꿔 배치할 수 있기 때문이다. 이제는 간단하다. 20개에서 3개를 고르는 순열이다.

   $${}_{20}{\mathrm{P}}_3=\frac{20!}{17!}=6840.$$

4. 숫자 {0, 1, 2, 3, 4, 5}로 같은 숫자를 두 번 쓰지 않고 세 자리 수를 몇 개 만들 수 있을까?

   순서가 중요할까? 그렇다. 123과 321은 다른 수이다. 서로 다른 세 숫자의 나열은 몇 가지일까? 6개에서 3개를 고르는 간단한 순열이다.

   $${}_6{\mathrm{P}}_3=\frac{6!}{3!}=120.$$

   하지만 첫째 자리가 0인 순열을 빼야 한다. 012는 세 자리 수가 아니기 때문이다. 이제 질문은 0으로 시작하는 나열이 몇 가지인가이다. 이때는 나머지 두 자리의 숫자만 바뀌므로((0, x₂, x₃) 꼴), 숫자 {1, 2, 3, 4, 5}로 두 숫자의 나열을 몇 가지 만들 수 있는지 구하면 된다. 이것도 간단하다. {}₅P₂ = 5!/3! = 20이다. 즉 0으로 시작하는 나열은 20가지이다.

   따라서 숫자 {0, 1, 2, 3, 4, 5}로 만든 세 자리 수는 모두 120 − 20 = 100개이다.

5. 숫자 {1, 2, 3, 4, 5}로 같은 숫자를 두 번 쓰지 않고 홀수인 세 자리 수를 몇 개 만들 수 있을까?

   123과 321은 다른 수이므로 순서가 중요하다. 홀수인 세 자리 수를 만들므로, 앞의 두 자리에는 아무 숫자나 올 수 있지만 마지막 자리에는 {1, 3, 5} 가운데 하나가 와야 한다. 먼저 다섯 숫자로 만들 수 있는 나열의 수를 모두 구한다. {}₅P₃ = 5! / 2! = 60이다.

   각 숫자는 마지막 자리에 같은 횟수만큼 오므로, 숫자가 5개이면 각 숫자가 마지막 자리에 60 / 5 = 12번씩 온다. 마지막 자리에 올 수 있는 숫자는 {1, 3, 5}의 세 개이므로, 1로 끝나는 수가 12개, 3으로 끝나는 수가 12개, 5로 끝나는 수가 12개이다. 합의 법칙을 쓰면 경우의 수는 모두 12 + 12 + 12 = 36이다.

6. {}_xP₂ = 72일 때 x를 구하시오. 다시 말해 원소가 x개인 집합에서 두 개를 순서대로 고르는데, 서로 다른 나열을 모두 72가지 만들 수 있다는 것을 안다. 나열을 고른 집합의 원소는 몇 개였을까? 식으로 풀어 쓰면 다음과 같다.

   $${}_x{\mathrm{P}}_2=\frac{x!}{(x-2)!}=72$$

   더 정리하면 다음과 같다.

   $$\begin{array}{rcl}\frac{x!}{(x-2)!}& =& 72\\ \frac{x\cdot (x-1)\cdot (x-2)!}{(x-2)!}& =& 72\\ x\cdot (x-1)& =& 72\\ x^2-x& =& 72\\ x^2-x-72& =& 0\end{array}$$

   이것은 전형적인 이차방정식이므로 판별식으로 풀거나 방정식을 다음 꼴로 바꿀 수 있다.

   $$(x+8)\cdot (x-9)=0$$

   여기서 해 x₁ = −8과 x₂ = 9를 바로 읽을 수 있다. 집합의 원소의 개수는 음수일 수 없으므로 음수인 해는 생각하지 않는다. 따라서 원래 방정식의 해는 x = 9이고, 집합의 원소는 아홉 개였다.