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

이 주의 길잡이

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

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

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

이번 주 목표

1. 비둘기집 원리를 일반형까지 진술하고 귀류로 증명하며, 비둘기집 논증의 3단 서식을 백지에 재현한다.

2. 순열 \(P(n,r)\)과 조합 \(\binom nr\)을 정의에서 공식까지 유도하고, 대칭\(\cdot\)파스칼 규칙을 두 길(대수\(\cdot\)조합)로 증명한다.

3. 이항정리를 귀납으로 완전히 증명하고, 계수가 조합인 이유를 조합적 해석으로 설명한다.

4. 이중 세기로 조합 항등식을 증명하고, 대수 증명과 무엇이 다른지 답안의 말로 구분한다.

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

표기 — § 와 난이도 표시

§는 “절”이라고 읽는다. §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)\)를 무엇으로 쓸 수 있는가.

2. 유클리드 보조정리를 진술하고, 산술의 기본정리 유일성 증명에서 그것이 쓰이는 자리를 한 줄로 적으시오.

3. 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번을 밀어붙여 본다.

시도 — 구성법으로 증인 제출하기

명제: 임의의 정수 \(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\)로 쓴 식으로 정하면 되는가. 그 식은 … “

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

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

답

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

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

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

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

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

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

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

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

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

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

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

이 주 전체의 기준

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

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

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

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

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}\)

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

답

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

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

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

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

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

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

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

기본형. \(n\)개의 물건을 \(k\)개의 상자에 넣을 때 \(n > k\)이면, 두 개 이상이 들어 있는 상자가 존재한다.

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

표기 — \(\lceil x \rceil\)

\(\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이 빌린 것은 “유한집합에서 단사와 전사가 동치”라는 별개의 명제이므로 원리에서 한 번 더 유도해야 청산된다. 그 유도가 다음 한 문단이다.

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

\(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의 배수가 아니다. 상자를 바꾸면 결론도 바뀐다.

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

답

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

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

목표가 “차가 4의 배수인 둘”이므로, 먼저 “\(a\)와 \(b\)의 차가 4의 배수”와 같은 말이

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

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

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

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

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

답

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

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

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

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

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

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

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

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

서로 다른 \(n\)개에서 \(r\)개를 순서를 따져 뽑아 나열하는 방법의 수를 순열이라 하고 \(P(n,r)\)로 쓴다.

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

표기 — \(P(n,r)\), \(\binom nr\), \(n!\)

\(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!\)개씩 모여 있다.

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

답

\(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\)가 된다.

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

답

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

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

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

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

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

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

모든 자연수 \(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 이중 세기 — 조합적 증명

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

백지 암기 대상

이중 세기의 원리

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

따라서 어떤 유한집합 \(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\)**를 세었다는 사실 하나뿐이다.

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

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

(나) \(n\)명 각각에 대해 “위원인가 아닌가”를 정하는 방법의 수

답

같은 집합을 세고 있다. 그 집합은 \(n\)명 집합의 부분집합 전체다.

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

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

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

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

답

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

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

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

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

확인해야 성립한다(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이 실제로 무너지는 답안이다.

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

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

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

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

답

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

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

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

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

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

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