양의 정수 $n \in \mathbb{N}$에 대하여 $n$의 \defn{계승}{factorial} $n!$을 \[ n! = n \times (n-1) \times \cdots \times 2 \times 1 \] 으로 정의한다. 특별히 $0! = 1$이라고 약속한다.

$ $

정리 1.2.1. 순열_{(permutation)}

서로 다른 $n$개에서 서로 다른 $r$개를 선택하여 일렬로 나열나는 것을 순열_{(permutation)}이라 하고 ${}_{n}P_{r}$로 나타낸다. $n \geq r$일 때, \[ {}_{n}P_{r} = n(n-1)(n-2) \cdots (n-r+1) = \frac{n!}{(n-r)!} \] 이다. 특히 서로 다른 $n$개를 일렬로 나열한 순열의 수는 ${}_{n}P_{n} = n!$이다.

$ $

예제 1.2.2.
Q. 자릿수가 모두 다르고 $1$은 반드시 포함하는 네 자리 양의 정수의 개수를 구하여라.
A. 두 가지 경우로 나누어 생각해 보자.

• $1$이 천의 자리에 들어가는 경우: \[ 1 \; \underline{\phantom{0}} \; \underline{\phantom{0}} \; \underline{\phantom{0}} \quad \to \quad {}_{9}P_{3} = 504\text{가지} \]
• $1$이 천의 자리에 들어가지 않는 경우: \begin{align*} & \underline{\phantom{0}} \; 1 \; \underline{\phantom{0}} \; \underline{\phantom{0}} \quad \to \quad 8 \times {}_{8}P_{2} = 448\text{가지} \\[1ex] & \underline{\phantom{0}} \; \underline{\phantom{0}} \; 1 \; \underline{\phantom{0}} \quad \to \quad 8 \times {}_{8}P_{2} = 448\text{가지} \\[1ex] & \underline{\phantom{0}} \; \underline{\phantom{0}} \; \underline{\phantom{0}} \; 1 \quad \to \quad 8 \times {}_{8}P_{2} = 448\text{가지} \end{align*}

각 사건은 동시에 일어나지 않으므로 전체 경우의 수는 \[ 504 + 3 \times 448 = 1848. \tag*{$\myblue{\square}$} \]

$ $

예제 1.2.3.
Q. $12$명의 학생들이 다음과 같은 모양에 책상에 앉는 경우의 수를 각각 구하여라.

$ $

$ $

A.

1. $12$명의 학생들을 일렬로 나열하는 경우의 수는 $12!$이다. 이 중 각각의 경우가 $4$번씩 중복되므로, 구하고자 하는 경우의 수는 $\dfrac{12!}{4}$.
2. $12$명의 학생들을 일렬로 나열하는 경우의 수는 $12!$이다. 이 중 각각의 경우가 $2$번씩 중복되므로, 구하고자 하는 경우의 수는 $\dfrac{12!}{2}$. $ $

$ $

정리 1.2.4. 중복순열_{(permutation with repetition)}

서로 다른 $n$개에서 중복을 허락하여 $r$개를 선택하여 일렬로 나열하는 것을 중복순열_{(permutation with repetition)}이라 하고 ${}_{n}\Pi_{r}$로 나타낸다. \[ {}_{n}\Pi_{r} = n^{r}. \]

$ $

예제 1.2.5.
Q. $A,\, B,\, C$가 각각 $8$개씩 있다고 하자. 이 중에서 $10$개의 문자로 이루어진 단어의 개수를 구하여라.
A. $A,\, B,\, C$로만 이루어진 $10$자리 단어의 개수는 총 ${}_{3}\Pi_{10} = 3^{10}$개이다. 이 중에서 $A,\, B,\, C$가 $9$번 이상 쓰인 단어의 개수를 제외해야 한다. 먼저 $A$가 $9$번 쓰인 단어의 개수는 $20$가지이고, $A$가 $10$번 모두 쓰인 단어의 개수는 $1$가지이다. 마찬가지로 $B$와 $C$에 대해서도 계산하면, 총 경우의 수는 \[ 3^{10} - 3 \times (20 + 1). \tag*{$\myblue{\square}$} \]

$ $

정리 1.2.6. 같은 것이 있는 순열

$k$개의 서로 다른 대상이 각각 $n_1,\, n_2,\, \ldots,\, n_k$개 있다고 하자. 대상을 일렬로 나열하는 경우의 수는 \[ \frac{(n_1 + n_2 + \cdots + n_k)!}{n_1! n_2! \cdots n_k!}. \]

$ $

예제 1.2.7.
Q. 단어 STATISTICS에 사용된 문자의 순서를 바꾸어 만들 수 있는 모든 단어의 수를 구하여라.
A. 문자 A, C, I, I, S, S, S, T, T, T를 일렬로 배열하는 경우의 수와 같으므로 \[ \frac{10!}{2! \cdot 3! \cdot 3!} = 50400. \tag*{$\myblue{\square}$} \]

$ $

예제 1.2.8.
Q. $A,\, B,\, C$가 각각 $5$개씩 있다고 하자. 이 중에서 각 문자를 적어도 $2$개씩 포함하는 $10$개의 문자로 이루어진 단어의 개수를 구하여라.
A. 우선 $A,\, B,\, C$를 $2$개씩 선택한 후, 나머지 문자 중에서 $4$개의 문자를 추가로 선택하여 배열하는 방법을 생각하자. 경우의 수를 나누어 생각하면

• 한 문자를 $3$개, 다른 문자를 $1$개 선택하는 경우: 총 $6$가지 경우가 있고, 각각의 문자가 $5,\, 3,\, 2$개씩 있게 되므로 이를 나열하는 경우의 수는 \[ 6 \times \frac{10!}{5! \cdot 3! \cdot 2!} \]
• 한 문자를 $2$개, 다른 문자를 $2$개 선택하는 경우: 총 $3$가지 경우가 있고, 각각의 문자가 $4,\, 4,\, 2$개씩 있게 되므로 이를 나열하는 경우의 수는 \[ 3 \times \frac{10!}{4! \cdot 4! \cdot 2!} \]
• 한 문자를 $2$개, 다른 문자를 각각 $1$개씩 선택하는 경우: 총 $3$가지 경우가 있고, 각각의 문자가 $4,\, 3,\, 3$개씩 있게 되므로 이를 나열하는 경우의 수는 \[ 3 \times \frac{10!}{4! \cdot 3! \cdot 3!} \]

각 사건은 동시에 일어나지 않으므로 전체 경우의 수는 \[ 6 \times \frac{10!}{5! \cdot 3! \cdot 2!} + 3 \times \frac{10!}{4! \cdot 4! \cdot 2!} + 3 \times \frac{10!}{4! \cdot 3! \cdot 3!}. \tag*{$\myblue{\square}$} \]

$ $

다음 정리는 주어진 등식의 좌변과 우변을 각각 조합적인 대상으로 생각하여 양변이 같음을 증명하는 방법이다. 이와 같이 어떤 등식을 대수적 방법을 이용하지 않고 주어진 대상을 서로 다른 방법으로 세는 방법 등을 통해 증명하는 방법을 조합론적 증명법이라 한다.

$ $

정리 1.2.9.

$n \geq r$인 양의 정수 $n,\, r$에 대하여 다음 등식이 성립한다.

1. ${}_{n}P_{n-1} = {}_{n}P_{n}$
2. ${}_{n}P_{r} = n \cdot {}_{n-1}P_{r-1}$
3. ${}_{n}P_{r} = {}_{n-1}P_{r} + r \cdot {}_{n-1}P_{r-1}$
4. $(n-r) \cdot {}_{n}P_{r} = n \cdot {}_{n-1}P_{r}$

$ $

증명.

1. $n$명의 지원자 중에서 $n-1$명의 합격자의 순위를 매기는 경우의 수 ${}_{n}P_{n-1}$는, $n$명의 지원자 전체의 순위를 매기는 경우의 수 (이 경우 전체 꼴등은 자동으로 불합격) ${}_{n}P_{n}$과 같다.
2. $n$명의 지원자 중에서 $r$명의 합격자의 순위를 매기는 경우의 수 ${}_{n}P_{r}$은 $n$명의 지원자 중에서 최고점 합격자를 먼저 선택하고, 나머지 $n-1$명의 지원자 중에서 $r-1$명의 합격자의 순위를 매기는 경우의 수 $n \cdot {}_{n-1}P_{r-1}$과 같다.
3. $n$명의 지원자 중에서 $r$명의 합격자의 순위를 매기는 경우의 수 ${}_{n}P_{r}$은, 특정 지원자 $A$가 불합격했을 때 나머지 $n-1$명의 지원자 중에서 $r$명의 합격자의 순위를 매기는 경우의 수 ${}_{n-1}P_{r}$와, 특정 지원자 $A$가 합격했을 때 먼저 $A$의 순위를 매기고 나머지 나머지 $n-1$명의 지원자 중에서 $r-1$명의 합격자의 순위를 매기는 경우의 수 $r \cdot {}_{n-1}P_{r-1}$의 합과 같다.
4. $n$명의 지원자 중에서 $r$명의 합격자의 순위를 매긴 후에 나머지 $n-r$명의 불합격자 중 추가합격자를 선택하는 경우의 수 $(n-r) \cdot {}_{n}P_{r}$은 $n$명의 지원자 중에서 최우수합격자를 먼저 선정하고 나머지 $n-1$명의 지원자 중에서 $r$명의 합격자의 순위를 매기는 경우의 수 $n \cdot {}_{n-1}P_{r}$과 같다. $ $

$ $

예제 1.2.8.
Q. 정육면체 모양의 주사위가 있다고 하자.

1. 각 면에 $1$부터 $6$까지의 숫자를 적는 방법의 수를 구하여라.
2. 마주보는 면에 적힌 수의 합이 $7$이 되도록 각 면에 $1$부터 $6$까지의 숫자를 적는 방법의 수를 구하여라.

A.

1. 주사위의 윗면에 $1$을 고정하면 아랫면에 적을 수 있는 숫자들의 경우의 수는 $5$가지이다. 그 다음 나머지 네 숫자를 옆면에 적는 경우의 수는 원순열의 개수와 같으므로, 전체 경우의 수는 \[ 5 \cdot \frac{4!}{4} = 30. \]
2. 주사위의 윗면에 $1$을 고정하면 아랫면에는 반드시 $6$이 적혀야 한다. 그 다음 숫자 $2$와 $5$, 그리고 숫자 $3$과 $4$가 서로 마주 보아야 하므로 $2$와 $3$을 적는 위치만 고려해 주면 충분하다. 따라서 전체 경우의 수는 $2$가지이다. $ $

$ $