셈의 기본 원리

개요 — 동기·문제의식

조합론은 "몇 가지인가"라는 질문에서 시작한다. 8자리 비밀번호는 몇 개나 가능한가, 100명 중 생일이 같은 달인 사람은 반드시 몇 명 이상인가 — 전자는 유한집합의 크기를 정확히 계산하는 문제이고, 후자는 크기 비교만으로 어떤 대상의 존재를 보장하는 문제다. 이 장은 두 질문 모두에 답하는 가장 기본적인 도구를 다룬다. 모든 논의는 집합과 함수에서 정의한 집합·함수·전단사의 언어 위에서 이루어진다.

정확한 세기를 위한 도구는 곱의 법칙·합의 법칙·뺄셈 법칙·나눗셈 법칙의 네 가지다. 겉보기에 자명하지만, 순열과 조합의 순열·조합 공식 전부가 이 네 법칙의 반복 적용으로 유도되므로 이 장이 조합론 전체의 지반이 된다. 존재 보장을 위한 도구는 비둘기집 원리다. 진술은 한 줄이지만 생일 문제부터 Erdős–Szekeres 정리까지 놀랄 만큼 다양한 존재 정리를 낳으며, 그 무구성적 성격은 확률적 방법의 존재 증명으로 이어지는 원형이다. 증명에는 증명 기법의 귀류법과 수학적 귀납법이 반복적으로 쓰인다.

직관

여러 단계로 이루어진 선택 절차는 나무그림(tree diagram)으로 그릴 수 있다. 뿌리에서 출발해 첫 단계의 각 선택이 가지가 되고, 각 가지 끝에서 다시 다음 단계의 선택이 갈라진다. 절차의 전체 결과는 잎(leaf)과 일대일로 대응하므로, 경우의 수를 세는 일은 잎의 개수를 세는 일이다. 매 단계에서 가지가 정확히 같은 개수로 갈라지면 잎의 수는 단계별 가지 수의 곱이 되고(곱의 법칙), 나무가 서로 겹치지 않는 몇 그루로 나뉘면 전체 잎 수는 각 나무의 잎 수의 합이 된다(합의 법칙). 나머지 두 법칙은 이 둘의 보정이다 — 겹치게 센 것은 빼고(뺄셈), 똑같이 여러 번 센 것은 나눈다(나눗셈).

비둘기집 원리의 심상은 더 단순하다. 비둘기가 상자보다 많으면 어떤 상자에는 두 마리 이상이 들어간다. 핵심은 평균 논법이다: $N$마리를 $k$개 상자에 어떻게 나누어 넣어도 상자당 평균은 $N/k$마리이므로, 평균 이상을 받은 상자가 적어도 하나 존재한다. "모두가 평균 미만일 수는 없다"는 이 한 문장이 원리의 전부이며, 어렵게 느껴지는 응용 문제들은 대부분 "무엇을 비둘기로, 무엇을 상자로 볼 것인가"라는 모델링 단계가 어려운 것이다.

두 심상은 성격이 다르다. 세기의 법칙들은 답을 정확한 수로 내놓지만, 비둘기집 원리는 개수를 전혀 계산하지 않고 두 크기의 비교만으로 결론을 얻는다. 그래서 후자의 결론은 언제나 "존재한다"는 형태이고, 그 대상을 실제로 찾는 절차는 주지 않는다. 이 대비 — 정확한 계산 대 존재 보장 — 가 이 장 전체를 관통하는 구도다.

정의

유한집합의 크기

정의. $[n]=\{1,2,\dots,n\}$으로 쓴다. 집합 $A$에 대해 $\lvert A\rvert=n$ $\iff$ 전단사 $A\to[n]$이 존재 ($n\ge 0$, $[0]=\varnothing$). 이런 $n$이 존재하면 $A$는 유한집합이다. 크기가 잘 정의됨(서로 다른 $n$이 동시에 될 수 없음)과 유한집합의 부분집합이 다시 유한이며 크기가 줄지 않음은 집합의 크기에서 다룬다. 이 장의 모든 집합은 유한집합이다.

세기의 함수적 모델

정의. 두 집합의 크기가 같음을 보이는 표준 방법은 전단사를 만드는 것이다(전단사 논법). "대상들을 상자에 분류한다"는 상황은 함수 $f:A\to B$($A$는 대상, $B$는 상자, $f(a)$는 $a$가 들어가는 상자)로 모델링되며, 상자 $b$에 든 대상의 집합은 원상 $f^{-1}(b)$이다. 비둘기집 원리는 이 모델에서 $f$의 단사성에 관한 진술이 된다.

나무그림

정의. 절차의 나무그림은 뿌리 있는 나무로, 깊이 $i$의 정점에서 뻗는 가지가 $i+1$번째 단계에서 가능한 선택과 대응하고, 잎이 절차의 완결된 결과와 일대일 대응한다. 단계별 선택지 수가 일정하지 않은 불규칙한 문제에서는 법칙을 공식처럼 쓰는 대신 나무그림으로 잎을 직접 세는 것이 안전하다. 나무 자체의 그래프 이론적 성질은 그래프와 트리에서 다룬다.

여집합 세기

정의. 전체집합 $U$ 안에서 집합 $A$를 셀 때 여집합 $\bar A=U\setminus A$가 더 세기 쉬우면 $\lvert A\rvert=\lvert U\rvert-\lvert\bar A\rvert$로 계산하는 기법을 여집합 세기라 한다. $U=A\cup\bar A$가 서로소 분할이라는 사실, 즉 합의 법칙의 직접적 귀결이며, "적어도 하나를 포함한다"는 조건을 셀 때 표준적으로 쓰인다.

주요 정리

정리 1 (합의 법칙). $A\cap B=\varnothing$이면 $\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert$. 일반적으로 $A_1,\dots,A_k$가 쌍마다 서로소이면 $\lvert A_1\cup\cdots\cup A_k\rvert=\lvert A_1\rvert+\cdots+\lvert A_k\rvert$.

정리 2 (곱의 법칙). $\lvert A_1\times\cdots\times A_n\rvert=\lvert A_1\rvert\cdots\lvert A_n\rvert$. 따라서 $n$단계 절차에서 $i$번째 단계의 선택지 수가 앞 단계의 선택과 무관하게 항상 $n_i$개이면, 절차 전체의 결과는 $n_1 n_2\cdots n_n$가지다.

정리 3 (뺄셈 법칙 — 두 집합의 포함배제). 임의의 유한집합 $A,B$에 대해 $\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$.

정리 4 (나눗셈 법칙). 함수 $f:A\to B$가 전사이고 모든 $b\in B$에 대해 $\lvert f^{-1}(b)\rvert=d$이면 $\lvert B\rvert=\lvert A\rvert/d$.

정리 5 (비둘기집 원리). $A,B$가 유한집합이고 $\lvert A\rvert>\lvert B\rvert$이면, 어떤 함수 $f:A\to B$도 단사가 아니다. 즉 $f(a_1)=f(a_2)$인 서로 다른 $a_1,a_2\in A$가 존재한다.

정리 6 (일반화 비둘기집 원리). $N$개의 대상을 $k$개의 상자에 넣으면($f:A\to B$, $\lvert A\rvert=N$, $\lvert B\rvert=k$), 적어도 $\lceil N/k\rceil$개의 대상이 든 상자가 존재한다.

정리 7 (Erdős–Szekeres, 단조 부분수열). 서로 다른 실수 $rs+1$개로 이루어진 수열은 길이 $r+1$의 증가 부분수열 또는 길이 $s+1$의 감소 부분수열을 포함한다. 특히 서로 다른 실수 $n^2+1$개의 수열은 길이 $n+1$의 단조 부분수열을 갖는다.

예제

예제 1 (문자열 세기 — 곱과 합의 결합). 길이 8의 비트열은 자리마다 2가지씩이므로 $2^8=256$개다(곱의 법칙). 대문자 3개 뒤에 숫자 3개가 오는 차량 번호판은 $26^3\cdot 10^3=17{,}576{,}000$개다. 길이가 1 이상 3 이하인 소문자 문자열은, 길이별로 서로소이므로 합의 법칙과 곱의 법칙을 결합해 $26+26^2+26^3=18{,}278$개다.

예제 2 (뺄셈 법칙). 길이 8의 비트열 중 1로 시작하거나 00으로 끝나는 것의 개수: 1로 시작하는 것 $2^7=128$개, 00으로 끝나는 것 $2^6=64$개, 둘 다인 것 $2^5=32$개이므로 $128+64-32=160$개다. 두 조건이 겹치므로 단순 합 $192$는 과잉 계산이다.

예제 3 (나눗셈 법칙 — 원탁). 서로 다른 $n$명을 원탁에 앉히는 방법의 수(회전해서 같으면 같은 배열)는 $(n-1)!$이다. 일렬 배열 전체($n!$개)에서 원탁 배열로 가는 대응은 회전 $n$가지가 같은 배열로 가는 $n$대$1$ 전사함수이므로, 나눗셈 법칙에서 $n!/n=(n-1)!$. 모든 원상의 크기가 정확히 $n$으로 같다는 점이 법칙 적용의 전제다.

예제 4 (생일 — 비둘기집과 그 일반화). 367명이 모이면 생일(윤년 포함 366가지)이 같은 두 사람이 반드시 존재한다($367>366$, 정리 5). 100명이 모이면 태어난 달이 같은 사람이 적어도 $\lceil 100/12\rceil=9$명 존재한다(정리 6). 거꾸로, 태어난 달이 같은 5명을 보장하려면 $\lceil N/12\rceil\ge 5$가 필요하므로 최소 $N=4\cdot 12+1=49$명이 필요하다 — $48$명이면 매달 정확히 4명씩 배치되는 반례가 있다.

예제 5 (나무그림 — 불규칙한 선택지). 동전을 3번 던질 때 앞면(H)이 연속으로 두 번 나오지 않는 결과의 수를 세자. 각 단계에서 허용되는 선택지 수가 직전 결과에 의존하므로(직전이 H이면 T만 가능) 곱의 법칙을 그대로 쓸 수 없다. 나무그림을 그려 잎을 직접 세면 TTT, TTH, THT, HTT, HTH의 $5$개다. 길이 $n$으로 일반화하면 잎의 수가 피보나치형 점화식을 만족하는데, 이런 자기참조적 세기는 점화식의 주제다.

예제 6 (같은 합을 갖는 두 부분집합). 각각 $100$ 이하인 서로 다른 양의 정수 10개의 집합 $S$에는, 원소 합이 같은 서로소인 두 비공 부분집합이 존재한다. 부분집합은 $2^{10}=1024$개(각 원소를 넣거나 빼는 곱의 법칙)인데, 부분집합의 합은 $0$ 이상 $10\cdot 100=1000$ 이하로 가능한 값이 $1001$가지뿐이다. $1024>1001$이므로 비둘기집 원리에 의해 합이 같은 서로 다른 두 부분집합 $X\ne Y$가 존재하고, 공통 원소를 양쪽에서 제거한 $X\setminus Y$와 $Y\setminus X$는 서로소이며 여전히 합이 같다. 양의 정수들이므로 어느 한쪽이 비었다면 다른 쪽도 합이 $0$, 즉 비어야 해서 $X=Y$가 되어 모순 — 둘 다 비공이다.

흔한 오해와 함정

• "두 경우로 나뉘면 언제나 개수를 더하면 된다" — 합의 법칙은 두 경우가 서로소일 때만 성립한다. 겹치는 경우에는 예제 2처럼 뺄셈 법칙으로 교집합을 빼야 하며, 이를 잊으면 과잉 계산이 된다.
• "곱의 법칙을 쓰려면 매 단계 선택지가 같은 집합이어야 한다" — 집합이 아니라 개수가 앞 선택과 무관하게 일정하면 충분하다. 반대로 선택지의 개수 자체가 앞 선택에 따라 달라지면 곱의 법칙을 그대로 쓸 수 없고, 경우를 나누어 합의 법칙과 결합하거나 나무그림으로 세야 한다.
• "비둘기집 원리는 어느 상자에 두 개가 들었는지 알려준다" — 원리는 순수한 존재 진술이며 어느 상자인지, 어떻게 찾는지에 대한 정보는 전혀 주지 않는다. 이 무구성성은 확률적 방법의 존재 증명과 공유하는 특징이다.
• "$N$개를 $k$상자에 넣으면 어떤 상자에는 $\lfloor N/k\rfloor+1$개 이상 있다" — $k\nmid N$일 때는 $\lceil N/k\rceil=\lfloor N/k\rfloor+1$이라 맞지만, $k\mid N$이면 거짓이다. $N=k$일 때 상자마다 1개씩 넣으면 어떤 상자도 2개를 갖지 않는다. 올바른 하계는 항상 $\lceil N/k\rceil$이다.
• "나눗셈 법칙은 전사함수면 언제나 $\lvert A\rvert/\lvert B\rvert$" — 모든 원상의 크기가 동일해야 한다. 회전 대칭이 있는 배열처럼 어떤 대상만 적게 중복되는 상황(예: 목걸이 뒤집기에서 대칭인 목걸이)에서는 단순 나눗셈이 틀린다.
• "'적어도 하나 포함' 조건은 그 대상의 위치를 먼저 고르고 나머지를 자유롭게 채우면 된다" — 숫자를 적어도 하나 포함하는 문자열을 "숫자 자리 하나 선택 $\times$ 나머지 자유"로 세면 숫자가 두 개 이상인 문자열이 여러 번 세어진다. 올바른 방법은 여집합 세기: 전체에서 "숫자가 하나도 없는" 문자열 수를 뺀다.
• "두 사람이 생일이 같을 가능성이 높으려면 367명쯤 필요하다" — 보장(확실성)과 높은 확률을 혼동한 것이다. 확률이 $1/2$을 넘는 데는 23명이면 충분하다(생일 역설). 비둘기집 원리가 주는 것은 확률 진술이 아니라 최악의 경우에도 성립하는 보장이다.

큰 그림 / 연결

이 장의 네 법칙은 조합론의 공리 역할을 한다. 순열과 조합의 순열 공식 $n!/(n-r)!$은 곱의 법칙의 직접 적용이고, 조합 공식 $\binom{n}{r}$은 거기에 나눗셈 법칙을 겹친 것이며, 이항정리와 조합적 증명 기법도 결국 "같은 집합을 두 방식으로 센다"는 전단사 논법의 변주다. 뺄셈 법칙은 포함–배제의 원리에서 임의의 $n$개 집합으로 일반화되어 교란순열 같은 문제를 풀고, 단계적 세기가 자기 자신을 참조하게 되면 점화식의 점화식이, 수열 전체를 한 번에 다루려면 생성함수의 형식적 멱급수가 등장한다.

비둘기집 원리는 다른 줄기로 뻗는다. Erdős–Szekeres 정리(정리 7)는 "충분히 큰 구조는 질서 있는 부분 구조를 강제로 포함한다"는 램지 이론의 전형이며, 이 사상은 확률적 방법에서 램지 수의 하계를 확률적으로 증명하는 데까지 이어진다. 크기 비교로 존재를 끌어내는 논법 자체는 집합의 크기의 대각선 논법(가산 대 비가산)과 정신을 공유한다 — 두 경우 모두 "크기가 다르면 전단사가 없다"는 사실에서 구체적 대상의 존재 또는 부재를 읽어낸다.

연습문제

1. 길이 10의 비트열은 몇 개인가? 그중 1로 시작하고 1로 끝나는 것은 몇 개인가?
2. 어떤 시스템의 비밀번호는 길이 6, 7, 8의 문자열로, 각 자리는 소문자 26개 또는 숫자 10개다. 가능한 비밀번호의 수를 합·곱의 법칙으로 표현하고 계산하라.
3. 길이 8의 비트열 중 1로 시작하지도 않고 00으로 끝나지도 않는 것의 개수를 뺄셈 법칙(예제 2)을 이용해 구하라.
4. 서로 다른 구슬 $n$개($n\ge 3$)로 목걸이를 만드는 방법의 수가 $(n-1)!/2$임을 나눗셈 법칙으로 보이고, 어떤 함수의 원상 크기가 왜 모두 같은지 명시하라.
5. 13명이 모이면 태어난 달이 같은 두 사람이 존재함을 보이고, 태어난 달이 같은 6명을 보장하는 데 필요한 최소 인원을 구하라.
6. $\{1,2,\dots,100\}$에서 51개의 수를 고르면 그중 연속한 두 정수가 존재함을 비둘기집 원리로 증명하라.
7. $\{1,2,\dots,2n\}$에서 $n+1$개의 수를 고르면 한 수가 다른 수를 나누는 쌍이 존재함을 증명하라.
8. (a) 임의의 정수 $a_1,\dots,a_n$에 대해 합이 $n$으로 나누어떨어지는 연속 블록 $a_{i+1}+\cdots+a_j$가 존재함을 증명하라. (b) 길이 $n^2$이면서 길이 $n+1$의 단조 부분수열을 갖지 않는 수열을 구성해, 정리 7의 $n^2+1$이 최선임을 보여라.

관련 개념

• 순열과 조합 — 곱·합·나눗셈 법칙의 반복 적용으로 얻는 순열·조합 공식
• 포함–배제의 원리 — 뺄셈 법칙의 $n$집합 일반화, 교란순열
• 점화식 — 단계적 세기가 자기참조가 될 때의 도구
• 생성함수 — 세기 문제를 형식적 멱급수로 압축
• 확률적 방법 — 비둘기집을 넘어서는 무구성적 존재 증명, 램지 이론
• 집합과 함수 — 크기·전단사·원상 등 이 장의 기초 언어
• 집합의 크기 — 크기 비교 논법의 무한집합 버전, 대각선 논법
• 그래프와 트리 — 나무그림의 그래프 이론적 배경