PART III — 세기
이산수학에서 세기는 더하기보다 강력합니다. 비밀번호 공간의 크기, 알고리즘의 가능한 상태 수, 확률 문제의 표본공간 — 이런 것들은 모두 "몇 개냐?"라는 단 하나의 질문으로 환원됩니다. 이 챕터에서는 그 질문에 답하는 핵심 도구들을 모아둡니다. 전단사를 이용한 카운팅, 곱 규칙, 나누기 규칙, 이항계수, 비둘기집, 포함-배제, 그리고 같은 양을 두 가지 방식으로 세서 항등식을 증명하는 조합적 증명까지. 손에 익히면 평생 써먹는 무기입니다.
어떤 집합의 원소를 직접 세기 어려울 때, 우리는 자주 "세기 쉬운 다른 집합과 짝을 지어준다"는 전략을 씁니다. 두 집합 사이에 일대일 대응(전단사)을 만들면, 한쪽의 크기를 알자마자 다른 쪽의 크기가 따라옵니다. 이게 카운팅의 가장 근본적인 원리예요.
정의 15.1.1 (전단사 카운팅 원리)
유한집합 \(A, B\)에 대해 전단사 \(f: A \to B\)가 존재하면 \(|A| = |B|\)이다.
말로 하면 당연해 보이지만, 이 단순한 사실이 카운팅의 거의 모든 트릭을 떠받칩니다. 직접 세기 곤란한 \(A\)를 들고 있으면, 더 친숙한 \(B\)와 짝지어 \(|A|\)를 \(|B|\)로 갈아끼웁니다.
예제 15.1.2 (3원소 부분집합 vs. 0/1 길이 \(n\) 수열)
\(\{1, 2, \dots, n\}\)의 부분집합의 개수를 셉니다. 부분집합 \(S\)마다 길이 \(n\)의 비트열 \(b_1 b_2 \cdots b_n\)을 대응시킵니다. \(b_i = 1\)이면 \(i \in S\), 아니면 \(i \notin S\). 이 대응은 명백히 전단사이고, 비트열은 자리마다 두 가지이므로 \(2^n\)개입니다. 따라서 \(\{1, \dots, n\}\)의 부분집합도 \(2^n\)개.
"직접 세지 마라, 짝지어라" — 이 챕터의 보이지 않는 슬로건입니다. 다음 절부터 짝지을 만한 표준 집합들 (수열, 순열, 조합 등)을 차례로 만들어둡니다.
카운팅의 첫 번째 도구상자는 수열입니다. 자리마다 어떤 집합에서 원소를 하나씩 골라 늘어놓는 것이죠. 자리들이 서로 독립이라면 단순한 곱셈이 답을 줍니다.
정리 15.2.1 (곱 규칙, Product Rule)
유한집합 \(P_1, P_2, \dots, P_k\)에 대해, 카르테시안 곱의 크기는 \(|P_1 \times P_2 \times \cdots \times P_k| = |P_1| \cdot |P_2| \cdots |P_k|.\)
특히 모든 자리가 같은 집합 \(P\)(\(|P| = n\))에서 골라지고 자리 수가 \(k\)이면 수열의 개수는 \(n^k\)입니다.
예제 15.2.2 (비밀번호의 무서움)
영문 소문자만 쓰는 8자리 비밀번호의 개수는 \(26^8 \approx 2.09 \times 10^{11}\). 이걸 영문 대소문자 + 숫자(62종)로 늘리면 \(62^8 \approx 2.18 \times 10^{14}\)로 1000배 커집니다. "한 자리만 더, 한 종류만 더" 같은 작은 변화가 거대한 차이를 만든다는 게 곱 규칙의 위력이에요.
예제 15.2.3 (DNA 가닥)
길이 \(n\)의 DNA 서열 — 각 자리에 A, C, G, T 중 하나 — 은 \(4^n\)개. \(n=20\)만 되어도 \(4^{20} = 2^{40} \approx 1.1 \times 10^{12}\)로 인간 게놈 한 곳을 검색하기에 충분히 많습니다.
이 단순한 \(n^k\) 수식 하나로 자료구조의 상태 공간, 해시 함수의 출력 공간, 트리의 노드 수 같은 것들이 한꺼번에 다뤄집니다. 곱 규칙이 카운팅의 \(+\)이라면, 다음 절의 일반화된 곱 규칙은 \(\times\)입니다.
현실의 선택은 종종 "앞에서 무엇을 골랐느냐"에 따라 다음에 가능한 선택지가 달라집니다. 이때도 곱 규칙은 유효한데, 다만 각 자리의 경우의 수가 일정하기만 하면 됩니다.
정리 15.3.1 (일반화된 곱 규칙)
길이 \(k\)의 수열 \( (s_1, s_2, \dots, s_k) \)를 만들 때, \(s_1\)을 \(n_1\)가지로 고를 수 있고, \(s_1\)이 어떻게 정해졌든 \(s_2\)를 \(n_2\)가지로, …, \(s_{i-1}\)까지가 어떻게 정해졌든 \(s_i\)를 \(n_i\)가지로 고를 수 있다면, 가능한 수열의 총 개수는 \(n_1 \cdot n_2 \cdots n_k\)이다.
각 단계의 가짓수가 이전 선택에 의존하더라도, 의존 결과의 크기가 일정하기만 하면 곱셈이 통한다 — 이게 핵심입니다.
예제 15.3.2 (\(n!\)의 등장)
\(\{1, 2, \dots, n\}\)의 모든 원소를 한 번씩 늘어놓는 방법(순열)의 수를 셉니다. 첫 자리는 \(n\)가지, 그 다음 자리는 무엇을 골랐든 남은 \(n-1\)가지, …, 마지막 자리는 \(1\)가지. 따라서 순열의 수는 \(n \cdot (n-1) \cdots 2 \cdot 1 = n!\). 이게 그 유명한 팩토리얼입니다.
예제 15.3.3 (서로 다른 카드 순서)
52장 카드를 한 줄로 늘어놓는 방법은 \(52! \approx 8.06 \times 10^{67}\). 이 수는 우주의 별 개수보다 훨씬 큽니다. 카드를 잘 섞었을 때 같은 순서가 우연히 두 번 나올 확률이 사실상 0인 이유가 여기에 있어요.
\(k\)개를 뽑아 늘어놓는 \(k\)-순열의 수는 \(n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}\)이고, 자주 \(P(n,k)\)로 씁니다. 곧 보겠지만 이 식은 다음 절들과 빠르게 얽혀 들어갑니다.
때로는 "필요 이상으로 많이 센 다음" 중복분으로 나누는 게 가장 빠른 길입니다. 모든 원소가 똑같이 \(k\)번씩 세어졌다는 사실만 잡으면, 답은 전체 / \(k\)예요.
정리 15.4.1 (나누기 규칙)
함수 \(f: A \to B\)가 \(k\)-대-\(1\) 매핑이면, 즉 모든 \(b \in B\)에 대해 \(|f^{-1}(b)| = k\)이면, \(|A| = k \cdot |B|\), 따라서 \(|B| = |A|/k\).
예제 15.4.2 (원탁에 둘러앉기)
\(n\)명을 원탁에 앉히는 자리 배치 수를 셉니다. 자리에 번호를 매겨 일렬 순열로 보면 \(n!\)가지인데, 원탁에서는 회전해서 같은 배치는 한 가지로 봅니다. 회전은 \(n\)가지이므로 \(n\)-대-\(1\) 매핑이 생기고, 답은 \(n!/n = (n-1)!\). 거울 대칭까지 같다고 보면 다시 \(2\)로 더 나누어 \((n-1)!/2\).
예제 15.4.3 (\(k\)-순열에서 \(k\)-조합으로)
\(\{1, \dots, n\}\)에서 \(k\)개를 뽑아 늘어놓는 방법은 \(P(n,k) = n!/(n-k)!\). 그런데 같은 \(k\)개의 원소들은 \(k!\)가지로 늘어놓을 수 있으니, "순서 무시"로 보면 \(k!\)-대-\(1\) 매핑입니다. 따라서 \(k\)개를 순서 무시하고 뽑는 방법, 즉 \(k\)-부분집합의 수는 \[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!}. \]
나누기 규칙은 본질적으로 "대칭이 있는 곳에서는 너무 많이 세어졌으니 대칭 횟수로 나눠라"라는 직관입니다. 알고리즘 분석에서 등가 클래스를 셀 때, 그래프의 라벨 없는 형태를 셀 때 끊임없이 재등장합니다.
앞에서 자연스럽게 등장한 \(\binom{n}{k}\)는 이산수학 전체에서 가장 자주 등장하는 수일지도 모릅니다. \(n\)개에서 \(k\)개를 순서 없이 고르는 방법의 수, 일명 이항계수예요.
정의 15.5.1 (이항계수)
음이 아닌 정수 \(n, k\)에 대해 \[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \quad (0 \le k \le n), \] 그 밖에는 \(0\). 읽기는 "n choose k".
예제 15.5.2 (작은 값들)
\(\binom{5}{2} = 10\) (5명에서 2명 뽑기), \(\binom{10}{3} = 120\) (10개 토픽에서 3개 고르기), \(\binom{n}{0} = \binom{n}{n} = 1\). 또한 대칭성 \(\binom{n}{k} = \binom{n}{n-k}\) — \(k\)개를 고르는 것과 \(n-k\)개를 "남기는 것"이 같은 일이라는 직관에서 바로 나옵니다.
정리 15.5.3 (파스칼 항등식)
\(1 \le k \le n\)에 대해 \[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \]
증명 (조합적 논증)
\(\{1, 2, \dots, n\}\)의 \(k\)-부분집합을 셉니다. 원소 \(n\)을 포함하느냐로 두 경우로 가릅니다. 포함하면 나머지 \(k-1\)개를 \(\{1, \dots, n-1\}\)에서 골라야 하므로 \(\binom{n-1}{k-1}\)가지. 포함하지 않으면 \(k\)개 모두를 \(\{1, \dots, n-1\}\)에서 골라야 하므로 \(\binom{n-1}{k}\)가지. 두 경우는 서로소이고 모든 \(k\)-부분집합을 빠짐없이 덮으므로 합이 \(\binom{n}{k}\).
∎
파스칼 항등식은 파스칼 삼각형을 한 줄씩 채우는 점화식이고, 동적계획법으로 \(\binom{n}{k}\)를 \(O(nk)\)에 정수 산술로 계산하는 알고리즘의 뿌리이기도 합니다.
이번에는 같은 글자가 여러 번 나오는 단어를 늘어놓는 문제입니다. 예를 들어 "MISSISSIPPI"의 글자들을 모두 한 번씩 사용해 만들 수 있는 서로 다른 단어는 몇 개일까요?
정리 15.6.1 (다중집합 순열)
\(n\)개의 자리 중 \(k_1\)자리에 1번 글자, \(k_2\)자리에 2번 글자, …, \(k_m\)자리에 \(m\)번 글자가 들어가는 (단, \(k_1 + \cdots + k_m = n\)) 단어의 수는 \[ \binom{n}{k_1, k_2, \dots, k_m} = \frac{n!}{k_1!\,k_2!\,\cdots k_m!}. \] 이를 다항계수(multinomial coefficient)라고 부릅니다.
예제 15.6.2 (MISSISSIPPI)
총 11글자, M 1개, I 4개, S 4개, P 2개. 따라서 \[ \frac{11!}{1!\,4!\,4!\,2!} = 34650. \]
또 하나 자주 나오는 문제는 구분되지 않는 \(n\)개의 공을 구분되는 \(k\)개의 상자에 나누어 담는 방법의 수입니다. 이건 그 유명한 "별과 막대"로 셉니다.
정리 15.6.3 (별과 막대)
\(x_1 + x_2 + \cdots + x_k = n\)을 만족하는 음이 아닌 정수 해 \( (x_1, \dots, x_k)\)의 개수는 \(\binom{n+k-1}{k-1}\).
증명 스케치
\(n\)개의 별 \(\star\)을 늘어놓고 사이에 \(k-1\)개의 막대 \(|\)를 끼워 넣습니다. 막대 사이의 별 개수가 각 \(x_i\)가 되죠. 별 \(n\)개와 막대 \(k-1\)개로 이뤄진 길이 \(n+k-1\) 수열 중 막대의 위치를 고르는 것이므로 \(\binom{n+k-1}{k-1}\).
∎
예제 15.6.4 (도넛 6개를 4종류 중에서 고르기)
같은 종류의 도넛은 구별하지 않고 6개를 4종류에서 고른다면 \(\binom{6+4-1}{4-1} = \binom{9}{3} = 84\)가지.
카운팅 도구가 정말로 익었는지 확인하는 가장 즐거운 방법은 포커입니다. 표준 52장 덱(13개 랭크 × 4개 슈트)에서 5장의 손패를 받습니다. 가능한 손패의 총 수는 \(\binom{52}{5} = 2{,}598{,}960\). 이걸 분모 삼아 각 족보의 확률을 계산해봅니다.
예제 15.7.1 (풀하우스)
쓰리카드 + 페어. 쓰리카드의 랭크를 고르고 (13가지), 그 랭크에서 4장 중 3장을 고르고 (\(\binom{4}{3} = 4\)), 페어의 랭크를 남은 12개에서 고르고 (12가지), 그 랭크에서 4장 중 2장을 고른다 (\(\binom{4}{2} = 6\)). \[ 13 \cdot 4 \cdot 12 \cdot 6 = 3744. \] 확률은 \(3744 / 2598960 \approx 0.00144\), 약 \(1/694\).
예제 15.7.2 (플러시, 스트레이트 플러시 제외 안 함)
같은 슈트 5장. 슈트 4가지 중 하나를 고르고, 그 슈트 13장에서 5장을 고른다. \[ 4 \cdot \binom{13}{5} = 4 \cdot 1287 = 5148. \] 그 중 스트레이트 플러시(연속 랭크)가 \(4 \cdot 10 = 40\)개. 따라서 "그냥 플러시"는 \(5148 - 40 = 5108\)이고 확률은 약 \(0.00197\).
예제 15.7.3 (투페어)
서로 다른 두 랭크의 페어 + 또 다른 한 랭크의 한 장. 페어 두 랭크 고르기 \(\binom{13}{2} = 78\), 각 랭크에서 페어 만들기 \(\binom{4}{2}^2 = 36\), 마지막 한 장의 랭크는 남은 11개에서 (11), 그 랭크에서 한 장 고르기 (4). \[ 78 \cdot 36 \cdot 11 \cdot 4 = 123552. \] 확률 약 \(0.0475\), 즉 \(1/21\) 정도. 생각보다 자주 나옵니다.
포커가 좋은 이유는 같은 손패를 두 번 세는 함정이 곳곳에 숨어 있기 때문입니다. 예를 들어 "쓰리카드 랭크는 13가지, 페어 랭크는 13가지"로 잡으면 같은 랭크를 동시에 골라버리는 모순이 생기죠. 의존적인 선택은 일반화된 곱 규칙에 충실해야 한다는 좋은 교훈입니다.
가장 단순해 보이지만 가장 자주 쓰는 카운팅 무기 — 비둘기집. 비둘기 \(n+1\)마리를 비둘기집 \(n\)개에 넣으면, 어떤 비둘기집에는 둘 이상이 들어 있다. 너무 당연하지 않나요? 그런데 이 한 줄이 종종 마법을 부립니다.
정리 15.8.1 (비둘기집 원리)
유한집합 \(A, B\)가 \(|A| > |B|\)일 때, 어떤 함수 \(f: A \to B\)도 단사일 수 없다. 즉 \(f(a_1) = f(a_2)\)인 서로 다른 \(a_1, a_2 \in A\)가 존재한다.
정리 15.8.2 (일반화된 비둘기집)
\(|A| > k \cdot |B|\)이면 어떤 \(b \in B\)에 대해 \(|f^{-1}(b)| \ge k+1\), 즉 같은 값으로 보내지는 \(A\)의 원소가 \(k+1\)개 이상 있다.
예제 15.8.3 (서울에 같은 머리카락 수)
사람의 머리카락 수는 많아야 100만 개 정도. 서울 인구는 900만이 넘습니다. 비둘기집 원리에 따라 머리카락 수가 정확히 같은 사람이 적어도 두 명 — 사실은 일반화 비둘기집으로 적어도 9명 — 존재합니다. 직접 한 명도 본 적 없지만 분명히 있어요.
예제 15.8.4 (악수와 친구)
파티에 \(n \ge 2\)명이 있을 때, 같은 사람 수와 악수한 두 사람이 반드시 있습니다. 한 사람의 악수 가능 횟수는 \(0, 1, \dots, n-1\)의 \(n\)가지인데, 0과 \(n-1\)은 동시에 나올 수 없으니 (모두와 악수한 사람이 있으면 아무와도 악수 안 한 사람은 없으므로) 실제 가능 값은 \(n-1\)가지뿐. \(n\)명을 \(n-1\)개 비둘기집에 넣은 격이라 충돌 발생.
예제 15.8.5 (중복된 부분합)
임의의 정수 \(a_1, a_2, \dots, a_n\)이 주어지면, 그 중 연속 부분의 합이 \(n\)으로 나누어떨어지는 것이 항상 존재합니다. 부분합 \(S_i = a_1 + \cdots + a_i\) (\(i = 1, \dots, n\))의 \(n\)으로 나눈 나머지를 봅니다. 나머지 후보는 \(0, 1, \dots, n-1\)의 \(n\)가지. 만약 어느 \(S_i\)가 0이면 끝. 아니면 \(n-1\)가지 비제로 나머지에 \(n\)개의 \(S_i\)가 들어가니, 같은 나머지를 갖는 \(S_i, S_j\) (\(i < j\))가 존재하고 \(S_j - S_i = a_{i+1} + \cdots + a_j\)가 \(n\)의 배수.
비둘기집은 카운팅 정리라기보다 존재 증명의 도구입니다. "있다"고 주장만 하고 누군지는 모르는 비구성적 증명의 전형이에요.
합집합의 크기를 셀 때 단순히 더하면 겹치는 부분이 두 번 세어집니다. 이걸 정확히 보정해주는 공식이 포함-배제예요. 두 집합이면 모두 알고 있는 \(|A \cup B| = |A| + |B| - |A \cap B|\)인데, 이걸 일반화한 모습이 이렇습니다.
정리 15.9.1 (포함-배제 원리)
유한집합 \(A_1, A_2, \dots, A_n\)에 대해
\[
\left| \bigcup_{i=1}^{n} A_i \right|
= \sum_{i} |A_i|
- \sum_{i
증명의 직관: 합집합의 한 원소가 정확히 \(m\)개의 \(A_i\)에 속한다면, 우변에서 그 원소는 \(\binom{m}{1} - \binom{m}{2} + \cdots + (-1)^{m+1} \binom{m}{m}\)번 세어지고, 이 합은 \(1 - (1-1)^m = 1\). 따라서 정확히 한 번 세어집니다.
예제 15.9.2 (서로소 순열, derangement)
\(\{1, 2, \dots, n\}\)의 순열 중 \(\pi(i) \ne i\)인, 즉 어떤 원소도 자기 자리에 머물지 않는 순열의 수 \(D_n\)을 셉니다. \(A_i\)를 "\(\pi(i) = i\)인 순열의 집합"이라 두면, 우리가 원하는 것은 \(n! - |A_1 \cup \cdots \cup A_n|\). \(k\)개의 인덱스를 고정하면 나머지는 자유로우니 \( |A_{i_1} \cap \cdots \cap A_{i_k}| = (n-k)!\)이고, 그런 인덱스 조합은 \(\binom{n}{k}\)개. \[ |A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k}(n-k)!. \] 따라서 \[ D_n = \sum_{k=0}^{n} (-1)^{k} \binom{n}{k}(n-k)! = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \] 흥미롭게도 \(D_n / n! \to 1/e\)이므로, \(n\)이 커지면 무작위 순열이 서로소 순열일 확률은 약 \(36.8\%\)에 수렴합니다.
예제 15.9.3 (전사 함수의 수)
\(f: \{1, \dots, n\} \to \{1, \dots, k\}\) 중 전사인 함수의 수는 포함-배제로 \[ \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n. \] "값으로 빠뜨려진 원소"가 있는 함수를 빼나가는 식입니다.
포함-배제는 식 자체는 무서워 보이지만 적용 과정은 거의 기계적입니다. 어떤 "나쁜 조건들"이 합집합으로 묶이는 문제를 만나면 거의 자동으로 떠올리세요.
이항계수 항등식 같은 식을 보면 보통 양변을 식으로 펼쳐 같은 다항식임을 보이려고 하죠. 그런데 더 우아한 길이 있습니다 — 같은 집합을 두 가지 방법으로 세서 양변이 같음을 보이는 것입니다. 이걸 조합적 증명이라고 합니다.
정리 15.10.1 (이항정리, 조합적 형태)
\[ \sum_{k=0}^{n} \binom{n}{k} = 2^n. \]
증명 (양쪽으로 세기)
\(\{1, \dots, n\}\)의 부분집합의 총 수를 두 방법으로 셉니다. 첫째: 각 원소가 들어가느냐 마느냐를 독립적으로 정하므로 \(2^n\). 둘째: 부분집합을 크기로 분류해 더하면 \(\sum_{k=0}^{n} \binom{n}{k}\). 두 방법 모두 같은 집합을 셌으니 \(\sum \binom{n}{k} = 2^n\).
∎
정리 15.10.2 (방데르몽드 항등식)
\[ \binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}. \]
증명 (조합적)
\(m\)명의 남자와 \(n\)명의 여자가 있는 그룹에서 \(r\)명의 위원회를 뽑는 방법을 세어봅니다. 좌변: 그냥 \(m+n\)명에서 \(r\)명 고르면 \(\binom{m+n}{r}\). 우변: 위원회 안의 남자 수 \(k\)로 분류 — 남자 \(k\)명을 고르고 (\(\binom{m}{k}\)) 여자 \(r-k\)명을 고른다 (\(\binom{n}{r-k}\)) — 모두 더하면 \(\sum_k \binom{m}{k}\binom{n}{r-k}\). 같은 일을 두 가지로 셌으니 등식.
∎
예제 15.10.3 (\(k \binom{n}{k} = n \binom{n-1}{k-1}\))
\(\{1, \dots, n\}\)에서 \(k\)명짜리 위원회를 만들고 그 중 한 명을 위원장으로 뽑는 방법을 셉니다. 좌변: 위원회를 먼저 (\(\binom{n}{k}\)), 그 안에서 위원장 한 명 (\(k\)). 우변: 위원장을 먼저 \(n\)명 중 한 명, 나머지 \(n-1\)명 중 \(k-1\)명을 추가 위원으로 (\(\binom{n-1}{k-1}\)). 두 방법이 같으므로 \(k \binom{n}{k} = n \binom{n-1}{k-1}\).
식 변형으로 푸는 증명이 "그렇다"라는 사실만 알려준다면, 조합적 증명은 "왜 그런지"를 보여줍니다. 같은 객체를 두 방법으로 세는 습관이 들면 이항계수에 관한 거의 모든 항등식이 자명해 보이기 시작해요. 카운팅이 단순한 수 세기 기법을 넘어 증명 기술이 되는 순간입니다.
노트 (이 챕터의 한 줄 정리)
직접 세지 말고 짝지어라. 자리들이 독립이면 곱하라. 의존적이면 일반화된 곱. 너무 많이 세었으면 나누어라. 합집합엔 포함-배제. 비둘기 \(n+1\)마리 \(n\)개 집엔 충돌이 있다. 그리고 같은 것을 두 방법으로 세면 항등식이 떨어진다 — 이게 카운팅 챕터의 모든 것입니다.