# C16주차 — 조합론 증명: 세는 것도 증명이다

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

**핵심 문장**: 세는 것도 증명이다. 개수의 비교만으로 존재가 강제되는 자리가 **비둘기집 원리**이고, 같은 유한집합을 두 방법으로 센 두 수가 같아야 한다는 것이 **이중 세기**이며, 이 둘 사이에서 **이항정리**가 대수의 전개와 조합의 세기를 잇는다.

**이 주의 위치**: 2학기 20주 과정의 C16주차. 1권 12~14주차에서 세기의 도구를 만들었고 1권 13주차에서 "세기 논증"이라는 이름으로 감각을 잡았던 것이, 여기서 **이중 세기**라는 절차와 채점표를 얻는다. 1권 26주차 문제 19가 이름만 알려 준 비둘기집 원리, C7주차 문제 16이 "인정하고 쓴다"로 미뤄 둔 그 원리가 이번 주에 진술과 증명을 얻고, C12주차 문제 17이 빌린 "유한집합에서 단사와 전사가 동치"도 그 원리의 따름 명제로 유도된다. 다음 주 C17주차는 세기를 떠나 극한으로 간다.

**원서 대응**: Chartrand 13장 (Proofs in Combinatorics). 1일차에 이 장을 통독한 상태로 이 교안에 온다.
:::

## 이번 주 목표

1. **비둘기집 원리**를 일반형까지 진술하고 귀류로 증명하며, 비둘기집 논증의 3단 서식을 백지에 재현한다.
1. **순열** $P(n,r)$과 **조합** $\binom nr$을 정의에서 공식까지 유도하고, 대칭$\cdot$파스칼 규칙을 두 길(대수$\cdot$조합)로 증명한다.
1. **이항정리**를 귀납으로 완전히 증명하고, 계수가 조합인 이유를 조합적 해석으로 설명한다.
1. **이중 세기**로 조합 항등식을 증명하고, 대수 증명과 무엇이 다른지 답안의 말로 구분한다.

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

:::{admonition} 표기 — § 와 난이도 표시
:class: quotebox

§는 "절"이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다.

다른 주차를 가리킬 때는 "C15주차 §1.2"처럼 주차를 앞에 적는다.

연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서

3으로 갈수록 지지대가 줄어든다.
:::

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

지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓰거나, 이번 주가 갚는 빚의 목록을 확인하는 데 쓴다.

1. 베주 항등식을 진술하시오 — 정수 $a, b$가 둘 다 0이 아닐 때 $\gcd(a,b)$를 무엇으로 쓸 수 있는가.
1. 유클리드 보조정리를 진술하고, 산술의 기본정리 유일성 증명에서 그것이 쓰이는 자리를 한 줄로 적으시오.
1. C15주차의 유클리드 호제법으로 $\gcd(252, 198)$을 계산하시오 (값은 $18$이다 — 절차의 네 줄을 재현하는 것이 이 문항의 목적이다).

이어서 진단 문제 하나를 풀어 보자. 풀지 못해도 된다 — 이번 주가 무엇을 메우는지 가늠하기 위한 기록이다.

1. (진단) 임의로 주어진 5개의 정수 중에는 차가 4의 배수인 두 개가 반드시 존재하는가.

근거와 함께 답하시오.

답을 노트에 적어 둔다. §5의 백지 재현 뒤에 이 기록을 다시 본다.

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

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 자연스러운 출발점이고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 예시로 확인.** $\{1,2,3,4,5\}$, $\{7,11,20,33,41\}$처럼 몇 조를 만들어

보고 매번 성립하므로 참이라고 적는다. 결론은 옳고, 사례를 실제로 만들어 본 것도 옳은 작업이다 — 참$\cdot$거짓을 가늠하는 데는 이것이 정당한 첫 걸음이다(C10주차). 문제는 "임의로 주어진 5개"가 **무한히 많다**는 것이다. 확인하지 않은 나머지 전부는 무엇이 보장하는가. §1.1이 이 간격에서 출발한다.

- **유형 2 — 반례를 찾다 실패.** 차가 4의 배수인 쌍이 하나도 없는 5개 조를 만들어

보려다 계속 실패하고, 그래서 참이라고 적는다. 방향은 옳다 — 전칭 명제를 의심할 때 반례를 먼저 노리는 것은 C10주차의 표준 절차다. 빠진 것은 **실패의 이유**다. "찾아봤지만 없었다"는 없음의 증명이 아니고, 왜 있을 수 없는지를 말해야 증명이 된다. §1.2가 그 이유를 개수 하나로 압축한다.

- **유형 3 — 나머지까지 갔지만 멈춤.** "4로 나눈 나머지는 $0,1,2,3$ 네 가지뿐인데

수는 다섯 개"까지 적고 멈춘다. 이 관찰이 이번 주의 핵심이며, 상자를 정확히 찾은 답이다. 빠진 것은 두 줄이다 — ① "네 가지뿐인데 다섯 개"에서 "둘이 겹친다"로 가는 근거의 이름 ② "나머지가 같다"에서 "차가 4의 배수"로 가는 되번역. §1.2와 §1.3이 각각 그 한 줄씩을 채운다.

## 개념 — 개수로 존재를 강제하고, 개수로 등식을 세우기

### 1 지금 가진 도구로 밀어붙이면 어디서 막히는가

새 원리를 꺼내기 전에, C7주차까지 가진 존재 증명의 도구 — 증인을 실제로 만들어 제출하는 **구성법** — 만으로 준비 운동 4번을 밀어붙여 본다.

:::{admonition} 시도 — 구성법으로 증인 제출하기
:class: quotebox

명제: 임의의 정수 $a_1, a_2, a_3, a_4, a_5$에 대해, 차가 4의 배수인 두 개가 존재한다.

"$a_1, \ldots, a_5$를 정수라 하자. 존재를 보이려면 그 두 개를 제시해야 한다.

첫 번째와 두 번째를 제시하면 되는가 — $a_1 = 1$, $a_2 = 2$이면 차가 $1$이므로 안 된다.

그러면 어느 둘인지를 $a_1, \ldots, a_5$로 쓴 식으로 정하면 되는가. 그 식은 … "
:::

여기서 멈춘다. 다음 줄이 나오지 않는다.

:::{container} quotebox
**확인 1.** 멈춘 자리에서 구성법이 요구하는 것 중 무엇을 제출할 수 없는가. 그리고 제출할 수 없는 이유는 $a_1, \ldots, a_5$의 어떤 성질 때문인가.
:::

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

제출할 수 없는 것은 **증인**, 곧 "이 둘이다"라고 지목되는 구체적인 두 첨자다.

이유는 $a_1, \ldots, a_5$가 **임의**라는 데 있다. 입력값을 보지 않고 첨자만으로

정하는 어떤 규칙("항상 첫 두 개", "항상 마지막 두 개")을 정해 놓아도, 그 규칙이

실패하는 5개 조를 언제나 만들 수 있다.

곧 겹치는 쌍의 **위치**는 입력마다 달라지므로 입력과 무관한 식으로 적을 수 없다.

물론 쌍이 10개뿐이므로 다섯 개를 손에 받은 뒤에 전부 대 보아 찾을 수는 있다 —

그러나 그것은 받은 뒤의 탐색이지, 명제를 증명하는 식이 아니다.

그렇다고 명제가 거짓인 것은 아니다 — 겹치는 쌍은 늘 있고, 다만 어디인지가

입력에 따라 옮겨 다닐 뿐이다. 필요한 것은 **위치를 말하지 않고 존재만 말하는**

증명이다. C7주차의 용어로 이것이 비구성적 존재 증명이고, 이번 주는 그 증명을

개수 비교 하나로 만드는 원리를 세운다.
:::

:::{admonition} 이 주 전체의 기준
:class: quotebox

개수의 비교만으로 존재가 강제되는 자리가 있다.

그 강제를 진술과 증명으로 굳힌 것이 **비둘기집 원리**다.

같은 유한집합을 두 방법으로 센 두 수가 같아야 한다는 것이 **이중 세기**다.

둘 다 계산이 아니라 세기를 근거로 삼는다 — 세는 것도 증명이다.
:::

### 2 사례를 모아 보기 — 물건과 상자

겹침이 강제되는 조건이 무엇인지 사례에서 먼저 읽어 낸다. 아래 표의 각 줄은 "물건을 상자에 넣는다"는 같은 상황이고, 물건 수와 상자 수만 다르다.

| **물건 (개수)** | **상자 (개수)** | **둘 이상 든 상자가 반드시 있는가** | **어떤 상자에 최소 몇 개인가** |
|---|---|---|---|
| 정수 5개 | 4로 나눈 나머지 4개 | 있다 | $2$ |
| 사람 13명 | 태어난 달 12개 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| 사람 12명 | 태어난 달 12개 | $\underline{\quad(3)\quad}$ | $1$ |
| 사람 25명 | 태어난 달 12개 | 있다 | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(4)를 채우고, "둘 이상 든 상자가 반드시 있다"가 성립하는 조건을 물건 수 $n$과 상자 수 $k$의 부등식 한 줄로 적어 보자.
:::

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

(1) 있다  (2) $2$  (3) 없다  (4) $3$.

조건은 $n > k$이다. 셋째 줄이 이 조건의 경계다 — 12명을 12개월에 한 명씩 배치할

수 있으므로 겹침이 **강제되지 않는다**. 강제되는 최소 개수는 넷째 줄에서 보이듯

$2$가 아니라 커질 수 있다: 25명을 12개월에 아무리 고르게 나누어도 어떤 달에는

$3$명 이상이 된다($12 \times 2 = 24 < 25$이므로 모든 달이 2명 이하일 수는 없다).
:::

이 관찰에 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 일을 문장으로 굳혔을 뿐이다.

### 정리 1.1 — 비둘기집 원리 (pigeonhole principle) [백지 암기 대상]

:::{container} quotebox
**기본형.** $n$개의 물건을 $k$개의 상자에 넣을 때 $n > k$이면, 두 개 이상이 들어 있는 상자가 존재한다.

**일반형.** $n$개의 물건을 $k$개의 상자에 넣으면, $\lceil n/k \rceil$개 이상이 들어 있는 상자가 존재한다.
:::

:::{admonition} 표기 — $\lceil x \rceil$
:class: quotebox

$\lceil x \rceil$는 "천장 $x$"라고 읽고, $x$ 이상인 정수 중 가장 작은 것을 뜻한다.

$\lceil 25/12 \rceil = 3$이고 $\lceil 6/3 \rceil = 2$이다.

정의에서 곧바로 나오는 성질 하나만 쓴다: 모든 실수 $x$에 대해 $\lceil x \rceil < x + 1$.
:::

**증명 (귀류).** 기본형부터 본다. 두 개 이상 든 상자가 하나도 없다고 하자. 그러면 각 상자에 든 물건은 많아야 한 개다. 상자마다 든 개수를 모두 더한 것이 물건의 총수이므로

$$
n = (\text{상자 1의 개수}) + \cdots + (\text{상자 } k \text{의 개수}) \le \underbrace{1 + \cdots + 1}_{k \text{개}} = k
$$

이고, 곧 $n \le k$이다. 이것은 가정 $n > k$와 모순이다. $\blacksquare$

일반형도 같은 계산이다. $m = \lceil n/k \rceil - 1$이라 두고, 모든 상자에 $m$개 이하가 들어 있다고 하자. 그러면 개수의 합을 계산해 $n \le km$을 얻는다. 한편 $\lceil n/k \rceil < n/k + 1$이므로 $m < n/k$이고, 양변에 $k > 0$을 곱하면 $km < n$이다. 두 부등식 $n \le km$과 $km < n$을 이으면 $n < n$이므로 모순이다. 따라서 $m + 1 = \lceil n/k \rceil$개 이상 든 상자가 존재한다. $\blacksquare$

기본형은 일반형의 특수한 경우다 — $n > k$이면 $n/k > 1$이므로 $\lceil n/k \rceil \ge 2$이다.

이 원리는 1권 26주차 문제 19(양말 문제)에서 이름만 소개된 채 논증은 귀류로 직접 썼고, C7주차 문제 16(부분집합의 합)과 C12주차 문제 17(유한집합에서 단사와 전사)에서는 "지금은 인정하고 쓴다"로 미뤄 두었다. 두 빚의 내용은 다르다 — C7주차 문제 16이 빌린 것은 원리 자체이므로 위 증명으로 청산되고, C12주차 문제 17이 빌린 것은 "유한집합에서 단사와 전사가 동치"라는 별개의 명제이므로 원리에서 한 번 더 유도해야 청산된다. 그 유도가 다음 한 문단이다.

:::{admonition} 따름 명제 1.A — 유한집합에서 단사와 전사 (injection and surjection on a finite set)
:class: quotebox

$A$가 원소 $n$개의 유한집합이고 $f : A \to A$이면, $f$가 단사인 것과 전사인 것이 같은 말이다.
:::

**증명.** 먼저 $f$가 단사라 하고, 전사가 아니라고 하자. 그러면 치역 $f(A)$는 $A$의 부분집합이면서 $A$와 다르므로 원소가 많아야 $n-1$개다. $A$의 원소 $n$개를 물건으로, $f(A)$의 원소를 상자로 보고 각 $a$를 상자 $f(a)$에 넣는다. 물건은 $n$개, 상자는 많아야 $n-1$개이고 $n > n-1$이므로, 비둘기집 원리에 의해 두 개 이상이 든 상자가 존재한다. 곧 $a \ne b$이면서 $f(a) = f(b)$인 두 원소가 있으므로 $f$는 단사가 아니고, 이는 가정과 모순이다. 따라서 단사이면 전사다.

거꾸로 $f$가 전사라 하고, 단사가 아니라고 하자. 그러면 $a \ne b$이면서 $f(a) = f(b)$인 두 원소가 있고, $a$를 빼도 치역은 줄지 않으므로 $f(A) = f(A \setminus \{a\})$이다. 오른쪽은 원소가 $n-1$개인 집합의 상이므로 원소가 많아야 $n-1$개이고, 따라서 $|f(A)| \le n - 1 < n = |A|$이므로 $f(A) \ne A$이다. 곧 $f$는 전사가 아니고, 이는 가정과 모순이다. 따라서 전사이면 단사다. $\blacksquare$

C12주차 문제 17이 "지금은 인정하고 쓴다"로 미뤄 둔 것이 이 명제이고, 위 다섯 줄이 그 빚의 청산이다. 무한집합에서 이 명제가 무너지는 이유도 증명에서 보인다 — 위 논증은 "물건 $n$개, 상자 $n-1$개 이하"라는 유한한 개수 비교에 기대고 있으므로, $A$가 무한하면 첫 문장부터 세울 수 없다.

### 3 절차 해부 — 비둘기집 논증의 세 걸음

원리 자체는 두 줄이지만, 답안에서 실제로 쓰이는 것은 세 걸음짜리 절차다. 걸음마다 하는 일이 다르고, 빠졌을 때 무너지는 것도 다르다.

| **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** |
|---|---|---|
| ① 상자를 정의한다 | 유한개이고, 서로 겹치지 않으며, 모든 물건이 어딘가에 들어가는 분류를 정한다 | 상자가 무한개면 $n > k$라는 비교 자체가 성립하지 않는다. 상자가 겹치거나 빈틈이 있으면 개수의 합이 총수와 어긋난다 |
| ② 물건을 넣고 두 수를 센다 | 물건 수 $n$과 상자 수 $k$를 숫자로 명시하고 $n > k$를 확인한다 | 비교 없이 "겹친다"고 쓰면 근거가 없다. 실제로 12명과 12개월에서는 겹치지 않는다 |
| ③ "같은 상자"를 원래 말로 되번역한다 | 같은 상자에 든 두 물건이 무엇을 뜻하는지 명제의 언어로 옮긴다 | 결론이 "같은 상자에 둘이 있다"에 머물러 원래 명제가 나오지 않는다 |

**걸음 삭제 실험 — ①을 바꿔 본다.** 준비 운동 4번에서 상자를 나머지가 아니라 "짝수와 홀수" 두 가지로 잡아 보자. 걸음 ②는 그대로 작동한다 — $5 > 2$이므로 같은 상자에 두 정수가 있다. 그러나 걸음 ③에서 얻는 것은 "홀짝이 같은 두 정수"뿐이고, $a = 1$과 $b = 3$이면 차가 $2$이므로 4의 배수가 아니다. 상자를 바꾸면 결론도 바뀐다.

:::{container} quotebox
**확인 3.** 위 실험이 보이는 것은 무엇인가. 걸음 ①에서 상자를 고르는 기준을 한 문장으로 적어 보자.
:::

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

비둘기집은 "겹치는 둘이 있다"까지만 주고, 그 겹침이 **쓸모 있는 결론**이 되는지는

상자의 설계에 달려 있다는 것이다. 기준은 거꾸로 세운다 — **결론에서 출발한다**.

목표가 "차가 4의 배수인 둘"이므로, 먼저 "$a$와 $b$의 차가 4의 배수"와 같은 말이

되는 조건을 찾고(나머지가 같다), 그 조건이 곧 "같은 상자"가 되도록 상자를

정의한다. 상자는 발명하는 것이 아니라 결론을 번역해서 얻는다.
:::

**걸음 삭제 실험 — ③을 빼 본다.** 걸음 ③ 없이 "따라서 나머지가 같은 두 정수가 존재한다"로 끝내면, 명제가 요구한 "차가 4의 배수"는 어디에도 적혀 있지 않다. 이 되번역은 C6주차의 합동에서 온다: $a \equiv b \pmod 4$와 $4 \mid (a-b)$가 같은 말이고, "나머지가 같다"와 "합동이다"가 같은 말임은 1권 25주차 예제 2.2에서 이미 증명했다. 곧 걸음 ③은 한 줄이지만 인용할 출처가 있는 한 줄이다.

:::{container} quotebox
**확인 4.** 어떤 답안이 다음과 같이 끝났다. 세 걸음 중 무엇이 빠졌는가.

"13명의 생일을 12개월로 분류하면 $13 > 12$이므로 비둘기집 원리에 의해 어떤 상자에 두 명 이상이 있다. $\blacksquare$"
:::

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

걸음 ③이 빠졌다. "어떤 상자에 두 명 이상"은 상자의 언어이고, 명제가 요구한 것은

"같은 달에 태어난 두 사람이 존재한다"는 사람의 언어다. 이 답안은 한 줄만 더 쓰면

완성된다 — "그 상자에 든 두 사람은 태어난 달이 같으므로, 같은 달에 태어난 두 사람이

존재한다." 걸음 ③이 형식적으로 보여도 빼지 않는 이유는, 상자를 잘못 골랐을 때

그 사실이 드러나는 자리가 정확히 여기이기 때문이다(위의 짝수와 홀수 실험).
:::

### 4 순열과 조합 — 1권 12~13주차의 회수

세기의 두 기본량을 정의로 다시 세운다. 두 정의의 차이는 한 낱말, **순서**다.

### 정의 1.2 — 순열과 조합 (permutation and combination) [백지 암기 대상]

:::{container} quotebox
서로 다른 $n$개에서 $r$개를 **순서를 따져** 뽑아 나열하는 방법의 수를 **순열**이라 하고 $P(n,r)$로 쓴다.

서로 다른 $n$개에서 $r$개를 **순서 없이** 뽑는 방법의 수, 곧 크기 $r$인 부분집합의 개수를 **조합**이라 하고 $\binom nr$로 쓴다.
:::

:::{admonition} 표기 — $P(n,r)$, $\binom nr$, $n!$
:class: quotebox

$P(n,r)$은 "피 엔 알"로 읽는다. $\binom nr$은 "엔 초즈 알"(n choose r) 또는

"엔에서 알을 고르는 방법의 수"로 읽고, 세로로 쓰되 분수가 아니다 — 가운데 줄이 없다.

$n!$은 "엔 팩토리얼"이고 $n! = n(n-1)\cdots 2 \cdot 1$, $0! = 1$이다(1권 12주차).
:::

**정의 해부 — 조각마다 하는 일.** 정의 1.2는 네 조각으로 되어 있고, 조각마다 이번 주 증명에서 맡는 역할이 다르다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "서로 다른 $n$개" | 모집단을 중복 없이 못 박는다 | $n$이 실제 선택지의 수가 된다. 곱셈 원리로 자리마다 $n, n-1, \ldots$을 세는 아래 유도가 이 조각에 기대고, 훈련 1의 두 갈래 세기도 남은 $n-1$개가 서로 다르다는 데 기댄다 |
| "$r$개를 뽑아" | 뽑는 개수를 하나로 고정한다 | $P(n,r)$과 $\binom nr$의 두 인수를 확정한다. $r$이 정해져야 예제 2.3의 크기별 분류가 크기마다 한 값을 갖는다 |
| 순열의 "순서를 따져 나열하는" | 같은 원소 조합이라도 배열이 다르면 다른 것으로 센다 | 확인 5에서 $P(n,r)$이 "나열 전체"의 개수가 되는 근거다. 이 조각이 있어야 나열 하나마다 부분집합 하나가 대응한다는 $r!$배 관계가 성립한다 |
| 조합의 "순서 없이", 곧 "크기 $r$인 부분집합" | 집합의 원소 나열 순서가 무의미하다는 성질에 세기를 얹는다 | "$\binom nr$"과 "크기 $r$인 부분집합의 개수" 사이를 근거 ①로 오갈 수 있게 한다. 예제 2.3$\cdot$훈련 1$\cdot$문제 12$\cdot$15$\cdot$16의 첫 줄이 전부 이 번역이다 |

**조각 삭제 실험 1 — 조합에서 "순서 없이"를 지우면.** $\binom nr$을 "$r$개를 뽑는 방법의 수"로만 두고 순서를 따지지 않는다는 조각을 빼면, $\binom nr$과 $P(n,r)$이 구별되지 않는다. $n = 4$, $r = 2$에서 값이 $\binom42 = 6$이 아니라 $P(4,2) = 12$가 되고, 확인 5의 관계 $P(n,r) = \binom nr \cdot r!$은 $12 = 12 \cdot 2$가 되어 거짓이 된다. 예제 2.3도 같이 무너진다 — 크기별로 더한 값이 $1 + 4 + 12 + 24 + 24 = 65$가 되어 $2^4 = 16$과 어긋난다. 나열 $\{1,2\}$와 $\{2,1\}$을 두 번 센 만큼 정확히 과다 계수된 것이다.

**조각 삭제 실험 2 — "서로 다른 $n$개"를 지우면.** 모집단에 중복을 허용해 $\{1, 1, 2\}$를 $n = 3$개로 세어 보자. 크기 2인 부분집합은 $\{1, 2\}$ 하나뿐인데 $\binom32 = 3$이므로 정의가 세는 값과 실제 개수가 어긋난다. 훈련 1의 파스칼 세기도 같은 자리에서 무너진다 — $a = 1$로 잡으면 "$a$를 포함하는 것"이 $\binom21 = 2$개, "$a$를 제외하는 것"이 $\binom22 = 1$개로 합이 $3$인데, 실제 부분집합은 하나뿐이다. 곧 "서로 다른"은 수식어가 아니라 $n$이라는 수가 서로 다른 선택지의 수임을 보증하는 조각이며, 이것이 빠지면 두 갈래 각각의 셈부터 값을 잃는다.

두 값을 공식으로 바꾼다. 순열은 곱셈 원리에서 바로 나온다(1권 12주차): 첫 자리에 $n$가지, 둘째 자리에 남은 $n-1$가지, 이렇게 이어 가면 $r$번째 자리에 $n-r+1$가지이므로

$$
P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}.
$$

조합은 순열에서 순서를 지워 얻는다. 크기 $r$인 부분집합 하나를 정하면 그 부분집합의 원소를 나열하는 방법이 $r!$가지이고, 그 $r!$개의 나열은 모두 같은 부분집합에서 나온 서로 다른 순열이다. 곧 순열 전체는 부분집합 하나마다 정확히 $r!$개씩 모여 있다.

:::{container} quotebox
**확인 5.** 위 관찰에서 $\binom nr$의 공식을 유도해 보자. $P(n,r)$와 $\binom nr$ 사이의 등식을 먼저 적고, 그다음 $\binom nr$에 대해 풀어 보자.
:::

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

$P(n,r) = \binom nr \cdot r!$이다. 좌변은 나열 전체의 개수이고, 우변은 "부분집합을

고른 뒤 그 안을 나열한다"로 같은 나열 전체를 센 것이다. 양변을 $r!$로 나누면

$$
\binom nr = \frac{P(n,r)}{r!} = \frac{n!}{r!\,(n-r)!}
$$

이다. 이 유도 자체가 이미 이중 세기다 — 같은 집합(나열 전체)을 두 방법으로 세었다.

1권 13주차 §1.6이 이 관찰을 "첫 세기 논증은 이미 끝나 있었다"로 짚은 그 자리다.
:::

기본 성질 세 가지를 미리 모아 둔다. 셋 다 증명이 붙어 있고, 어디에 붙어 있는지가 셋마다 다르다.

| **성질** | **식** | **증명은 어디에 있는가** |
|---|---|---|
| 대칭 | $\binom nr = \binom n{n-r}$ | 문제 7 (대수와 조합 두 길) |
| 파스칼 규칙 | $\binom nr = \binom{n-1}{r-1} + \binom{n-1}{r}$, 단 $1 \le r \le n-1$ | 1권 13주차 예제 2.2에서 세기 논증으로 이미 증명 / 훈련 1(그 증명을 이중 세기 서식으로 재현), 문제 11(대수적인 두 번째 길) |
| 전체 합 | $\sum_{k=0}^n \binom nk = 2^n$ | 예제 2.3 (이중 세기), 문제 19의 재료 |

또 $\binom n0 = \binom nn = 1$이다 — 크기 0인 부분집합은 공집합 하나뿐이고, 크기 $n$인 부분집합은 전체 하나뿐이다.

### 5 이항정리 — 계수가 조합인 이유

$(x+y)^n$을 전개하면 $x^{n-k}y^k$ 꼴의 항들이 나오고, 그 계수가 무엇인지가 문제다. 전개를 기계적으로 하지 말고 **무엇을 세고 있는지** 보자. $(x+y)^n$은 $(x+y)$가 $n$개 곱해진 것이고, 전개란 각 괄호에서 $x$ 또는 $y$를 하나씩 골라 곱한 결과를 모두 더하는 일이다. 고른 결과 중 $y$를 정확히 $k$번 고른 것들이 $x^{n-k}y^k$가 된다.

:::{container} quotebox
**확인 6.** $(x+y)^3$의 전개에서 $xy^2$의 계수를 세어 보자. 세 개의 괄호 중 무엇을 정하면 항 하나가 정해지는가.
:::

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

$y$를 고를 괄호 **두 개를 정하면** 항 하나가 정해진다. 세 괄호에서 두 개를 고르는

방법은 $\binom32 = 3$가지이므로 계수는 3이다. 실제로

$(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$이다.

여기서 순서를 따지지 않는 이유는, 어느 괄호에서 골랐든 곱은 같은 항이 되기

때문이다 — 그래서 $P(3,2)$가 아니라 $\binom32$다.
:::

### 정리 1.3 — 이항정리 (binomial theorem) [백지 암기 대상]

:::{container} quotebox
모든 자연수 $n$과 모든 수 $x, y$에 대해

$$
(x+y)^n = \sum_{k=0}^n \binom nk x^{n-k} y^k.
$$
:::

이 정리는 예제 2.2에서 귀납으로 증명한다. 정리가 **항등식**이라는 점이 중요하다 — $x$와 $y$ 자리에 아무 수나 넣어도 성립하므로, 특정 값을 넣어 새 등식을 얻을 수 있다. 가정의 "모든"을 써먹는 특수화(S7주차)의 전형적인 사용처다.

| **대입** | **얻는 등식** | **이번 주 어디에서 쓰는가** |
|---|---|---|
| $x = y = 1$ | $\sum_{k=0}^n \binom nk = 2^n$ | 예제 2.3의 대수 대응물, 문제 19 |
| $x = 1$, $y = -1$ | $\sum_{k=0}^n (-1)^k \binom nk = 0$, 단 $n \ge 1$ | 문제 8, 문제 19 |
| $x = 1$, $y = 2$ | $\sum_{k=0}^n \binom nk 2^k = 3^n$ | 훈련 2 |

### 6 이중 세기 — 조합적 증명

비둘기집이 개수 비교로 **존재**를 얻는다면, 이중 세기는 개수 비교로 **등식**을 얻는다.

:::{admonition} 백지 암기 대상
:class: keybox

**이중 세기의 원리**

하나의 유한집합의 크기는 세는 방법과 무관하게 정해진 수 하나다.

따라서 어떤 유한집합 $X$를 두 방법으로 세어 각각 $A$와 $B$를 얻었다면 $A = B$이다.

등식 $A = B$를 증명하려면, 좌변이 $X$를 이렇게 센 결과이고 우변이 **같은** $X$를

저렇게 센 결과임을 보이면 된다.
:::

1권 13주차 §1.6이 "세기 논증"이라는 이름으로 세운 것이 이 원리이고, 여기서 **이중 세기**(double counting)라는 이름과 아래의 3단 서식을 얻는다. 감각으로 하던 일이 절차와 채점표를 갖추는 자리다.

| **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** |
|---|---|---|
| ① 세는 대상 $X$를 선언한다 | 유한집합 하나를 명시한다 | 두 셈이 같은 것을 세었다는 보증이 사라진다. 서로 다른 집합을 센 두 수는 같을 이유가 없다 |
| ② 방법 1로 세고, 그 셈의 정당성을 밝힌다 | 분류가 서로소이고 전체를 덮는지, 또는 곱셈 원리의 조건이 맞는지 적는다 | 분류가 겹치면 과다 계수, 빈틈이 있으면 과소 계수가 되어 등식이 어긋난다 |
| ③ 방법 2로 세고, 두 수를 등식으로 잇는다 | "같은 $X$를 두 방법으로 세었으므로"를 명시하고 결론을 적는다 | 두 수를 나란히 적기만 하면 등식의 근거가 답안에 없다 |

**걸음 삭제 실험 — ①을 빼 본다.** 대상을 선언하지 않고 "좌변은 무언가의 개수이고 우변도 무언가의 개수이므로 같다"라고 쓰면, 같은 논법으로 거짓 등식도 통과한다. 예를 들어 $\sum_{k=0}^n \binom nk = 3^n$은 거짓인데($n=1$에서 $2 \ne 3$이다), 좌변과 우변 각각이 "무언가의 개수"라는 것은 여전히 참이다. 등식을 낳는 것은 두 셈이 **같은 $X$**를 세었다는 사실 하나뿐이다.

:::{container} quotebox
**확인 7.** 다음 두 셈이 같은 집합을 세고 있는지 판정해 보자. 같다면 그 집합이 무엇인지 한 줄로 적어 보자.

(가) $n$명에서 위원 $k$명을 뽑는 방법의 수를 $k = 0, 1, \ldots, n$에 대해 모두 더한 수

(나) $n$명 각각에 대해 "위원인가 아닌가"를 정하는 방법의 수
:::

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

같은 집합을 세고 있다. 그 집합은 **$n$명 집합의 부분집합 전체**다.

(가)는 부분집합을 크기별로 묶어 세었고, (나)는 부분집합 하나를 "각 사람의

포함 여부"라는 결정의 목록으로 보아 세었다. 둘 다 부분집합 하나마다 정확히 한 번씩

센다. 이것이 예제 2.3의 증명이 된다.
:::

:::{container} quotebox
**확인 8.** 걸음 ②의 "서로소이고 전체를 덮는다"를 빼면 어떤 오류가 생기는가. $n$명에서 두 명을 뽑는 방법을 "① 첫 번째 사람을 포함하는 경우 ② 두 번째 사람을 포함하는 경우"로 분류하면 무엇이 어긋나는가.
:::

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

두 갈래가 **겹친다** — 첫 번째와 두 번째를 함께 뽑은 경우가 양쪽에 모두 들어가므로

두 번 세어지고, 합이 실제보다 커진다. 게다가 셋째 사람과 넷째 사람만 뽑은 경우는

어느 갈래에도 없으므로 전체를 덮지도 못한다. 곧 걸음 ②의 정당성 문장은 형식이

아니라 셈의 값을 좌우한다. 경우로 나누어 더하는 셈은 서로소와 전체 덮기를 함께

확인해야 성립한다(S15주차 정의 15.1의 경우법은 전수성만 요구한다 — 케이스가 겹쳐도

각 케이스에서 결론이 나오면 논리적 증명은 무너지지 않는다. 세기에서는 겹침이 곧

이중 계수이므로 서로소가 조건 하나 더 붙는다. 이것이 논리의 경우 나누기와 세기의

경우 나누기가 갈리는 자리다).
:::

### 7 이번 주에 쓸 수 있는 근거 — 목록 갱신

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식$\cdot$부등식의 성질 ④ 이미 증명한 명제. 이번 주가 채우는 것은 ①과 ④다.

| **근거** | **이번 주에 추가$\cdot$갱신되는 것** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | **정의 1.2**(순열$\cdot$조합), 상자와 물건의 분류 정의 | "$\binom nr$" $\leftrightarrow$ "크기 $r$인 부분집합의 개수" 사이를 번역한다 |
| ② 닫힘성 | 변화 없음 | 정수끼리의 합$\cdot$차$\cdot$곱이 정수임을 별도 설명 없이 쓴다 |
| ③ 등식$\cdot$부등식의 성질 | 천장 함수의 성질 $\lceil x \rceil < x+1$ | 비둘기집 일반형의 증명에서 $km < n$을 얻는 자리에 쓴다 |
| ④ 이미 증명한 명제 | **비둘기집 원리**(정리 1.1) $\cdot$ 유한집합에서 단사와 전사(따름 명제 1.A) $\cdot$ **이중 세기의 원리**(§1.6) $\cdot$ 조합 공식(§1.4) $\cdot$ **이항정리**(정리 1.3, 증명은 예제 2.2) $\cdot$ 대칭(문제 7) $\cdot$ 파스칼 규칙(1권 13주차 예제 2.2에서 기증명, 이번 주에는 훈련 1과 문제 11에서 다시 세운다) $\cdot$ 곱셈 원리(1권 12주차)와 합의 법칙/덧셈 원리(1권 14주차) $\cdot$ 합동과 나머지가 같은 말임(1권 25주차 예제 2.2) $\cdot$ 모든 정수는 짝수이거나 홀수임(1권 33주차 나눗셈 정리) | "비둘기집 원리에 의해"처럼 이름을 대고 한 줄로 끝낸다 |

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 **"반례를 찾아봤지만 없었다"와 "계산해 보니 몇 개가 맞았다"는 근거가 아니다** — 전자는 §0의 유형 2가, 후자는 문제 18이 실제로 무너지는 답안이다.

:::{container} quotebox
**확인 9.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) "$\binom nk$는 크기 $k$인 부분집합의 개수이므로, 그것들을 $k$에 대해 모두 더하면 부분집합 전체의 개수다."

(나) "$n = 3, 4, 5$에서 성립함을 확인했으므로 모든 $n$에서 성립한다."

(다) "$5 > 4$이므로 어떤 나머지 상자에 두 정수가 들어 있다."
:::

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

(가) 허용 — 근거 ①(정의 1.2)과 ④(합의 법칙, 1권 14주차)를 함께 쓴 문장이다.

크기별 분류가 서로소이고 전체를 덮으므로 더하는 것이 정당하다.

(나) 불허 — 목록 밖이다. 전칭 명제에 대한 유한 개의 확인은 근거가 아니며,

문제 18이 정확히 이 형태의 답안을 다룬다.

(다) 허용 — 근거 ④(비둘기집 원리 기본형). 상자를 무엇으로 잡았는지가 앞줄에

적혀 있다는 조건에서만 그렇다.
:::