포함–배제의 원리

개요 — 동기·문제의식

셈의 기본 원리의 합의 법칙은 집합들이 서로소일 때만 $|A\cup B|=|A|+|B|$를 보장한다. 그러나 실제 셈 문제에서 조건들은 거의 항상 겹친다 — "2의 배수 또는 3의 배수", "적어도 한 과목을 수강하는 학생", "적어도 하나의 값을 빠뜨리는 함수". 겹침이 있으면 단순 합은 교집합의 원소를 여러 번 세고, 포함–배제의 원리(principle of inclusion–exclusion, PIE)는 이 중복을 교집합들의 크기를 교대로 더하고 빼서 정확히 상쇄시키는 체계적 보정 공식이다.

이 원리의 진짜 힘은 합집합 세기 자체보다 그 여집합 형태(체 공식)에 있다. "나쁜 성질 $A_1,\dots,A_n$을 하나도 갖지 않는 원소의 수"를 각 교집합 $|A_{i_1}\cap\cdots\cap A_{i_k}|$가 쉽게 계산되는 상황에서 구하는 것 — 전사함수의 개수, 고정점 없는 순열(교란순열) $D_n$, $n$과 서로소인 수의 개수 $\varphi(n)$이 모두 이 한 가지 틀에서 나온다. 어려운 "정확히 조건을 만족" 문제를 쉬운 "적어도 이만큼 위반" 문제들의 교대합으로 바꾸는 것이 PIE의 요체다.

이름이 시사하듯 공식의 구조는 단순하다 — 하나짜리는 포함하고, 둘짜리 겹침은 배제하고, 셋짜리는 다시 포함하고. 어려움은 공식 자체가 아니라 전체집합 $S$와 나쁜 성질 $A_i$를 무엇으로 잡을 것인가의 모형화에 있으며, 이 장의 응용 세 가지(전사함수·교란순열·$\varphi$)는 그 모형화의 표준 견본이다.

직관

두 집합의 벤 다이어그램에서 $|A|+|B|$를 계산하면 겹치는 부분이 두 번 세어지므로 $|A\cap B|$를 한 번 빼 준다. 세 집합에서 쌍끼리의 교집합을 모두 빼면 이번에는 한가운데 $A\cap B\cap C$의 원소가 $3-3=0$번 세어져 버려서 다시 한 번 더해야 한다. 과하게 세고(포함), 과하게 빼고(배제), 다시 보정하는 진동이 집합 개수만큼 이어진다 — 각 원소가 결국 정확히 한 번씩만 세어지도록.

이 진동이 왜 정확히 $1$에서 멈추는지는 이항정리가 설명한다. 어떤 원소가 $n$개의 집합 중 정확히 $m\ge1$개에 속하면, 크기 $k$짜리 교집합 항들 중 $\binom{m}{k}$개에서 등장하므로 총 기여는 $\sum_k(-1)^{k-1}\binom{m}{k}=1-(1-1)^m=1$이다. 즉 PIE는 $(1-1)^m=0$이라는 항등식을 집합 세기의 언어로 번역한 것이며, 아래 모든 증명이 이 한 줄로 환원된다.

정의

기호

정의. 유한 전체집합 $S$와 부분집합 $A_1,\dots,A_n\subseteq S$에 대해, 색인집합 $J\subseteq\{1,\dots,n\}$마다 $A_J=\bigcap_{j\in J}A_j$ (단 $A_\emptyset=S$)로 쓰고, $k$번째 대칭합을 $S_k=\sum_{\lvert J\rvert=k}\lvert A_J\rvert$로 정의한다. $A_i$를 "성질 $i$를 갖는 원소들의 집합"으로 읽으면, 합집합은 "적어도 한 성질을 가짐", 여집합 $S\setminus\bigcup A_i$는 "아무 성질도 갖지 않음"이다.

교란순열

정의. $\{1,\dots,n\}$의 순열 $\sigma$가 교란순열(derangement, 완전순열) $\iff$ 모든 $i$에 대해 $\sigma(i)\ne i$ (고정점이 없음). 교란순열의 개수를 $D_n$으로 쓴다. 편의상 $D_0=1$ (빈 순열은 공허하게 고정점이 없다).

오일러 φ 함수

정의. 양의 정수 $n$에 대해 $\varphi(n)=\bigl|\{k:1\le k\le n,\ \gcd(k,n)=1\}\bigr|$ — $n$ 이하의 양의 정수 중 $n$과 서로소인 것의 개수.

주요 정리

정리 1 (두·세 집합의 포함–배제). $|A\cup B|=|A|+|B|-|A\cap B|$이고, $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$.

정리 2 (일반 포함–배제의 원리). 유한집합 $A_1,\dots,A_n$에 대해 $$\Bigl|\bigcup_{i=1}^{n}A_i\Bigr|=\sum_{k=1}^{n}(-1)^{k-1}S_k=\sum_{k=1}^{n}(-1)^{k-1}\sum_{1\le i_1<\cdots<i_k\le n}\bigl|A_{i_1}\cap\cdots\cap A_{i_k}\bigr|.$$

따름정리 3 (체 공식 — 여집합 형태). 어떤 $A_i$에도 속하지 않는 원소의 개수는 $$\Bigl|S\setminus\bigcup_{i=1}^{n}A_i\Bigr|=\sum_{J\subseteq\{1,\dots,n\}}(-1)^{\lvert J\rvert}\lvert A_J\rvert=|S|-S_1+S_2-\cdots+(-1)^nS_n.$$

정리 4 (전사함수의 개수). $n\ge k\ge1$일 때 $\{1,\dots,n\}$에서 $\{1,\dots,k\}$로 가는 전사함수의 개수는 $$\operatorname{Sur}(n,k)=\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}.$$

정리 5 (교란순열의 공식). $n\ge0$에 대해 $$D_n=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)!=n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}.$$

정리 6 ($D_n$과 $1/e$). $\dfrac{D_n}{n!}\to\dfrac1e$ ($n\to\infty$)이고, $n\ge1$이면 $D_n$은 $n!/e$에 가장 가까운 정수다.

정리 7 (오일러 φ 함수의 곱 공식). $n\ge2$의 서로 다른 소인수가 $p_1,\dots,p_r$이면 $$\varphi(n)=n\prod_{i=1}^{r}\Bigl(1-\frac{1}{p_i}\Bigr).$$

예제

예제 1 (배수 세기). $1$부터 $1000$까지 중 $2$, $3$, $5$ 중 적어도 하나의 배수는 몇 개인가. $|A_2|=500$, $|A_3|=333$, $|A_5|=200$, $|A_6|=166$, $|A_{10}|=100$, $|A_{15}|=66$, $|A_{30}|=33$이므로 정리 1에서 $500+333+200-166-100-66+33=734$. 따라서 셋 모두와 서로소인 수는 $1000-734=266$개다. 교집합의 크기가 최소공배수의 배수 세기로 즉시 계산된다는 점이 PIE가 잘 작동하는 전형적 상황이다.

예제 2 (전사함수). $\operatorname{Sur}(4,3)=3^4-\binom{3}{1}2^4+\binom{3}{2}1^4=81-48+3=36$. 검산: $S(4,3)=6$ (4개 원소를 3블록으로 분할 — 한 블록만 2원소, $\binom42=6$가지)이므로 $3!\cdot S(4,3)=36$으로 일치한다.

예제 3 (모자 맡기기 문제). $n=4$명이 맡긴 모자를 무작위로 돌려받을 때 아무도 자기 모자를 받지 못하는 경우는 $D_4=4!\bigl(1-1+\tfrac12-\tfrac16+\tfrac1{24}\bigr)=24-24+12-4+1=9$가지. 확률은 $9/24=0.375$로 이미 $1/e\approx0.3679$에 가깝다 — 정리 6의 수렴은 $1/(n+1)!$ 속도로 매우 빠르다.

예제 4 (φ 계산). $360=2^3\cdot3^2\cdot5$이므로 $\varphi(360)=360\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45=96$. 곱 공식은 소인수의 지수와 무관하게 서로 다른 소인수 하나당 인자 하나만 곱한다.

예제 5 (르장드르 방식의 소수 세기 — 에라토스테네스 체의 정량화). $100$ 이하의 합성수는 반드시 $\sqrt{100}=10$ 이하의 소인수($2,3,5,7$)를 가지므로, $2,3,5,7$ 중 어느 것으로도 나누어지지 않는 $n\le100$은 $1$과 "$7$보다 큰 소수"뿐이다. 따름정리 3으로 세면 ($|A_J|=\lfloor 100/\prod p\rfloor$) $$100-(50+33+20+14)+(16+10+7+6+4+2)-(3+2+1+0)+0=100-117+45-6=22.$$ 따라서 $\pi(100)=22-1+4=25$ ($1$을 빼고 소수 $2,3,5,7$을 되돌려 더함). 에라토스테네스의 체가 합성수를 "지워 나가는" 과정을 PIE가 정확한 개수로 바꿔 준다 — 이것이 해석적 수론의 체 방법(sieve method)의 출발점이다. 정리 7과의 차이도 눈여겨볼 것: 여기서는 $p\nmid 100$인 소수도 끼어들어 $|A_J|$에 내림 $\lfloor\cdot\rfloor$이 필요하다.

예제 6 (고정점이 정확히 $m$개인 순열). $\{1,\dots,n\}$의 순열 중 고정점이 정확히 $m$개인 것은 고정점 위치를 고르고($\binom{n}{m}$) 나머지를 교란시키면($D_{n-m}$) 되므로 $\binom{n}{m}D_{n-m}$개다. 무작위 순열이 고정점을 정확히 $m$개 가질 확률은 $\binom{n}{m}D_{n-m}/n!=\frac{1}{m!}\cdot\frac{D_{n-m}}{(n-m)!}\to\frac{e^{-1}}{m!}$ ($n\to\infty$, 정리 6) — 고정점 개수가 평균 $1$인 푸아송 분포로 수렴한다는, 확률적 방법에서 다시 만날 사실의 조합적 원형이다.

흔한 오해와 함정

• "세 집합이면 쌍끼리 교집합만 빼면 끝" — $A\cap B\cap C$의 원소는 세 번 더해지고 세 번 빼져서 $0$번 세어진다. 삼중 교집합을 다시 더해야 하며, 일반적으로 짝수 크기 교집합은 빼고 홀수 크기는 더하는 교대가 끝까지 이어진다.
• "고정점이 적어도 하나 있는 순열은 $n\cdot(n-1)!$개" — 고정점 위치 $n$가지 × 나머지 배열 $(n-1)!$은 고정점이 둘 이상인 순열을 중복 계산한다. 실제로 $n\cdot(n-1)!=n!$이 되어 "모든 순열이 고정점을 갖는다"는 틀린 결론이 나온다. 올바른 값은 $n!-D_n$.
• "$D_n=n!/e$" — $n!/e$는 무리수이므로 정수 $D_n$과 같을 수 없다. 정확한 관계는 반올림: $D_n=\bigl\lfloor n!/e+\tfrac12\bigr\rfloor$ ($n\ge1$).
• "전사함수는 $k^n-k(k-1)^n$개" — 첫 두 항에서 멈춘 것. 값 두 개를 빠뜨리는 함수가 두 번 빼져서 과소평가된다. 교대합을 $j=k$까지 끝까지 써야 한다.
• "$\varphi(p^a)=p^a-p$" — $p^a$ 이하의 $p$의 배수는 $p$개가 아니라 $p^{a-1}$개다. 옳은 값은 $\varphi(p^a)=p^a-p^{a-1}$이고, 곱 공식 $p^a(1-1/p)$와 일치한다.
• "교대합을 중간에서 잘라도 등호가 성립한다" — 일반적으로 거짓. 다만 홀수 번째 대칭합까지 자르면 상한, 짝수 번째까지 자르면 하한이 된다(Bonferroni 부등식). 이 절단 부등식은 확률적 방법의 합집합 상계(union bound)의 정밀화다.

큰 그림 / 연결

포함–배제는 셈의 기본 원리의 합의 법칙을 "겹침 허용" 버전으로 완성하는 조합론의 기본 도구이며, 계산의 재료(교집합 크기, 이항계수)는 순열과 조합에서 온다. 교란순열은 이 장의 닫힌 공식 외에도 점화식 $D_n=(n-1)(D_{n-1}+D_{n-2})$로 접근할 수 있고(점화식, 연습문제 6), 지수생성함수 $e^{-x}/(1-x)$로도 압축된다(생성함수) — 같은 수열을 세 가지 언어로 보는 대표적 사례다. 정리 4의 전사함수 세기는 집합과 함수의 분할·스털링 수와 직결된다.

더 높은 관점에서 PIE는 부분순서집합(관계와 동치관계) 위의 뫼비우스 반전 공식의 특수한 경우다 — 부분집합 격자에서 뫼비우스 함수가 $(-1)^{\lvert J\rvert}$이기 때문에 교대합이 나타나고, 수론의 뫼비우스 함수 $\mu$는 약수 격자에서의 같은 현상이다(정리 7이 그 접점). 예제 5의 르장드르 셈법은 에라토스테네스의 체를 등식으로 정량화한 것으로, 항의 개수가 지수적으로 늘어나는 약점을 절단·가중으로 다스리는 것이 현대 체 방법의 주제다. 확률 버전 $P(\bigcup A_i)=\sum_k(-1)^{k-1}\sum P(A_{i_1}\cap\cdots\cap A_{i_k})$와 Bonferroni 절단 부등식은 확률적 방법의 출발 도구가 된다.

연습문제

1. $1$부터 $600$까지의 정수 중 $4$의 배수 또는 $6$의 배수는 몇 개인가.
2. 학생 $100$명 중 $A$ 수강 $60$, $B$ 수강 $45$, $C$ 수강 $30$, $A\cap B$ $25$, $A\cap C$ $15$, $B\cap C$ $10$, 셋 다 수강 $5$명일 때 아무것도 수강하지 않는 학생 수를 구하라.
3. $1$부터 $10^4$까지의 정수 중 완전제곱수도 완전세제곱수도 아닌 것은 몇 개인가.
4. $\operatorname{Sur}(5,3)$을 정리 4로 계산하고, $S(5,3)=25$를 이용해 검산하라.
5. $D_5$를 정리 5로 계산하고, 점화식 $D_5=4(D_4+D_3)$으로 검산하라.
6. 점화식 $D_n=(n-1)(D_{n-1}+D_{n-2})$ ($n\ge2$)를 조합적으로 증명하라.
7. 원소가 $A_1,\dots,A_n$ 중 정확히 $m$개에 속하는 개수가 $E_m=\sum_{k=m}^{n}(-1)^{k-m}\binom{k}{m}S_k$임을 증명하라 (따름정리 3은 $m=0$인 경우).
8. "$x$ 이하의 정수 중 $\sqrt{x}$ 이하의 어떤 소수로도 나누어지지 않는 것의 개수 $=\pi(x)-\pi(\sqrt{x})+1$"임을 논증하고, 이를 이용해 $\pi(50)$을 계산하라.

관련 개념

• 셈의 기본 원리 — 합·곱의 법칙: PIE가 보정하는 출발점
• 순열과 조합 — 이항계수와 이항정리: 기여도 논법의 핵심 항등식
• 집합과 함수 — 전사함수, 분할, 스털링 수
• 점화식 — 교란순열의 점화식 $D_n=(n-1)(D_{n-1}+D_{n-2})$
• 생성함수 — $D_n$의 지수생성함수 $e^{-x}/(1-x)$
• 관계와 동치관계 — 부분순서와 뫼비우스 반전(PIE의 일반화)
• 확률적 방법 — 확률 버전 PIE, union bound와 Bonferroni 부등식