7강. 경우의 수

경우의 수를 세는 일은 “하나씩 나열해 세기”를 피하는 기술입니다. 두 법칙(합과 곱)과 두 대상(순열과 조합)만으로 대부분의 문제를 풉니다. 핵심은 순서가 중요한지, 같은 것을 다시 고를 수 있는지를 먼저 정하는 것입니다.

7.1 합의 법칙과 곱의 법칙

정리 7.1 (합의 법칙). 서로 겹치지 않는 두 경우 $A$, $B$가 각각 $m$, $n$가지이면 “$A$ 또는 $B$”는 $m + n$가지입니다. 집합으로는 서로소인 $A$, $B$에 대해 $|A \cup B| = |A| + |B|$입니다.

정리 7.2 (곱의 법칙). 첫 단계가 $m$가지이고, 각 경우마다 둘째 단계가 $n$가지이면 두 단계를 차례로 하는 방법은 $mn$가지입니다. 집합으로는 $|A \times B| = |A||B|$입니다.

예제 7.3. 영문 대문자 2개 뒤에 숫자 3개가 오는 번호판은 $26^2 \cdot 10^3 = 676{,}000$개입니다.

예제 7.4. 길이 8인 비트열은 $2^8 = 256$개입니다. 그중 0으로 시작하거나 11로 끝나는 것은 $2^7 + 2^6 - 2^5 = 160$개입니다(겹치는 “0으로 시작하고 11로 끝남”을 빼므로 4강의 정리 4.10).

7.2 순열

정의 7.5 (순열). 서로 다른 $n$개에서 $r$개를 골라 순서 있게 늘어놓는 것을 $r$-순열이라 하고 그 수를 $P(n, r)$로 씁니다.

정리 7.6. $P(n, r) = n(n-1)\cdots(n-r+1) = \dfrac{n!}{(n-r)!}$. 특히 $n$개를 모두 늘어놓는 방법은 $n!$가지입니다.

증명. 첫 자리는 $n$가지, 둘째 자리는 남은 $n-1$가지, …, $r$번째 자리는 $n - r + 1$가지이므로 곱의 법칙으로 나옵니다. □

$0! = 1$로 약속합니다. 아무것도 늘어놓지 않는 방법은 1가지이기 때문입니다.

7.3 조합

정의 7.7 (조합). 서로 다른 $n$개에서 순서 없이 $r$개를 고르는 것을 $r$-조합이라 하고 그 수를 $\binom{n}{r}$ 또는 $C(n, r)$로 씁니다.

정리 7.8. $\dbinom{n}{r} = \dfrac{n!}{r!\,(n-r)!}$.

증명. $r$-순열은 “$r$개를 고르고($\binom{n}{r}$가지) 그 $r$개를 늘어놓는($r!$가지)” 것이므로 $P(n, r) = \binom{n}{r} \cdot r!$입니다. □

이 증명처럼 “한 가지를 여러 번 셌으면 그 배수로 나눈다”는 생각이 셈의 기본 도구입니다.

정리 7.9. $\binom{n}{r} = \binom{n}{n-r}$. $r$개를 고르는 것은 남길 $n - r$개를 고르는 것과 같습니다.

예제 7.10. 10명 중 회장, 부회장을 뽑는 방법은 $P(10, 2) = 90$, 대표 2명을 뽑는 방법은 $\binom{10}{2} = 45$입니다.

7.4 파스칼 삼각형과 이항정리

정리 7.11 (파스칼 항등식). $\dbinom{n}{r} = \dbinom{n-1}{r-1} + \dbinom{n-1}{r}$ ($1 \le r \le n - 1$).

증명. $n$개 중 특정한 원소 $x$를 하나 정합니다. $r$개를 고르는 방법은 $x$를 포함하는 것(나머지 $n-1$개에서 $r-1$개: $\binom{n-1}{r-1}$)과 포함하지 않는 것(나머지에서 $r$개: $\binom{n-1}{r}$)으로 나뉩니다. □

이 항등식으로 이항계수를 삼각형으로 쌓은 것이 파스칼 삼각형입니다.

정리 7.12 (이항정리). $(x + y)^n = \displaystyle\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$.

증명. $(x + y)^n$을 전개하면 $n$개의 괄호에서 각각 $x$나 $y$를 하나씩 골라 곱한 항들의 합입니다. $x^k y^{n-k}$는 $n$개 괄호 중 $x$를 고를 $k$개를 정하는 방법의 수, 곧 $\binom{n}{k}$번 나옵니다. □

따름정리 7.13. $\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n$, $\displaystyle\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$ ($n \ge 1$).

이항정리에 $x = y = 1$과 $x = -1, y = 1$을 넣으면 됩니다. 첫째 식은 원소 $n$개인 집합의 부분집합을 크기별로 센 것이므로 4강의 정리 4.8과 같습니다.

7.5 중복을 허용할 때

정리 7.14 (별과 막대). $n$종류에서 중복을 허용해 $r$개를 고르는(순서 없이) 방법은 $\binom{n + r - 1}{r}$가지입니다. 같은 말로, $x_1 + \cdots + x_n = r$의 음이 아닌 정수해는 $\binom{n + r - 1}{n - 1}$개입니다.

증명. $r$개의 별(★)과 $n - 1$개의 막대(|)를 한 줄로 늘어놓으면, 막대가 별을 $n$개 칸으로 나눕니다. $i$번째 칸의 별 수를 $x_i$로 읽으면 해와 배열이 일대일로 대응합니다. 배열은 $n + r - 1$개 자리 중 막대 $n-1$개의 자리를 고르는 것이므로 $\binom{n + r - 1}{n - 1}$가지입니다. □

예제 7.15. 세 종류의 사탕에서 10개를 고르는 방법은 $\binom{12}{2} = 66$가지입니다.

정리 7.16 (같은 것이 있는 순열). $n$개 가운데 같은 것이 $n_1, n_2, \dots, n_k$개씩 있으면, 늘어놓는 방법은 $\dfrac{n!}{n_1!\, n_2! \cdots n_k!}$가지입니다.

예제 7.17. MISSISSIPPI의 글자를 늘어놓는 방법: M 1, I 4, S 4, P 2이므로 $\frac{11!}{1!\,4!\,4!\,2!} = 34650$가지입니다.

쓰이는 곳. 확률 계산의 분모·분자, 알고리즘의 경우의 수 어림, 조합 최적화, 이항분포가 이 강의 셈 위에 있습니다. 머신러닝에서 '가능한 모델의 수'를 세어 일반화 상한을 구하는 것도 같은 생각입니다.

7.6 이 장의 요약

• 먼저 정합니다: 순서가 중요한가? 다시 고를 수 있는가?
• $P(n,r) = \binom{n}{r} r!$. 여러 번 셌으면 나눕니다.
• 파스칼 항등식, 이항정리, 별과 막대.

문제

336
56
252
66

120

120

286

60

84