12.1곱의 법칙
조합론의 모든 것은 한 가지 원리에서 출발한다 — 곱의 법칙(multiplication principle). 한 일을 여러 단계로 나눌 수 있고 각 단계가 독립이면, 전체 경우의 수는 각 단계의 경우의 수를 곱한다.
예: 셔츠 3벌, 바지 4벌이 있다. 옷차림은 몇 가지? 셔츠를 고르는 3가지 각각에 대해 바지를 고르는 4가지가 있으므로, 3 × 4 = 12가지. "각각에 대해"라는 말이 나오면 곱셈이다.
반대로, 경우가 서로 겹치지 않게 여러 유형으로 나뉘면 — 그때는 각 유형의 수를 더한다(합의 법칙).
합의 법칙: (경우 A) + (경우 B) + …
12.2순열 — 순서가 중요할 때
순열(permutation)은 순서를 고려해 줄 세우는 경우의 수다. n개를 모두 한 줄로 세우는 방법은 — 곱의 법칙으로 — n × (n−1) × (n−2) × … × 1이다. 이 곱을 n 팩토리얼이라 하고 n!으로 쓴다.
왜? 첫 자리에 올 것을 고르는 방법이 n가지, 그다음 자리는 남은 것 중에서 n−1가지 — 이렇게 줄어든다. n개 중 r개만 골라 줄 세우면 n!/(n−r)!이다.
P(n, r) = n! / (n − r)!
문제. 5명의 학생 중 3명을 뽑아 1, 2, 3등 시상대에 세우는 방법은?
풀이. 순서가 중요하다 — 금메달과 은메달은 다르다. 곱의 법칙으로 직접 세자. 1등 자리: 5명 중 1명 (5가지). 2등 자리: 남은 4명 중 1명 (4가지). 3등 자리: 남은 3명 중 1명 (3가지). 따라서 5 × 4 × 3 = 60가지. 공식으로는 P(5,3) = 5!/2! = 120/2 = 60. ∎
12.3조합 — 순서가 중요하지 않을 때
조합(combination)은 순서를 무시하고 단지 뽑기만 하는 경우의 수다. 시상대(순서 중요)와 달리, 위원회(순서 무관)를 뽑을 때 쓴다.
핵심 발상: 조합은 순열에서 "순서로 인한 중복"을 나눠 없앤 것이다. r개를 뽑아 줄 세우는 방법은 P(n,r)인데, 같은 r개 묶음이 r!가지 순서로 거듭 세어졌다. 그래서 r!로 나눈다.
C(n, r) = C(n, n − r)
문제. 8명 중 3명으로 위원회를 구성하는 방법은?
풀이. 위원회 안에서는 누가 먼저 뽑혔는지 중요하지 않다 — 조합이다. C(8,3) = 8!/(3!·5!) = (8·7·6)/(3·2·1) = 336/6 = 56가지. 만약 순서가 중요했다면 P(8,3) = 336이었을 것 — 조합은 그것을 3! = 6으로 나눈 값이다. ∎
12.4잘못 센 것 바로잡기
조합론에서 가장 흔한 실수는 중복해서 세거나, 빠뜨리는 것이다. 노련한 문제 해결자는 두 가지 교정 기술을 쓴다.
여집합 — 반대를 세라
"적어도 하나"를 직접 세면 경우가 복잡하다. 그럴 때 전체에서 "하나도 없는" 경우를 빼라. 반대가 더 셀 만하다면 여집합으로 우회한다.
포함-배제 — 겹친 만큼 빼라
두 집합을 합쳐 셀 때 교집합이 두 번 세어진다. |A∪B| = |A| + |B| − |A∩B| — 겹친 만큼 한 번 빼준다.
문제. 동전을 5번 던질 때, 앞면이 적어도 한 번 나오는 경우의 수는?
풀이. "적어도 한 번"을 직접 세면 1번, 2번, …, 5번으로 다섯 경우를 합쳐야 한다. 대신 여집합을 보자 — "앞면이 한 번도 안 나옴" = "모두 뒷면"은 단 1가지. 전체 경우는 각 던지기가 2가지이므로 2⁵ = 32가지. 따라서 답은 32 − 1 = 31가지. 반대를 세는 것이 압도적으로 쉽다. ∎
12.5이항정리
(x + y)ⁿ을 전개하면 어떤 계수들이 나올까? 놀랍게도 그 계수들이 바로 조합의 수다 — 이것이 이항정리(Binomial Theorem)다.
왜 그럴까? (x+y)ⁿ은 (x+y)를 n개 곱한 것이다. 전개할 때 각 괄호에서 x 또는 y를 하나 고른다. xᵏyⁿ⁻ᵏ 항은 "n개 괄호 중 k개에서 x를 골랐다"는 뜻 — 그 방법의 수가 C(n,k)다.
문제. (x + 2)⁵의 전개식에서 x³의 계수는?
풀이. 이항정리에서 x³ 항은 C(5,3) · x³ · 2²이다(5개 괄호 중 3개에서 x, 나머지 2개에서 2). C(5,3) = 10, 2² = 4. 계수는 10 × 4 = 40. 전체를 전개하지 않고 필요한 항만 집어냈다. ∎
12.6예제 모음 — 경시 문제 맛보기
문제. 격자에서 왼쪽 아래 모서리에서 오른쪽 위 모서리로, 오른쪽(→) 또는 위(↑)로만 움직여 간다. 가로 4칸, 세로 3칸 격자에서 경로의 수는?
풀이. 어떤 경로든 오른쪽 이동 4번, 위 이동 3번 — 총 7번의 이동으로 이루어진다. 경로 하나를 정한다는 것은 7번의 이동 중 어느 4번을 "오른쪽"으로 할지 고르는 것이다. 따라서 C(7,4) = 7!/(4!·3!) = 35가지. 순서 문제가 조합으로 변신했다. ∎
문제. 글자 'BANANA'를 배열하는 서로 다른 방법은 몇 가지인가?
풀이. 6글자를 모두 다르다 치면 6! = 720가지다. 그러나 A가 3개, N이 2개로 똑같다. 같은 A 3개끼리의 3! = 6가지 순서는 구별되지 않으니 중복이다. 같은 N 2개끼리의 2! = 2가지도 마찬가지. 중복을 나눠 없앤다: 6! / (3! · 2!) = 720 / 12 = 60가지. ∎