# 14주차 — 포함–배제의 원리 + 3부 총정리

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 두 번 센 것은 한 번 빼면 된다.

**이 주의 위치**: 50주 과정의 14주차. 3부(세기)의 마지막 주 — 덧셈 원리$\cdot$포함–배제$\cdot$여사건 세기를 더하고, 총정리 모의시험으로 12~14주차를 닫는다.

**원서 대응**: BoP(Book of Proof) 3.3, 3.7 — 병행자 참고용. 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 덧셈 원리(서로소 분할이면 개수를 더한다)를 조건까지 포함해 진술하고 사용한다.
1. $|A \cup B| = |A| + |B| - |A \cap B|$를 **증명**한다 — 고1 때 외운 $n(A \cup B)$ 공식이자, 5주차 문제 13에서 수치로만 확인한 등식의 빚 회수다.
1. 3집합 포함–배제와 여사건 세기("적어도 하나")를 사용한다.
1. 3부(세기) 총정리 모의시험으로 12~14주차를 자가 평가한다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (13주차 복습)

1. $\binom{n}{k}$의 정의와 공식을 쓰시오.
1. 파스칼 공식을 쓰고, 세기 증명의 핵심(기준 인물 분할)을 한 문장으로 말하시오.
1. $(x+y)^5$의 $x^2y^3$ 계수는?

답은 §6 해설 맨 앞에 있다. 채점까지 마친 뒤 본문으로 들어간다.

### 자주 나오는 세 가지 답

채점 결과는 대개 다음 세 유형 중 하나로 갈린다. 셋 다 13주차 내용을 절반 이상 소화한 상태이고, 셋 다 이번 주 모의시험 전에 메워야 할 정확한 간격이 있다.

- **유형 1 — 공식은 정확한데 세기 증명의 핵심이 안 나온다.** $1 \le k \le n-1$이면

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$까지는 적는다 — 조건까지 붙였으면 13주차 예제 2.2의 명제 그대로이고, 조건을 빠뜨렸으면 그 한 줄부터 보충한다. 공식 암기는 완료된 상태다. 간격은 우변의 두 항이 **무엇을 세는지**다 — 기준 인물(갑)의 포함/미포함으로 부분집합 전체를 겹침 없이 둘로 나눈 뒤 각각 세어 더한다는 논증. 그 "겹침 없이 나눠 더하기"를 정당화하는 원리가 이번 주의 덧셈 원리이고, 모의시험 문제 16이 이 증명의 백지 재현이다.

- **유형 2 — 첨자가 어긋난다.** $\binom{n}{k} = \binom{n-1}{k} + \binom{n}{k-1}$처럼

적는 경우가 많다. 파스칼 삼각형의 그림 기억에만 의존한 것이 원인이다 — 각 항이 세는 대상(갑 포함이면 남은 $n-1$명 중 $k-1$명, 갑 미포함이면 $n-1$명 중 $k$명)을 항 옆에 붙이면 첨자는 스스로 복원된다. 공식은 그림이 아니라 분할에서 나온다.

- **유형 3 — 3번의 값은 맞는데 이유가 없다.** 계수 10을 적고 끝낸다. 값은 옳다.

간격은 서술이다 — 12주차 서술 규범대로 "다섯 괄호에서 $y$를 고를 3곳을 선택하는 가짓수 $\binom{5}{3}$"이라는 한 줄이 있어야 채점 가능한 답이 된다. 이번 주 모의시험은 이 서술을 전 문항에서 요구한다.

## 개념 — 덧셈 원리, 포함–배제, 여사건

### 1 곱셈 원리만으로 밀어붙이면 어디서 막히는가

12주차 이후 세기의 도구는 곱셈 원리 하나였다. 이 도구로 다음 문제를 밀어붙여 보자.

:::{admonition} 시도 — 곱셈 원리로 밀어붙이기
:class: quotebox

문제: 미술반 12명, 음악반 15명(두 반에 겹치는 학생은 없다) 가운데 축제 대표

1명을 뽑는 가짓수는?

서술 규범대로 적어 보자: "대표 선출은 (1단계: $\underline{\qquad}$, 2단계:

$\underline{\qquad}$)의 길이 2 목록이고 …" — 여기서 멈춘다.

1단계와 2단계가 없다. 뽑는 사람은 한 명이고, 선택은 한 번뿐이다.
:::

:::{container} quotebox
**확인 1.** 곱셈 원리의 적용 조건(12주차)은 무엇이었는가. 이 문제는 왜 그

조건에 들어맞지 않는가. 억지로 $12 \times 15$를 계산하면, 그 수는 실제로

무엇을 세는가?
:::

:::{admonition} 답
:class: quotebox dropdown

곱셈 원리는 세기가 **단계의 연속**(길이 $k$ 목록)으로 분해될 때 쓴다. 이

선택은 단계가 아니라 갈래다 — "미술반에서 뽑는 경우" 아니면 "음악반에서 뽑는

경우". $12 \times 15$는 (미술반원, 음악반원) **쌍**의 개수, 즉 **각 반에서

한 명씩** 두 명을 뽑는 다른 문제의 답이다(27명 중 아무 두 명을 뽑는 문제의 답

$\binom{27}{2} = 351$과도 다르다). 필요한 것은 단계를 잇는 원리가 아니라

**경우끼리 개수를 결합하는** 새 원리다.
:::

### 2 경우로 쪼개 더하기 — 원리를 만들어 보기

두 경우에 걸친 후보 전체는 집합의 언어로 $A \cup B$다 ($A$ = 미술반, $B$ = 음악반). 작은 사례부터 — 겹치지 않는 두 집합의 합집합을 직접 나열해 크기를 재 보자.

| **$A$** | **$B$** | **$\lvert A \rvert$** | **$\lvert B \rvert$** | **$A \cup B$의 나열** | **$\lvert A \cup B \rvert$** |
|---|---|---|---|---|---|
| $\{1, 2\}$ | $\{5, 7, 9\}$ | 2 | 3 | $1, 2, 5, 7, 9$ | 5 |
| $\{a, b\}$ | $\{c\}$ | 2 | 1 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| 미술반 | 음악반 | 12 | 15 | 두 명단을 이어 붙인 것 | $\underline{\quad(3)\quad}$ |

:::{container} quotebox
**확인 2.** 표의 빈칸 (1)(2)(3)을 채우고, 세 줄에 공통인 규칙을 등식 하나로

적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $a, b, c$  (2) $3$  (3) $27$. 공통 규칙: $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert$.

이유도 나열 안에 이미 있다 — 겹침이 없으므로 $A$의 나열 뒤에 $B$의 나열을

이어 붙인 것이 곧 $A \cup B$의 나열이고, 같은 원소가 두 번 등장하지도,

빠지지도 않는다. 개수는 그대로 합이다.
:::

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 겹치지 않는 두 명단을 이어 붙이면 개수가 합이 된다는, 방금 표에서 한 관찰을 문장으로 굳혔을 뿐이다.

### 덧셈 원리 (Addition Principle) [백지 암기 대상]

:::{container} quotebox
유한집합 $A, B$가 **서로소**($A \cap B = \emptyset$)이면 $|A \cup B| = |A| + |B|$이다.

일반화: $A_1, \dots, A_k$가 쌍마다 서로소이면 $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_k|$이다.
:::

두 집합 꼴의 근거는 확인 2의 이어 붙이기 논증으로 충분하다. $k$개 일반형은 이 논증을 반복해서 얻는데, 그 반복의 정당화는 31주차 귀납법에서 완결한다 — 지금은 인정하고 쓴다.

실은 이미 써 본 원리다. 13주차 파스칼 공식의 세기 증명에서 부분집합 전체를 "갑 포함/갑 미포함"으로 나눠 더할 때 "14주차에서 공식화한다"고 예고했던 바로 그것이고, 12주차 문제 20에서 설계한 "경우 나누기" 상황의 해답이다. **곱셈 원리는 "단계"로 쪼갤 때, 덧셈 원리는 "경우"로 쪼갤 때** 쓴다.

:::{container} quotebox
**확인 3.** 다음 세 세기는 각각 단계로 쪼개는가(곱셈), 경우로 쪼개는가(덧셈).

(가) 대문자 1개 뒤에 숫자 1개를 붙인 코드의 가짓수

(나) 대문자 1개 **또는** 숫자 1개로 된 기호 하나의 가짓수

(다) $\{1, \dots, 30\}$에서 2의 배수 또는 3의 배수인 수의 개수
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 단계 — (문자, 숫자)의 길이 2 목록, 곱셈 원리로 $26 \times 10 = 260$.

(나) 경우 — 대문자인 경우와 숫자인 경우. 대문자이면서 숫자인 기호는 없으므로

서로소이고, 덧셈 원리로 $26 + 10 = 36$.

(다) 경우이긴 한데 — 2의 배수이면서 3의 배수인 수(6, 12, …)가 있어 두 경우가

**서로소가 아니다**. 덧셈 원리의 조건이 무너지는 이 상황이 §1.4의 주제다.
:::

### 3 원리 해부 — 조각마다 하는 일

| **조각** | **하는 일** | **세기(증명)에서의 역할** |
|---|---|---|
| "유한집합 $A, B$" | 대상의 제한 | 크기 $\lvert \cdot \rvert$가 개수로 확정되는 무대다 — 무한집합의 크기 비교는 48~49주차의 주제다 |
| "서로소 ($A \cap B = \emptyset$)" | 적용 조건 | 이 조각이 무너지면 이중 세기가 생긴다 (아래 실험) |
| "$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert$" | 결론 등식 | 큰 세기 하나를 작은 세기 두 개로 분해한다 — 파스칼 증명이 이 분해였다 |
| "쌍마다 서로소" | 일반화의 조건 | 셋 이상일 때는 **모든 쌍**이 겹치지 않아야 이어 붙이기가 반복된다 |

**조각 삭제 실험.** 둘째 조각 "서로소"를 지우고 원리를 확인 3의 (다)에 적용해 보자. $U = \{1, \dots, 30\}$에서 $A$ = 2의 배수 집합(15개), $B$ = 3의 배수 집합(10개)이므로 $15 + 10 = 25$개 — 라고 주장하게 된다.

:::{container} quotebox
**확인 4.** $A \cup B$를 실제로 나열해 개수를 세어 보자. 25개가 맞는가?
:::

:::{admonition} 답
:class: quotebox dropdown

$2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30$ —

**20개**다. $25 \neq 20$ — "서로소" 조각을 지우는 순간 등식이 실제 개수보다

5만큼 크게 어긋난다. 조건은 장식이 아니라 등식을 지키는 조각이다.

어긋난 5가 정확히 어디서 왔는지는 다음 절에서 원소 단위로 추적한다.
:::

### 4 겹치면 그냥 더할 수 없다 — 초과분의 정체

$15 + 10 = 25$가 실제 20보다 커진 이유를 원소의 입장에서 본다. $15 + 10$이라는 계산은 $A$의 명단과 $B$의 명단을 그대로 이어 붙여 센 것이다 — 원소 하나하나가 이 계산에서 몇 번 세어지는지 표로 추적해 보자.

| **원소** | **$A$의 명단에서** | **$B$의 명단에서** | **$15 + 10$에서 세어진 횟수** |
|---|---|---|---|
| $4$ (2의 배수만) | 1번 | 0번 | 1번 |
| $9$ (3의 배수만) | 0번 | 1번 | $\underline{\quad(1)\quad}$번 |
| $6$ (2와 3의 배수) | 1번 | 1번 | $\underline{\quad(2)\quad}$번 |
| $7$ (어느 쪽도 아님) | 0번 | 0번 | 0번 |

:::{container} quotebox
**확인 5.** 표의 빈칸 (1)(2)를 채우고, "초과분 5"의 정체를 집합의 언어로

지목해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $1$  (2) $2$. 두 번 세어지는 원소는 정확히 **양쪽 명단에 다 있는 원소**,

곧 $A \cap B$의 원소들이다. 여기서는 6의 배수 $6, 12, 18, 24, 30$의 5개 —

초과분 5는 바로 $\lvert A \cap B \rvert$다. 그러므로 각 원소를 정확히 한 번씩만

세려면 두 번 센 만큼을 한 번 빼면 된다: $25 - 5 = 20$ ✓.
:::

이 조정에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 두 번 센 만큼($|A \cap B|$)을 한 번 뺐을 뿐이다.

### 포함–배제 원리 (Inclusion–Exclusion) [백지 암기 대상]

:::{container} quotebox
유한집합 $A, B$에 대해

$$
|A \cup B| = |A| + |B| - |A \cap B|
$$

유한집합 $A, B, C$에 대해

$$
|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|
$$
:::

고1 때 외운 $n(A \cup B)$ 공식이 이것이다. 이번 주에는 외우는 대신 **증명**한다 — 예제 2.1에서 덧셈 원리 두 번으로 만들고, 문제 11에서 백지에 재현한다.

3집합 버전의 리듬: 홀수 개짜리 교집합은 더하고($+$), 짝수 개짜리 교집합은 뺀다($-$). 목적은 하나다 — **각 원소가 정확히 한 번씩 세어지도록** 조정하는 것. (3집합 식은 예제 2.1을 두 번 적용하고 분배법칙 $C \cap (A \cup B) = (C \cap A) \cup (C \cap B)$ (7주차 예제에서 진리표로 확정)을 쓰면 이번 주 도구만으로도 유도된다 — 여기서는 원소 세기 관찰(확인 6)로 납득하고 넘어가고, 임의의 $n$집합 일반형은 31주차 귀납법 이후에 완결한다.)

:::{container} quotebox
**확인 6.** 3집합 식의 우변에서, 다음 두 원소가 각각 몇 번 세어지는지 항별로

추적해 보자.

(가) 세 집합 모두에 속하는 원소  (나) $A$와 $B$에만 속하고 $C$에는 없는 원소
:::

:::{admonition} 답
:class: quotebox dropdown

(가) $|A| + |B| + |C|$에서 $3$번, 쌍 교집합 세 개를 빼며 $-3$번, 삼중 교집합에서

$+1$번 — 합계 $3 - 3 + 1 = 1$번.

(나) 단일 항에서 $2$번($A$, $B$), 쌍 교집합에서는 $A \cap B$ 하나에만 속하므로

$-1$번, 삼중 교집합에는 없으므로 $0$번 — 합계 $2 - 1 = 1$번.

어느 부류의 원소든 정확히 한 번 — 부호의 리듬은 이 "정확히 한 번"을 맞추기

위한 조정이다.
:::

### 5 배수는 몇 개인가 — 바닥 기호

포함–배제를 배수 세기에 쓰려면 "$1$부터 $N$까지 중 $d$의 배수의 개수"가 재료다. 새 기호 하나를 들인다 — $\lfloor x \rfloor$는 "$x$의 **바닥**"으로 읽고, $x$를 넘지 않는 가장 큰 정수를 뜻한다. 예: $\lfloor 3.7 \rfloor = 3$, $\lfloor 5 \rfloor = 5$.

**사실.** $1$부터 $N$까지의 자연수 중 $d$의 배수는 $\lfloor N/d \rfloor$개다. 이유 — 그 배수들은 $d \cdot 1, d \cdot 2, \dots, d \cdot k$ ($d \cdot k \le N$인 가장 큰 $k$)로 나열되고, 그 $k$가 바로 $N$을 $d$로 나눈 몫 $\lfloor N/d \rfloor$다.

:::{container} quotebox
**확인 7.** $1$부터 $100$까지 중 $7$의 배수는 몇 개인가. 바닥 기호로 적고,

마지막 배수가 무엇인지로 검산해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$\lfloor 100/7 \rfloor = 14$개. 검산 — 마지막 배수는 $7 \times 14 = 98 \le 100$이고

다음 배수 $7 \times 15 = 105$는 100을 넘는다 ✓. §1.3의 삭제 실험에서 쓴

"2의 배수 15개"도 같은 계산 $\lfloor 30/2 \rfloor = 15$였다.
:::

### 6 "적어도 하나"는 뒤집어 센다

포함–배제가 "또는"의 세기라면, 이번에는 "적어도 하나"의 세기다. 정면으로 밀어붙이면 비용이 어떻게 되는지부터 본다.

:::{admonition} 시도 — 정면 돌파
:class: quotebox

문제: 3자리 비밀번호(각 자리 0~9) 중 숫자 0을 적어도 하나 포함하는 것은 몇 개인가?

"적어도 하나"이므로 0의 개수로 경우를 나눈다 — 0이 정확히 1개:

자리 선택 $\binom{3}{1} = 3$, 나머지 두 자리 $9^2$가지로 $3 \times 81 = 243$개.

정확히 2개: $\binom{3}{2} \times 9 = 27$개. 정확히 3개: $1$개.

세 경우는 서로소이고 전체를 덮으므로 덧셈 원리로 $243 + 27 + 1 = 271$개.
:::

답은 나왔다 — 그러나 경우 세 개마다 곱셈 원리 계산이 하나씩 필요했고, 자리가 5개, 10개로 늘면 경우도 그만큼 늘어난다. 방향을 바꿔 보자. 11주차 부정 규칙 — "적어도 하나($\exists$)"의 부정은 "전부 아님($\forall\neg$)" — 이 세기 전략이 되는 지점이다(12주차 문제 15에서 먼저 맛본 전환이다).

:::{container} quotebox
**확인 8.** "0을 적어도 하나 포함한다"의 부정을 11주차 규칙으로 문장으로 적고,

그 부정에 해당하는 비밀번호의 개수를 곱셈 원리로 계산해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

부정: "**어느 자리에도 0이 없다**" — 모든 자리가 0이 아니다. 각 자리의 후보가

1~9의 9가지인 길이 3 목록이므로 곱셈 원리로 $9^3 = 729$개. 전체 $10^3 = 1000$개에서

빼면 $1000 - 729 = 271$개 — 정면 돌파의 결과와 일치한다. 경우 세 개가 뺄셈

한 번으로 줄었다.
:::

### 여사건 세기 (complementary counting) [백지 암기 대상]

:::{container} quotebox
유한집합 $U$와 $A \subseteq U$에 대해 $|A| = |U| - |A^c|$이다.
:::

'빼기 원리'라고도 부른다. **"적어도 하나 ~"는 정면 돌파가 번거롭고, 그 부정("하나도 ~ 아님")은 곱셈 원리 한 번으로 끝날 때가 많다.** 부정을 세서 전체에서 빼는 이 전략이 여사건 세기다.

:::{container} quotebox
**확인 9.** 이 공식은 외울 것이 아니라 유도할 것이다 — 덧셈 원리에서 두 줄로

나온다. $U$를 어떤 서로소 조각으로 나누면 되는지부터 시작해 유도 전체를 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$U$의 임의의 원소는 $A$에 속하거나 속하지 않거나 — 정확히 한쪽이다. 따라서

$U = A \cup A^c$이고 $A \cap A^c = \emptyset$ (5주차 여집합의 정의). $U$가

유한집합이므로 조각 $A$, $A^c$도 유한집합이고, 서로소인 두 유한집합에 덧셈

원리를 적용하면 $|U| = |A| + |A^c|$이고, 이항하면(근거 ③) $|A| = |U| - |A^c|$이다. $\blacksquare$

여사건 공식은 덧셈 원리의 두 줄짜리 따름 명제다 — 유도했으므로 오늘부터

근거 ④로 인용해 쓴다.
:::

### 7 근거 목록 갱신 — 칸은 그대로 네 개

칸은 그대로 네 개다. 이번 주에 새 정의는 바닥 기호 하나뿐이고(§1.5), 세 원리는 전부 "이미 증명했거나 논증한 명제"로서 ④ 칸에 들어간다.

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | **바닥 기호 $\lfloor x \rfloor$**(§1.5) 추가 (목록$\cdot$팩토리얼 12주차, 조합 13주차) | "적어도 하나 포함하는 비밀번호"를 집합 $A \subseteq U$로 번역하고, $\lfloor N/d \rfloor$를 배수의 개수로 번역한다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 이번 주에는 등장이 적다 |
| ③ 등식의 성질 | 대입 / 이항 / 묶기 | $\lvert A - B \rvert$를 이항으로 표현하고(예제 2.1의 (ii)), (ii)를 (i)에 대입한다 |
| ④ 이미 증명한 명제 | **덧셈 원리**(두 집합은 §1.2의 이어 붙이기 논증, 일반형은 31주차까지 인정), **포함–배제 2집합**(예제 2.1에서 증명), **3집합**(원소 세기 관찰로 납득 — 예제 2.1을 두 번 적용하고 분배법칙을 쓰면 유도된다), **여사건 공식**(확인 9에서 유도), **배수 세기 $\lfloor N/d \rfloor$**(§1.5), **공배수 = 최소공배수의 배수**(5주차 문제 9의 관찰 — 20주차에서 증명, 지금은 인정하고 쓴다), 곱셈 원리$\cdot$조합$\cdot$이항정리(12~13주차) | 세기 답안의 인용 근거 — "덧셈 원리에 의해", "포함–배제에 의해"가 이번 주의 표준 문구다 |

:::{container} quotebox
**확인 10.** 어떤 답안에 다음 세 근거 문장이 나왔다. 각각 근거 목록을 통과하는가?

(가) "2와 5의 공배수는 10의 배수이므로 $\lfloor 100/10 \rfloor = 10$개"

(나) "$n(A \cup B)$ 공식은 고등학교에서 배웠으므로"

(다) "포함–배제(예제 2.1에서 증명)에 의해"
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 통과 — "2와 5의 공배수 = 10의 배수"(근거 ④의 공배수 관찰 — 20주차에서

증명, 지금은 인정)와 배수 세기 사실(근거 ④)의 결합 적용이다.

(나) 불통과 — "학교에서 배웠다"는 목록 밖의 권위다. 식 자체는 옳지만, 이

교재 안에서는 예제 2.1의 증명이 그 식의 근거이고 그렇게 인용해야 한다.

(다) 통과 — 같은 식을 근거 ④의 형식으로 바르게 인용한 것이다. (나)와 (다)의

차이가 곧 "외운 공식"과 "증명한 명제"의 차이다.
:::