# 13주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 조합과 파스칼 공식을 함께 만들기 완성된 풀이를 먼저 보이지 않는다. 설계부터 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 조합 계산과 그 의미 **문제.** 5명 중 대표 2명(직책 없음)을 뽑는 가짓수를 구하시오. **설계 — 쓰기 전에 정하는 두 가지.** 세기 답안의 출발점은 세는 대상의 선언(12주차 규범 ①)이고, 도착점은 개수와 그 근거다. 번역표로 정리하면 — | | **말** | **세기 언어 번역** | |---|---|---| | 세는 대상 (출발점) | 대표 2명의 뽑기 결과 | 5명 집합의 크기 2 $\underline{\quad(?)\quad}$ | | 목표 (도착점) | 가능한 뽑기 전부의 수 | 그런 부분집합의 개수 | | 전략 (셀 방법) | 바로 세기 어려우면 목록을 경유 | 목록으로 세고, 각 대상이 정확히 몇 번 세어졌는지로 나눈다 | :::{container} quotebox **확인 11.** 대상 칸의 빈칸을 채워 보자. 문제 문장의 어느 조건이 이 번역을 결정하는가? ::: :::{admonition} 답 :class: quotebox dropdown **부분집합**이다. 결정하는 조건은 "직책 없음" — 직책이 있으면 (회장, 부회장)처럼 순서 있는 목록이고(12주차 예제 2.1), 없으면 $\{A, B\}$라는 집합이다. §1.1이 보여 주었듯 이 선언이 틀리면 이후 계산이 전부 옳아도 답이 두 배가 된다 — 목록인가 집합인가가 세기 답안의 첫 갈림길이다. ::: **1단계 — 대상을 선언한다.** 첫 문장의 임무는 세는 대상의 정체를 못 박는 것이다. :::{container} quotebox **확인 12.** 첫 문장을 완성해 보자: "뽑는 결과는 5명 집합의 크기 $\underline{\quad}$인 $\underline{\qquad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown "크기 2인 **부분집합**이다." 확인 11의 번역을 답안의 첫 줄로 옮겼을 뿐이다 — 설계가 되어 있으면 첫 문장은 창작이 아니라 옮겨 적기다. ::: **2단계 — 목록으로 일단 센다.** 부분집합은 바로 세기 어렵지만 목록은 12주차 도구로 세어진다. 일부러 순서를 붙여 세는 것이다. :::{container} quotebox **확인 13.** 둘째 문장을 완성해 보자: "순서 있는 목록으로는 $\underline{\quad} \times \underline{\quad} = \underline{\quad}$개다." ::: :::{admonition} 답 :class: quotebox dropdown $5 \times 4 = 20$개. (첫째, 둘째)의 반복 없는 길이 2 목록 — 1번째 5가지, 2번째 4가지, 곱셈 원리(근거 ④). §1.1의 시도와 같은 계산이지만, 이번에는 이것이 최종 답이 아니라 **경유지**임을 알고 세는 점이 다르다. ::: **3단계 — 몇 번씩 세어졌는지 확인한다.** 나눗셈의 자격을 만드는 문장이다. :::{container} quotebox **확인 14.** 셋째 문장을 완성해 보자: "각 부분집합 $\{A, B\}$는 목록 $\underline{\quad}$와 $\underline{\quad}$의 $\underline{\quad}$개로 중복 계산되었다." ::: :::{admonition} 답 :class: quotebox dropdown $(A, B)$와 $(B, A)$ — $2! = 2$개. 크기 2 집합 하나를 나열하는 가짓수다. "정확히 2개씩"이라는 균일성이 핵심이다 — 부분집합마다 부푼 배수가 다르다면 한 번의 나눗셈으로 되돌릴 수 없다(문제 18의 일직선 조건이 정확히 이 균일성을 지키는 장치다). ::: **4단계 — 나누어 마무리한다.** :::{container} quotebox **확인 15.** 마지막 문장을 완성해 보자: "따라서 $\binom{5}{2} = \underline{\quad} \div \underline{\quad} = \underline{\quad}$가지이다." ::: :::{admonition} 답 :class: quotebox dropdown $20 \div 2 = 10$가지. 공식 검산: $\binom{5}{2} = \frac{5!}{2!\,3!} = \frac{120}{2 \times 6} = 10$ ✓. 논증과 공식이 같은 값을 내는 것은 우연이 아니다 — 공식 자체가 이 논증(§1.2)으로 만들어졌기 때문이다. ::: **완성본.** 방금 만든 네 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 뽑는 결과는 5명 집합의 크기 2 부분집합이다. | 직책이 없으므로 순서 무관 — 목록이 아니라 부분집합. 대상 선언이 반이다. | | 순서 있는 목록으로는 $5 \times 4 = 20$개다. | 12주차 방식으로 일단 세기 — 목록은 곱셈 원리로 세어진다. | | 각 부분집합 $\{A, B\}$는 목록 $(A,B), (B,A)$ 2개로 중복 계산되었다. | 순서 지우기의 자격: 크기 2 집합 하나당 나열이 정확히 $2! = 2$개. | | 따라서 $\binom{5}{2} = \dfrac{20}{2} = 10$가지이다. $\blacksquare$ | 나누기 논증 완성. 공식 $\frac{5!}{2!\,3!} = 10$과 일치. | **검산.** 5명을 1~5로 부르고 나열하면 $\{1,2\}$부터 $\{4,5\}$까지 10개 — §1.1의 나열과 일치한다. 나열 검산은 $n$이 커지면 불가능해지지만, 작은 사례 하나로 논증의 오류를 잡아내는 탐지기로는 쓸 만하다. ### 예제 2.2 — 파스칼 공식의 세기 증명 **명제.** $1 \le k \le n-1$이면 $\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$. 이번에는 설계만 함께 하고, 증명 본문은 완성본으로 본다. 세기 논증의 설계는 두 가지를 정하는 일이다 — ① 두 변이 함께 세는 하나의 집합 ② 우변의 모양을 만들어 줄 세기 방식. :::{container} quotebox **확인 16.** 좌변 $\binom{n}{k}$가 세는 집합은 무엇인가. 그리고 우변이 두 항의 **합**이라는 사실은, 그 집합을 어떻게 다루라는 신호인가? ::: :::{admonition} 답 :class: quotebox dropdown 좌변은 $n$명 집합의 크기 $k$ 부분집합 **전체**를 센다. 우변의 합 꼴은 그 전체를 겹치지 않는 두 무리로 쪼개어(서로소 분할) 각각 세라는 신호다 — 서로소인 두 무리로 나뉘면 개수를 더할 수 있다(덧셈 원리, 14주차에서 공식화 — 지금은 인정하고 쓴다). 세기 논증의 설계는 이렇게 목표 식의 생김새에서 거꾸로 읽어 낸다. ::: :::{container} quotebox **확인 17.** 우변의 두 항은 둘 다 $n-1$명에서 뽑는 개수다 — 한 사람이 특별 취급된다는 신호다. 그 한 사람(갑이라 부르자)을 기준으로, 크기 $k$ 뽑기 전체를 어떻게 두 무리로 나누면 되는가? ::: :::{admonition} 답 :class: quotebox dropdown "갑을 포함하는 뽑기"와 "갑을 포함하지 않는 뽑기"로 나눈다. 어떤 뽑기든 갑을 포함하거나 포함하지 않거나 둘 중 정확히 하나이므로, 두 무리는 겹치지 않고 전체를 덮는다. 갑 포함 무리: 갑은 확정이니 나머지 $n-1$명에서 $k-1$명 — $\binom{n-1}{k-1}$가지. 갑 미포함 무리: 갑을 빼고 $n-1$명에서 $k$명 — $\binom{n-1}{k}$가지. 우변의 두 항이 정확히 만들어졌다. ::: **완성본.** 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $n$명 중 한 명을 '갑'이라 이름 붙이자. 좌변은 $n$명에서 $k$명을 뽑는 가짓수다. | 세는 대상(크기 $k$ 부분집합 전체)을 선언하고, 기준 인물을 하나 고정한다. | | 모든 뽑기는 "갑 포함" 아니면 "갑 미포함" — 두 경우는 겹치지 않고 전체를 덮는다. | 서로소인 분할로 쪼개면 개수를 더할 수 있다(덧셈 원리 — 14주차에서 공식화, 지금은 인정하고 쓴다). | | 갑 포함인 뽑기: 갑을 넣고 나머지 $n-1$명에서 $k-1$명 $\to$ $\binom{n-1}{k-1}$가지. | 갑이 자리 하나를 차지했으므로 남는 선택만 센다. | | 갑 미포함인 뽑기: 갑을 빼고 $n-1$명에서 $k$명 $\to$ $\binom{n-1}{k}$가지. | 갑 없는 $n-1$명에서 온전히 $k$명을 고른다. | | 따라서 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$이다. $\blacksquare$ | 같은 대상을 두 방법(한 번에 / 갑 기준 분할)으로 센 결과의 일치. | 계산이 한 줄도 없는 증명이다 — 이것이 세기 논증이다. 같은 등식을 공식 $\frac{n!}{k!(n-k)!}$의 통분으로도 증명할 수 있지만, 그 계산은 등식이 **왜** 성립하는지 — 뽑기 전체가 기준 인물로 두 무리로 갈라진다는 구조 — 를 보여 주지 않는다. 문제 12에서 이 증명을 구체 사례로 재서술하고, 문제 14에서 수치 사례로 다시 만난다. ### 예제 2.3 — 이항정리 사용 **문제.** $(x + y)^4$를 전개하고, $(2x - 1)^5$에서 $x^3$의 계수를 구하시오. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 18.** 설계 두 가지를 정해 보자. ① 전개의 계수 다섯 개는 어디서 얻는가. ② $(2x-1)^5$에 이항정리를 적용하려면 정리의 $x, y$ 자리에 각각 무엇을 넣어야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 파스칼 삼각형의 $n = 4$행 $1, 4, 6, 4, 1$(확인 6에서 완성한 행)을 읽는다. ② $x$ 자리에 $2x$, $y$ 자리에 $-1$을 넣는다. 정리의 문자와 문제의 문자가 겹치므로, 혼동을 피해 일반항 $\binom{5}{k}(2x)^{5-k}(-1)^k$부터 적어 놓고 시작하는 것이 안전하다 — 원하는 거듭제곱이 나오는 $k$를 지목하면 항 하나만 계산해도 된다. ::: **풀이.** $n = 4$행의 계수 $1, 4, 6, 4, 1$을 읽으면 $$ (x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4 $$ 이다. $(2x-1)^5$는 이항정리에 $x$ 자리 $2x$, $y$ 자리 $-1$을 넣은 것이므로 일반항은 $\binom{5}{k}(2x)^{5-k}(-1)^k$이다. $x^3$ 항이 되려면 $5 - k = 3$, 즉 $k = 2$이고, 그 항은 $$ \binom{5}{2}(2x)^3(-1)^2 = 10 \cdot 8x^3 \cdot 1 = 80x^3 $$ 이다. 따라서 $x^3$의 계수는 $80$이다. 부호는 $(-1)^k$가 관리한다 — $k$가 홀수인 항만 음수가 된다. $\blacksquare$ 이번 풀이는 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 답안은 처음부터 끝까지 이런 산문이다. ### 관찰 — 두 논증의 같은 뼈대 예제 2.1과 2.2는 장치가 다르다 — 하나는 나눗셈, 하나는 분할. 그런데 뼈대가 같은지 대응표의 빈칸을 채워 확인해 보자. | **단계** | **예제 2.1** | **예제 2.2** | |---|---|---| | ① 세는 대상 선언 | 5명 집합의 크기 2 부분집합 | $\underline{\quad(1)\quad}$ | | ② 세기 장치와 그 정당성 | 목록 경유 — 각 부분집합이 정확히 $\underline{\quad(2)\quad}$번씩 세어짐 | 갑 기준 분할 — 두 경우가 $\underline{\quad(3)\quad}$ 않고 전체를 덮음 | | ③ 두 셈을 이어 결론 | $20 \div 2 = 10$ | $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ | :::{container} quotebox **확인 19.** 표의 빈칸 (1)(2)(3)을 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $n$명 집합의 크기 $k$ 부분집합 전체 (2) $2$ ($= 2!$) (3) 겹치지. 장치는 달라도 — 중복 배수로 나누기, 서로소 분할로 더하기 — 세 걸음은 같다: 무엇을 세는지 선언하고, 장치의 정당성을 명시하고, 두 셈을 잇는다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **세기 논증의 3단계 틀** ① 세는 대상을 선언한다 $\to$ ② 세기 장치(서로소 분할$\cdot$중복 배수$\cdot$1:1 대응)를 설계하고 그 정당성(겹치지 않고 전체를 덮는다 / 정확히 $m$번씩 / 빠짐도 겹침도 없는 짝짓기)을 명시한다 $\to$ ③ 두 셈의 결과를 이어 결론을 적는다 ::: 이 틀이 §4의 세기 증명 문제(11, 12, 13, 15, 17, 19)의 채점표다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** $\binom{7}{3} = 35$. **유도.** 7개짜리 집합에서 만드는 반복 없는 길이 3 목록은 $7 \times \underline{\quad(1)\quad} \times \underline{\quad(2)\quad} = 210$개다. 크기 3 부분집합 하나마다 그것을 나열한 목록이 정확히 $\underline{\quad(3)\quad} = 6$개씩 생기므로, 부분집합의 수는 $$ \binom{7}{3} = \frac{210}{6} = \underline{\quad(4)\quad} $$ 이다. 공식 검산: $\binom{7}{3} = \dfrac{7!}{3!\,\underline{\quad(5)\quad}!} = 35$ ✓. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장도 빈칸이다. **명제.** $\binom{6}{2} = \binom{5}{1} + \binom{5}{2}$. **증명.** 6명 중 한 명을 갑이라 하자. 좌변은 6명 집합의 크기 $\underline{\quad(1)\quad}$ 부분집합 전체의 수다. 모든 뽑기는 갑 포함 아니면 갑 미포함이고, 두 경우는 $\underline{\quad(2)\quad}$ 않고 전체를 $\underline{\quad(3)\quad}$ — 개수를 더할 수 있다. 갑 포함인 뽑기는 나머지 5명에서 $\underline{\quad(4)\quad}$명을 고르므로 $\binom{5}{1} = 5$가지, 갑 미포함인 뽑기는 5명에서 $\underline{\quad(5)\quad}$명을 고르므로 $\binom{5}{2} = \underline{\quad(6)\quad}$가지다. 따라서 $\binom{6}{2} = 5 + 10 = \underline{\quad(7)\quad}$이다. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 3단계 틀의 각 칸을 통째로 채운다. **명제.** $\binom{n}{n-1} = n$. **세기 증명의 뼈대.** (크기 $n-1$ 부분집합 하나는 무엇 하나로 완전히 결정되는지부터 생각한다.) - ① 세는 대상 선언: $\underline{\quad(1)\quad}$ - ② 세기 장치와 정당성: $\underline{\quad(2)\quad}$ - ③ 결론: $\underline{\quad(3)\quad}$ (이 훈련이 문제 15의 예행연습이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 세기 증명 문제는 3단계 틀(관찰 절)의 ①부터 적고 시작한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "10가지(맞음)"는 0점이고, 세는 대상의 선언과 장치의 정당성("각 쌍이 정확히 2번씩 세어졌으므로 2로 나눈다")까지 적어야 만점이다. 세기 증명 문제는 3단계 틀 ①②③이 그대로 채점표다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** 계산하시오. (a) $\binom{6}{2}$ (b) $\binom{7}{3}$ (c) $\binom{10}{4}$ :::{admonition} 힌트 :class: quotebox dropdown $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$ — 분자에 $k$개만 내려 쓰면 빠르다(12주차 문제 1의 꼬리 약분을 공식에 적용한 꼴). (a)는 훈련 2에서 이미 한 번 계산했다. ::: **2.** $\binom{n}{0} = 1$, $\binom{n}{n} = 1$, $\binom{n}{1} = n$을 각각 "부분집합 세기"의 언어로 설명하시오 (공식 계산 금지). :::{admonition} 힌트 :class: quotebox dropdown 각 값이 "어떤 부분집합들"의 개수인지 직접 나열해 본다 — 확인 5에서 한 번 했다. 크기 0인 부분집합은 무엇 하나뿐인가. ::: **3.** 파스칼 삼각형을 $n = 0$부터 $n = 6$행까지 그리시오. :::{admonition} 힌트 :class: quotebox dropdown 양 끝은 1, 안쪽은 바로 위 두 수의 합 — 파스칼 공식이 곧 작도 규칙이다. $n = 5$행까지는 §1.5에 있으므로 $n = 6$행만 새로 계산하면 된다. ::: **4.** $\binom{8}{3}$과 $\binom{8}{5}$를 각각 계산해 같음을 확인하고, 같은 이유를 한 문장으로 쓰시오 (계산 아닌 세기 언어로). :::{admonition} 힌트 :class: quotebox dropdown 8명 중 3명을 **뽑는** 일이 끝나는 순간, 뽑히지 않은 사람들에게도 어떤 일이 완결된다 — 몇 명이 남는가. "뽑기"와 "남기기"가 별개의 선택인지 생각해 본다. ::: **5.** 로또는 45개 번호 중 6개를 (순서 없이) 고른다. 가짓수를 조합 기호와 공식으로 쓰시오. (참고: 값은 $8{,}145{,}060$) :::{admonition} 힌트 :class: quotebox dropdown "순서 없이"가 대상 선언을 결정한다 — 크기 6 부분집합이다. 기호와 공식만 요구되므로 값 계산은 검산용이다. 분자에 6개를 내려 쓰고 $6! = 720$으로 나눈다. ::: **6.** 학생 5명 중 청소 당번 2명을 뽑는 가짓수를 예제 2.1의 4단계 서술(대상 선언 $\to$ 목록 세기 $\to$ 중복 배수 $\to$ 나누기)로 구하시오. :::{admonition} 힌트 :class: quotebox dropdown 값을 아는 것과 서술이 되는 것은 다르다 — 이 문제의 목적은 서술 순서의 재현이다. 첫 문장은 "결과는 …의 크기 … 부분집합이다"로 시작한다. ::: ### 표준 ●●○ **7.** 남자 5명, 여자 4명 중 남자 2명과 여자 2명으로 위원회를 만드는 가짓수를 곱셈 원리와 조합으로 구하시오. :::{admonition} 힌트 :class: quotebox dropdown (남자 선택, 여자 선택)의 2단계다 — 각 단계 안은 조합, 단계 사이는 곱셈 원리. 곱셈 원리를 쓰려면 여자 쪽 가짓수가 남자 쪽 선택과 무관함을 한 마디 확인해야 한다(12주차 규범 ②). ::: **8.** 이항정리로 $(x + y)^4$과 $(a - b)^4$을 전개하시오. :::{admonition} 힌트 :class: quotebox dropdown 계수는 둘 다 파스칼 $n = 4$행이다. $(a-b)^4$은 $y$ 자리에 $-b$를 넣은 것 — $(-b)^k = (-1)^k b^k$이므로 부호가 한 칸씩 교대한다. ::: **9.** $(2x - 1)^5$의 전개에서 $x^4$의 계수와 상수항을 구하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.3에서 적은 일반항 $\binom{5}{k}(2x)^{5-k}(-1)^k$를 재사용한다. $x^4$은 $5 - k = 4$인 $k$, 상수항은 $x$의 거듭제곱이 0이 되는 $k$다. ::: **10.** 좌표평면에서 $(0,0)$에서 $(4, 3)$까지 오른쪽(R) 또는 위(U)로 한 칸씩만 이동한다. 최단 경로의 수를 "목록과 위치 선택"의 언어로 구하시오. :::{admonition} 힌트 :class: quotebox dropdown 최단 경로 하나는 R 4개와 U 3개를 섞어 적은 길이 7 문자열과 1:1로 대응한다. 문자열은 "U가 놓일 자리"만 정하면 완전히 결정된다 — 7자리 중 3자리를 고르는 일은 어떤 세기인가. ::: **11.** 공식 $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$을 순서 지우기 논증으로 유도하시오 (개념 절 재현 — 백지에서). :::{admonition} 힌트 :class: quotebox dropdown 세 문장이면 된다: ① 반복 없는 길이 $k$ 목록의 수(12주차 문제 12) ② 부분집합 하나당 목록이 정확히 몇 개씩 생기는지 ③ 나눗셈. 훈련 1이 $n = 7, k = 3$으로 한 예행연습이다. ::: **12.** $\binom{5}{2} = \binom{4}{1} + \binom{4}{2}$를 (a) 수치로 확인하고, (b) 예제 2.2의 세기 증명을 이 경우($5$명 중 $2$명, 기준 인물 '갑')로 다시 서술하시오. :::{admonition} 힌트 :class: quotebox dropdown (b)는 예제 2.2의 완성본을 $n = 5$, $k = 2$로 옮겨 적는 일이다. 기준 인물 '갑'을 먼저 세우고, "겹치지 않고 전체를 덮는다"는 문장을 빠뜨리지 않는다 — 그 문장이 덧셈의 자격이다. ::: **13.** $\sum_{k=0}^{n} \binom{n}{k} = 2^n$을 두 가지 방법으로 증명하시오: (a) 이항정리에 대입 (b) 양변이 같은 대상(무엇?)을 세고 있음을 지적. :::{admonition} 힌트 :class: quotebox dropdown (a)는 확인 9에서 했다 — 어떤 수를 대입하면 거듭제곱이 전부 사라지는가. (b)의 "같은 대상"은 $n$원소 집합의 부분집합 전체다. 좌변은 그것을 크기별로, 우변은 원소별 넣음/뺌 목록으로(12주차 문제 13) 센다. ::: **14.** 10명 중 대표 3명을 뽑는다. (a) 특정인 A를 반드시 포함하는 경우의 수, (b) A를 포함하지 않는 경우의 수를 구하고, (c) 두 값의 합이 $\binom{10}{3}$과 같음을 확인한 뒤 이것이 어느 공식의 사례인지 말하시오. :::{admonition} 힌트 :class: quotebox dropdown (a)는 A가 확정이므로 남은 선택만 센다. (c)에서 "포함/미포함이 전체를 겹침 없이 덮는다"는 문장까지 적으면, 이 문제 전체가 어떤 증명의 수치판인지 보인다 — 예제 2.2를 다시 본다. ::: ### 도전 ●●● :::{admonition} 새 도구 — 대응으로 세기 :class: quotebox 두 집합의 원소들이 하나씩 빠짐없이 짝지어지면(1:1 대응) 두 집합의 크기는 같다. 12주차 §1.8에서 부분집합과 넣음/뺌 목록을 짝지어 $2^n$을 얻은 것이 이 논법이었다. 대응으로 개수가 같음을 보이는 서술의 완결 조건은 세 가지다: ① 대응 규칙을 제시한다 ② 서로 다른 것은 서로 다른 것에 대응함을 확인한다 ③ 상대편 어느 것도 빠지지 않음을 확인한다. (이 논법의 정식 언어 — 전단사 — 는 41주차에서 세운다. 지금은 세 조건의 서술로 충분하다.) ::: **15.** $\binom{n}{k} = \binom{n}{n-k}$의 세기 증명을 쓰시오. (힌트: $k$명을 "뽑는 것"과 $n-k$명을 "남기는 것" 사이의 대응) :::{admonition} 힌트 :class: quotebox dropdown 크기 $k$ 선택 하나마다 "남겨진 사람들의 집합"이 하나 정해진다 — 이것이 대응 규칙이다. 위 상자의 조건 ②③을 이 대응에 대해 확인하면 끝난다. 문제 4에서 수치로 만진 것의 일반화이고, 훈련 3이 $k = n-1$인 특수 사례였다. ::: **16.** $n \ge 1$일 때 $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$을 이항정리로 증명하고, 이 등식을 "홀수 크기 부분집합의 수와 짝수 크기 부분집합의 수"에 대한 문장으로 해석하시오. :::{admonition} 힌트 :class: quotebox dropdown 좌변이 이항정리의 우변 꼴이 되는 대입은 $x = 1, y = -1$이다. 해석에서는 $(-1)^k$의 부호에 따라 항을 두 무리로 나눠 음수 항을 반대편으로 넘긴다. $n \ge 1$ 조건이 왜 필요한지도 확인해 본다 — $n = 0$이면 좌변이 얼마인가. ::: **17.** $\binom{n}{2} = \dfrac{n(n-1)}{2}$을 두 가지 방법으로 증명하시오: (a) 공식 계산 (b) 악수 논증(12주차 문제 17의 일반화). :::{admonition} 힌트 :class: quotebox dropdown (b)는 예제 2.1의 4단계 서술을 $n$명으로 일반화하는 것이다 — 목록 $n(n-1)$개, 쌍 하나당 정확히 2개씩. 문자 $n$이 들어와도 서술은 한 글자도 달라지지 않는다. ::: **18.** 평면 위에 어느 세 점도 한 직선 위에 있지 않은 $n$개의 점이 있다. (a) 두 점을 잇는 직선의 개수, (b) 세 점으로 만드는 삼각형의 개수를 조합으로 표현하고, $n = 5$일 때 값을 구하시오. :::{admonition} 힌트 :class: quotebox dropdown "두 점이 직선 하나를 결정한다"가 대응 규칙이다 — 크기 2 부분집합과 직선이 1:1로 짝지어지려면 어떤 조건이 지켜져야 하는가. 문제가 준 일직선 조건이 무엇을 막고 있는지 생각하며 쓴다. ::: **19.** 등식 $k\binom{n}{k} = n\binom{n-1}{k-1}$의 세기 증명을 쓰시오. (힌트: "$n$명 중 위원 $k$명을 뽑고 그중 위원장 1명을 정하는" 가짓수를 두 가지 순서로 세기: ① 위원회 먼저 ② 위원장 먼저) :::{admonition} 힌트 :class: quotebox dropdown 세는 대상은 (위원회, 위원장) 쌍 전체다 — 3단계 틀 ①에 이 선언부터 적는다. 방법 ①은 좌변, 방법 ②는 우변이 되도록 각 단계의 가짓수를 곱셈 원리로 세면, 결론은 "같은 대상을 센 두 결과"라는 표준 문구로 닫힌다. ::: **20.** (서술) 세기 증명(combinatorial proof)이 대수 계산 증명보다 나은 점과 못한 점을 각각 한 가지씩 쓰시오. 그리고 "같은 것을 두 번 센다"가 등식의 증명이 되는 근거를 한 문장으로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 문제 13(두 방법을 다 써 본 문제)과 문제 17에서 두 증명을 나란히 겪었다 — 어느 쪽이 기계적이었고 어느 쪽이 이유를 보여 주었는가. 마지막 물음의 근거는 §1.6의 원리 상자에 있는 한 문장이다. ::: ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 세기 논증의 3단계 틀과 근거 목록(§1.8)만 펴 놓고, 공식 유도(§1.2)와 예제 2.2(파스칼 공식)를 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다: - [ ] $\binom{n}{k}$의 정의(크기 $k$ 부분집합의 개수)와 공식을 쓰고, 순서 지우기 논증으로 유도했다. - [ ] 파스칼 공식의 세기 증명(예제 2.2)을 백지에 재현했다 — 분할의 "겹치지 않고 전체를 덮는다"까지. - [ ] 이항정리를 쓰고, 계수가 $\binom{n}{k}$인 이유("$y$를 고른 괄호 위치의 선택")를 설명했다. - [ ] $x = y = 1$, $x = 1, y = -1$ 대입으로 두 항등식을 얻었다. - [ ] 파스칼 삼각형을 $n = 6$행까지 그렸다. - [ ] 재현한 세기 증명에서 ① 대상 선언 ② 장치와 정당성 ③ 결론의 3단계를 손가락으로 짚을 수 있다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 공식만 기억나고 유도가 안 나온다 | §1.2의 표 — 목록 수를 $k!$로 나누는 자리를 다시 채운다 | | 목록인지 집합인지 헷갈린다 | §1.1과 확인 11 — "직책$\cdot$순서" 유무로 판정한다 | | 세기 증명의 첫 문장이 안 나온다 | 관찰 절의 3단계 틀 — ① 세는 대상 선언부터 적는다 | | 갑 분할 다음이 안 나온다 | 예제 2.2 확인 17 — 서로소$\cdot$완전을 명시한 뒤 각 무리를 센다 | | 이항정리 계수의 이유를 설명 못 한다 | §1.7 확인 8 — $x^2y$를 만드는 목록을 직접 나열한다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $6$ (2) $5$ (3) $3!$ (4) $35$ (5) $4$ ※ (1)(2)에서 마지막 항이 $7 - 3 + 1 = 5$인 것은 12주차 확인 8의 그 자리다. (5)는 $(n-k)! = (7-3)! = 4!$ — 공식의 분모 두 조각($k!$과 $(n-k)!$)을 혼동하지 않는지 확인하는 빈칸이다. ### 빈칸 사다리 — 훈련 2 (1) $2$ (2) 겹치지 (3) 덮는다 (4) $1$ (5) $2$ (6) $10$ (7) $15$ ※ (2)(3)의 두 낱말(서로소$\cdot$완전)이 빠지면 "더할 수 있다"의 근거가 사라진다 — 이 증명에서 생략할 수 없는 자리다. 검산: $\binom{6}{2} = \frac{6 \times 5}{2} = 15$ ✓. ### 빈칸 사다리 — 훈련 3 (1) 세는 대상: $n$명 집합의 크기 $n-1$ 부분집합 전체. (2) 장치: 크기 $n-1$ 부분집합 하나는 "빠진 한 명"으로 완전히 결정된다 — 부분집합과 빠진 사람이 1:1로 대응한다(서로 다른 부분집합은 서로 다른 사람을 빼고, 누구를 빼든 부분집합이 하나 나온다). (3) 결론: 빠진 사람의 선택지는 $n$가지이므로 $\binom{n}{n-1} = n$이다. $\blacksquare$ ※ "뽑을 사람들" 대신 "뺄 사람"을 세는 관점 전환 — 문제 15의 일반형 $\binom{n}{k} = \binom{n}{n-k}$가 이 대응의 완성이다. ### 문제 1 **접근.** 공식 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$을 그대로 쓰기보다, 분자와 $(n-k)!$을 미리 약분한 꼴 $\frac{n(n-1)\cdots(n-k+1)}{k!}$ — 분자에 $k$개만 내려 쓰기 — 이 빠르다. 12주차 문제 1의 꼬리 약분과 같은 요령이다. **풀이.** (a) $\binom{6}{2} = \dfrac{6 \times 5}{2!} = \dfrac{30}{2} = 15$. (b) $\binom{7}{3} = \dfrac{7 \times 6 \times 5}{3!} = \dfrac{210}{6} = 35$. (c) $\binom{10}{4} = \dfrac{10 \times 9 \times 8 \times 7}{4!} = \dfrac{5040}{24} = 210$. **검산.** (a)와 (b)는 파스칼 삼각형에서도 읽힌다 — $n=6$행의 셋째 수 15 (문제 3에서 그린다), $n=7$행 대신 훈련 1의 유도값 35 ✓. **복기.** 분자에 내려 쓰는 개수와 분모의 $k!$이 같은 $k$개다 — 이 대칭이 무너지면(분자 4개에 분모 $3!$ 등) 즉시 오류다. 계산 전에 개수를 맞춰 본다. ### 문제 2 **접근.** 공식 계산이 금지이므로 정의로 돌아간다 — 각 값이 "어떤 부분집합들"의 개수인지 직접 나열한다. 확인 5에서 한 번 했다. **풀이.** $\binom{n}{0} = 1$: 크기 0인 부분집합은 원소를 하나도 갖지 않는 집합 — $\emptyset$ 하나뿐이다. 따라서 개수는 1이다. $\binom{n}{n} = 1$: 크기 $n$인 부분집합은 $n$개 원소를 전부 담아야 하므로 전체집합 자신 하나뿐이다. 따라서 개수는 1이다. $\binom{n}{1} = n$: 크기 1인 부분집합은 $\{x\}$ 꼴이고, 원소 $x$를 하나 고를 때마다 정확히 하나씩 생긴다. 원소가 $n$개이므로 개수는 $n$이다. **복기.** 끝값은 공식보다 정의가 빠르고 확실하다 — "애매하면 정의로 돌아간다"(1주차 §1.5)가 세기에서도 그대로 작동한다. ### 문제 3 **접근.** 작도 규칙은 파스칼 공식 그 자체다 — 각 행의 양 끝은 $\binom{n}{0} = \binom{n}{n} = 1$, 안쪽은 바로 위 두 수의 합. $n = 5$행까지는 §1.5에 있으므로 $n = 6$행만 새로 만든다. **풀이.** ```text n=0: 1 n=1: 1 1 n=2: 1 2 1 n=3: 1 3 3 1 n=4: 1 4 6 4 1 n=5: 1 5 10 10 5 1 n=6: 1 6 15 20 15 6 1 ``` $n = 6$행의 안쪽 계산: $1 + 5 = 6$, $5 + 10 = 15$, $10 + 10 = 20$, $10 + 5 = 15$, $5 + 1 = 6$. **검산.** 행의 합이 $2^n$이어야 한다(문제 13): $1 + 6 + 15 + 20 + 15 + 6 + 1 = 64 = 2^6$ ✓. ### 문제 4 **접근.** 계산으로 같음을 확인한 뒤, 이유를 세기 언어로 — "3명을 뽑는 것"과 "5명을 남기는 것"이 별개의 두 선택인지 생각한다. **풀이.** 계산: $$ \binom{8}{3} = \frac{8 \times 7 \times 6}{3!} = \frac{336}{6} = 56, \qquad \binom{8}{5} = \frac{8!}{5!\,3!} = \frac{8 \times 7 \times 6}{6} = 56 $$ — 일치한다. 이유: 8명 중 3명을 **뽑는** 선택과 5명을 **남기는** 선택은 같은 결정의 두 이름이므로 — 뽑기 하나가 끝나는 순간 남기기 하나도 확정된다 — 가짓수가 같다. **복기.** 이 "뽑기 $\leftrightarrow$ 남기기"를 임의의 $n, k$로 일반화한 것이 문제 15다 — 수치 확인은 이 사례만 덮고, 일반 증명이 전부를 덮는다. ### 문제 5 **접근.** "순서 없이"가 대상 선언을 결정한다 — 뽑기 결과는 45개 번호 집합의 크기 6 부분집합이다. 기호와 공식으로 쓰는 것이 요구이고, 값은 검산이다. **풀이.** 가짓수는 45개짜리 집합의 크기 6 부분집합의 수이므로 $$ \binom{45}{6} = \frac{45!}{6!\,39!} $$ 이다. 값을 계산하면 분자에 6개를 내려 쓰고 $6! = 720$으로 나눈다: $$ \binom{45}{6} = \frac{45 \times 44 \times 43 \times 42 \times 41 \times 40}{720} = \frac{5{,}864{,}443{,}200}{720} = 8{,}145{,}060 $$ — 문제의 참고값과 일치한다 ✓. (1등 확률이 약 814만분의 1인 이유가 이 분모다.) **복기.** $\frac{45!}{6!\,39!}$에서 $39!$이 분자의 꼬리를 통째로 지워 $45 \times \cdots \times 40$만 남는다 — 팩토리얼 꼴과 내려 쓰기 꼴은 같은 수의 두 표기다(12주차 문제 12의 공식을 거꾸로 읽기). ### 문제 6 **접근.** 값(10)을 아는 것과 서술이 되는 것은 다르다 — 이 문제의 목적은 예제 2.1의 4단계 서술 순서를 그대로 재현하는 것이다. 채점 기준도 값이 아니라 네 문장의 존재다. **풀이.** ① 대상 선언: 당번 뽑기의 결과는 직책이 없으므로 5명 집합의 크기 2 부분집합이다. ② 목록 세기: 순서 있는 (첫째, 둘째) 목록으로는 1번째 5가지, 2번째 4가지 — 곱셈 원리에 의해 $5 \times 4 = 20$개다. ③ 중복 배수: 각 부분집합 $\{A, B\}$는 목록 $(A, B)$와 $(B, A)$의 $2! = 2$개로 정확히 두 번씩 세어졌다. ④ 나누기: 따라서 가짓수는 $20 \div 2 = \binom{5}{2} = 10$가지다. $\blacksquare$ **복기.** ③의 "정확히"가 나눗셈의 자격 조건이다 — 이 낱말이 빠진 답안은 장치의 정당성(3단계 틀 ②)이 빠진 것이다. ### 문제 7 **접근.** (남자 선택, 여자 선택)의 2단계 구조다. 각 단계의 안쪽은 순서 없는 뽑기이므로 조합이고, 단계 사이는 곱셈 원리다. 곱셈 원리의 자격 — 2단계의 가짓수가 1단계의 결과와 무관함 — 을 한 마디 확인한다(12주차 규범 ②). **풀이.** 위원회는 (남자 2명의 집합, 여자 2명의 집합) 쌍으로 결정된다. 남자 2명의 선택은 $\binom{5}{2} = \frac{5 \times 4}{2} = 10$가지, 여자 2명의 선택은 $\binom{4}{2} = \frac{4 \times 3}{2} = 6$가지다. 어느 남자들을 뽑았든 여자 쪽 선택지는 6가지 그대로이므로 — 두 선택은 서로 다른 사람들 위에서 일어난다 — 곱셈 원리에 의해 $10 \times 6 = 60$가지다. $\blacksquare$ **복기.** 조합(단계 안)과 곱셈 원리(단계 사이)의 역할 분담 — "몇 명 중 몇 명"이 보이면 조합, "그리고 또"가 보이면 곱셈이다. 14주차의 덧셈 원리까지 합류하면 세기 도구 세 개의 분업이 완성된다. ### 문제 8 **접근.** 계수는 둘 다 파스칼 $n = 4$행 $1, 4, 6, 4, 1$이다. $(a-b)^4$은 이항정리의 $y$ 자리에 $-b$를 넣은 것 — $(-b)^k = (-1)^k b^k$이므로 $k$가 홀수인 항만 음수가 된다. **풀이.** $(x+y)^4$: 일반항 $\binom{4}{k} x^{4-k} y^k$에 $k = 0, 1, 2, 3, 4$를 넣으면 $$ (x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4 $$ 이다. $(a-b)^4$: $x$ 자리 $a$, $y$ 자리 $-b$를 넣으면 일반항이 $\binom{4}{k} a^{4-k} (-1)^k b^k$이므로 부호가 교대한다: $$ (a-b)^4 = a^4 - 4a^3b + 6a^2b^2 - 4ab^3 + b^4 $$ **검산.** $(x+y)^4$에 $x = y = 1$: 좌변 $2^4 = 16$, 우변 $1+4+6+4+1 = 16$ ✓. $(a-b)^4$에 $a = b = 1$: 좌변 $0$, 우변 $1-4+6-4+1 = 0$ ✓ — 문제 16의 교대합 등식이 여기서도 확인된다. ### 문제 9 **접근.** 예제 2.3에서 적어 둔 일반항 $\binom{5}{k}(2x)^{5-k}(-1)^k$를 재사용한다(근거 ④ — 부품 재사용). $x^4$은 $5 - k = 4$에서 $k = 1$, 상수항은 $x$의 거듭제곱이 0이 되는 $5 - k = 0$, 즉 $k = 5$다. **풀이.** $x^4$ 항 ($k = 1$): $$ \binom{5}{1}(2x)^4(-1)^1 = 5 \cdot 16x^4 \cdot (-1) = -80x^4 $$ 이므로 $x^4$의 계수는 $-80$이다. 상수항 ($k = 5$): $$ \binom{5}{5}(2x)^0(-1)^5 = 1 \cdot 1 \cdot (-1) = -1 $$ 이므로 상수항은 $-1$이다. **검산.** 상수항은 $x = 0$ 대입으로도 나온다: $(2 \cdot 0 - 1)^5 = (-1)^5 = -1$ ✓. **복기.** 전개 전체를 쓰지 않고 일반항에서 필요한 $k$만 지목한다 — 예제 2.3과 이 문제가 같은 패턴의 두 실행이다. ### 문제 10 **접근.** 대상을 목록으로 번역하는 것이 전부다. 최단 경로는 오른쪽 4번, 위쪽 3번을 어떤 순서로 밟는가로 완전히 결정되므로, R 4개와 U 3개로 된 길이 7 문자열과 1:1로 대응한다. 문자열은 다시 "U가 놓일 위치"의 선택으로 결정된다. **풀이.** 최단 경로는 총 $4 + 3 = 7$걸음이고, 각 경로는 걸음의 기록 — R 4개와 U 3개를 섞은 길이 7 문자열 — 과 1:1로 대응한다(경로가 다르면 어느 걸음에선가 방향이 갈리므로 문자열이 다르고, 문자열 하나는 경로 하나를 정확히 그린다). 그런 문자열은 7개 자리 중 U가 놓일 3자리를 고르면 완전히 결정되고(남은 자리는 전부 R), 자리의 선택은 7개짜리 집합의 크기 3 부분집합 선택이다. 따라서 경로의 수는 $$ \binom{7}{3} = \frac{7 \times 6 \times 5}{3!} = 35 $$ 가지다. $\blacksquare$ **복기.** "R의 위치 4자리"를 골라도 된다 — $\binom{7}{4} = 35 = \binom{7}{3}$이고, 이 일치가 문제 15의 등식이다. 경로가 문자열로, 문자열이 부분집합으로 옮겨지는 이중 번역이 이 문제의 뼈대다. ### 문제 11 **접근.** §1.2의 재현이다 — 세 문장이면 된다: ① 반복 없는 길이 $k$ 목록의 수 ② 부분집합 하나당 목록이 정확히 $k!$개씩 ③ 나눗셈. ②의 "정확히"와 "$k!$의 출처(원소 $k$개의 나열 수)"가 채점 포인트다. **풀이.** $n$개짜리 집합에서 반복 없는 길이 $k$ 목록은 $\frac{n!}{(n-k)!}$개다(12주차 문제 12 — 곱셈 원리). 크기 $k$ 부분집합 하나마다 그것을 일렬로 나열한 목록이 정확히 $k!$개씩 생긴다 — 원소 $k$개를 전부 세우는 가짓수다(12주차 정의 12.2). 목록은 순서를 기억하고 부분집합은 기억하지 않으므로, 목록 전체는 부분집합 각각을 정확히 $k!$번씩 센 것이다. 따라서 부분집합의 수는 $$ \binom{n}{k} = \frac{n!}{(n-k)!} \div k! = \frac{n!}{k!\,(n-k)!} $$ 이다. $\blacksquare$ **복기.** 이 유도는 세기 논증이기도 하다(확인 7) — 목록 전체라는 한 집합을 자리별(곱셈 원리)과 부분집합별($k!$개씩 묶음)의 두 방법으로 센 것이다. 공식을 잊어도 이 세 문장에서 언제든 재구성할 수 있다. ### 문제 12 **접근.** (a)는 양변을 각각 계산해 대조한다. (b)는 예제 2.2의 완성본을 $n = 5$, $k = 2$로 옮겨 적되, "겹치지 않고 전체를 덮는다"는 문장을 빠뜨리지 않는 것이 채점 포인트다 — 그 문장이 덧셈의 자격이다. **풀이.** (a) 좌변 $\binom{5}{2} = \frac{5 \times 4}{2} = 10$. 우변 $\binom{4}{1} + \binom{4}{2} = 4 + \frac{4 \times 3}{2} = 4 + 6 = 10$ — 일치 ✓. (b) 5명 중 한 명을 갑이라 하자. 좌변은 5명 집합의 크기 2 부분집합(2인조) 전체의 수다. 모든 2인조는 갑을 포함하거나 포함하지 않거나 둘 중 정확히 하나이므로, 두 경우는 겹치지 않고 전체를 덮는다 — 개수를 더할 수 있다. 갑을 포함하는 2인조는 나머지 4명 중 1명만 더 고르면 되므로 $\binom{4}{1} = 4$가지이고, 갑을 제외한 2인조는 4명 중 2명이므로 $\binom{4}{2} = 6$가지다. 따라서 $\binom{5}{2} = 4 + 6$이다. $\blacksquare$ **복기.** 일반 증명(예제 2.2)을 구체 사례로 다시 쓰는 연습 — 문자 $n, k$에 수를 넣어도 모든 문장이 그대로 작동함을 확인하는 것은 1주차 확인 13의 대입 시뮬레이션과 같은 훈련이다. ### 문제 13 **접근.** (a)는 대입 한 줄 — 확인 9에서 했다. (b)의 핵심은 "같은 대상"의 지목이다: 양변 모두 $n$원소 집합의 **부분집합 전체**를 센다. 좌변은 크기별로 나눠 세는데, 이때 무리가 $n+1$개이므로 두 무리짜리가 아니라 **일반형 덧셈 원리**를 인정하고 쓴다(§1.8). 우변은 원소별 넣음/뺌 목록으로(12주차 문제 13) 센다. **풀이.** (a) 이항정리 $(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$에 $x = y = 1$을 대입하면(근거 ③) 좌변은 $(1+1)^n = 2^n$, 우변은 모든 거듭제곱이 1이 되어 $\sum_{k=0}^{n} \binom{n}{k}$이다. 따라서 $\sum_{k=0}^{n} \binom{n}{k} = 2^n$이다. $\blacksquare$ (b) 양변이 함께 세는 대상은 $n$원소 집합의 부분집합 전체다. 좌변: 부분집합을 크기별로 분류하면 크기 $k$인 것이 $\binom{n}{k}$개씩이고(정의 13.1), 크기가 다른 무리끼리는 겹치지 않고 $k = 0$부터 $n$까지가 전체를 덮으므로 — 무리가 셋 이상일 때도 개수를 더할 수 있다는 사실은 지금은 인정하고 쓴다(일반형 덧셈 원리, 14주차에서 공식화$\cdot$31주차에서 완결) — 총수는 $\sum_{k=0}^{n} \binom{n}{k}$이다. 우변: 부분집합은 원소별 넣음/뺌의 길이 $n$ 목록과 1:1로 대응하므로(12주차 §1.8, 문제 13) 총수는 $2^n$이다. 같은 대상을 센 두 결과이므로 두 값은 같다. $\blacksquare$ **복기.** 한 등식에 대수 증명(대입)과 세기 증명(두 방법)이 나란히 선 첫 문제다 — 문제 20의 재료가 여기서 만들어진다. ### 문제 14 **접근.** (a)는 A가 확정이므로 남은 선택만 센다. (b)는 A를 무대에서 빼고 센다. (c)는 두 경우가 전체의 서로소 분할임을 말하고, 등식의 정체를 지목한다 — 예제 2.2의 수치판이다. **풀이.** (a) A를 반드시 포함하므로 A는 확정이고, 나머지 9명 중 2명을 고른다: $\binom{9}{2} = \frac{9 \times 8}{2} = 36$가지. (b) A를 제외한 9명 중 3명을 고른다: $\binom{9}{3} = \frac{9 \times 8 \times 7}{6} = 84$가지. (c) $36 + 84 = 120$이고 $\binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$ — 일치 ✓. 모든 3인조는 A를 포함하거나 포함하지 않거나 둘 중 정확히 하나이므로 두 경우는 전체를 겹침 없이 덮고, 따라서 이 등식은 **파스칼 공식** $\binom{10}{3} = \binom{9}{2} + \binom{9}{3}$의 사례다(기준 인물 = A). **복기.** "특정인 포함/미포함"으로 쪼개는 수는 세기 문제의 상비 도구다 — 파스칼 공식은 그 도구를 일반형으로 등록해 둔 것이고, 14주차 문제 16에서 같은 분할이 다시 나온다. ### 문제 15 **접근.** §4의 상자(대응으로 세기)의 첫 실전이다. 대응 규칙: 크기 $k$ 선택 $X$마다 "남겨진 사람들의 집합"이 하나 정해진다. 조건 ②(다른 것은 다른 것에)와 ③(빠짐없이)을 이 대응에 대해 확인하면 두 모임의 크기가 같다. **풀이.** $n$명 집합에서 $k$명을 뽑는 각 선택 $X$(크기 $k$ 부분집합)에 대해, 남겨진 $n-k$명의 집합 — $X$에 들지 않은 원소 전체, 5주차의 여집합 $X^c$ — 가 하나 정해진다. 이 대응은 크기 $k$ 선택 전체와 크기 $n-k$ 선택 전체를 1:1로 짝짓는다: 서로 다른 $X$는 남기는 사람들도 다르므로 서로 다른 $X^c$를 주고(②), 크기 $n-k$인 어떤 집합 $Y$든 그 여집합 $Y^c$(크기 $k$)를 뽑는 선택에서 나오므로 빠지는 것이 없다(③). 세 조건 ①②③을 모두 확인했으므로 두 모임은 1:1로 대응하고, 1:1로 대응하는 두 모임의 개수는 같다(§4 도구 상자). 따라서 $$ \binom{n}{k} = \binom{n}{n-k} $$ 이다. $\blacksquare$ **검산.** 문제 4의 $\binom{8}{3} = \binom{8}{5} = 56$이 이 등식의 사례다 ✓. **복기.** 세지 않고 짝지어서 개수의 같음을 얻었다 — 분할$\cdot$나눗셈에 이은 세 번째 세기 장치다. 이 "대응으로 크기 비교"가 41주차에서 전단사라는 이름을 얻고, 48주차에서 무한집합의 크기 비교 도구로 완성된다. ### 문제 16 **접근.** 좌변이 이항정리 우변의 꼴이 되는 대입은 $x = 1, y = -1$이다. 해석에서는 $(-1)^k$의 부호대로 항을 두 무리(짝수 $k$ / 홀수 $k$)로 나눠 음수 항을 반대편으로 넘긴다. $n \ge 1$ 조건의 역할도 확인한다. **풀이.** 이항정리에 $x = 1, y = -1$을 대입하면(근거 ③) 우변은 $\sum_{k=0}^{n} \binom{n}{k} 1^{n-k} (-1)^k = \sum_{k=0}^{n} (-1)^k \binom{n}{k}$ 이고, 좌변은 $(1 + (-1))^n = 0^n$이다. $n \ge 1$이면 $0^n = 0$이므로 $$ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 $$ 이다. $\blacksquare$ ($0^n = 0$은 $n \ge 1$에서만 참이다. $n = 0$이면 이항정리의 좌변은 $0^0 = 1$이고 문제의 합도 $\sum_{k=0}^{0}(-1)^k\binom{0}{k} = 1$이므로 등식 $= 0$이 거짓이 된다 — 조건 $n \ge 1$이 정확히 이 경우를 걸러 낸다.) 해석: 등식에서 $(-1)^k$가 $+$인 항(짝수 $k$)과 $-$인 항(홀수 $k$)을 나눠 음수 항을 우변으로 넘기면 $$ \sum_{k \text{ 짝수}} \binom{n}{k} = \sum_{k \text{ 홀수}} \binom{n}{k} $$ — **크기가 짝수인 부분집합과 크기가 홀수인 부분집합은 개수가 같다.** 문제 13과 결합하면 그 공통값은 전체 $2^n$의 절반, 각각 $2^{n-1}$개다. **검산.** $n = 3$: 짝수 크기 $1 + 3 = 4$, 홀수 크기 $3 + 1 = 4$ — 같고, $4 = 2^{3-1}$ ✓. ### 문제 17 **접근.** 같은 등식을 두 길로 — (a)는 공식에서 팩토리얼 약분, (b)는 12주차 문제 17의 악수 논증을 $n$명으로 일반화. 문자 $n$이 들어와도 예제 2.1의 4단계 서술이 한 글자도 달라지지 않음을 확인하는 것이 (b)의 목적이다. **풀이.** (a) 공식 계산: $$ \binom{n}{2} = \frac{n!}{2!\,(n-2)!} = \frac{n(n-1)(n-2)!}{2 \cdot (n-2)!} = \frac{n(n-1)}{2} $$ — $(n-2)!$이 분자$\cdot$분모에서 약분된다(근거 ③). $\blacksquare$ (b) 악수 논증: $n$명이 서로 한 번씩 악수할 때, 악수 쌍은 $n$명 집합의 크기 2 부분집합이다. 순서 있는 목록 (먼저 세는 사람, 나중 세는 사람)은 1번째 $n$가지, 2번째 $n-1$가지로 곱셈 원리에 의해 $n(n-1)$개이고, 각 쌍 $\{A, B\}$는 목록 $(A,B), (B,A)$의 정확히 2개로 세어졌다. 따라서 쌍의 수는 $\frac{n(n-1)}{2}$이고, 같은 대상(크기 2 부분집합 전체)을 정의 13.1로 세면 $\binom{n}{2}$이므로 두 결과는 같다: $\binom{n}{2} = \frac{n(n-1)}{2}$. $\blacksquare$ **검산.** $n = 5$: $\frac{5 \times 4}{2} = 10$ — 12주차 문제 17의 나열값과 일치 ✓. **복기.** (a)는 빠르고 (b)는 이유를 보여 준다 — $n(n-1)$이 목록의 수이고 2가 쌍 하나당 나열의 수라는 것이 (b)에서만 보인다. 문제 20의 서술이 이 대조의 언어화다. ### 문제 18 **접근.** 대응으로 세기다 — "두 점이 직선 하나를 결정한다", "세 점이 삼각형 하나를 결정한다"가 대응 규칙이고, 문제의 일직선 조건이 이 대응의 1:1을 지키는 장치다. **풀이.** (a) 서로 다른 두 점은 직선을 정확히 하나 결정하고, 어느 세 점도 한 직선 위에 없으므로 서로 다른 두 점 쌍이 같은 직선을 만들 수 없다 — 서로 다른 두 쌍의 합집합은 점 3개 이상이고, 두 쌍이 같은 직선을 주면 그 점들이 전부 한 직선 위에 놓여(예: $\{A,B\}$와 $\{A,C\}$면 $A, B, C$가, $\{A,B\}$와 $\{C,D\}$면 네 점이 — 특히 $A, B, C$가 — 공선) 조건에 어긋난다. 따라서 직선과 크기 2 부분집합이 1:1로 대응하고, 직선의 수는 $\binom{n}{2}$이다. $n = 5$: $\binom{5}{2} = \frac{5 \times 4}{2} = 10$개. (b) 한 직선 위에 있지 않은 세 점은 삼각형을 정확히 하나 결정하고, 조건에 의해 어느 세 점도 퇴화하지 않는다. 또 삼각형은 그 꼭짓점 세 개를 결정하므로, 서로 다른 3점 집합은 서로 다른 삼각형을 준다. 따라서 삼각형과 크기 3 부분집합이 1:1로 대응한다. 삼각형의 수는 $\binom{n}{3}$이다. $n = 5$: $\binom{5}{3} = \frac{5 \times 4 \times 3}{6} = 10$개. **복기.** 조건("어느 세 점도 일직선 위에 없다")은 장식이 아니라 대응의 1:1을 보장하는 부품이다 — 조건이 무너지면 점 쌍들이 직선을 공유하는 중복과 삼각형이 되지 못하는 퇴화가 생겨 세기가 무너진다. ### 문제 19 **접근.** 힌트의 대상 — "$n$명 중 위원 $k$명을 뽑고 그중 위원장 1명을 정하는" 결과, 곧 (위원회, 위원장) 쌍 전체 — 을 3단계 틀 ①로 선언하고, 두 가지 **순서**로 센다: 위원회부터 뽑고 위원장을 지명하면 좌변, 위원장부터 뽑고 위원을 충원하면 우변이 나온다. **풀이.** ($1 \le k \le n$인 경우를 센다. $k = 0$이면 위원장을 지명할 수 없어 세는 대상 자체가 없고, 좌변은 $0 \cdot \binom{n}{0} = 0$, 우변의 $\binom{n-1}{-1}$은 정의 13.1이 다루는 범위 밖이다 — 등식은 $k \ge 1$에서 주장한다.) 세는 대상: (위원회, 위원장) 쌍 전체 — 위원회는 $n$명 중 $k$명의 집합이고, 위원장은 그 위원 중 1명이다. 방법 ① (위원회 먼저): 위원회를 $\binom{n}{k}$가지로 뽑고, 그 안에서 위원장을 $k$가지로 지명한다. 위원장 선택지 수는 어느 위원회든 $k$로 일정하므로 곱셈 원리에 의해 $\binom{n}{k} \cdot k$가지. 방법 ② (위원장 먼저): 위원장을 전체 $n$명 중에서 $n$가지로 뽑고, 나머지 위원 $k-1$명을 남은 $n-1$명에서 $\binom{n-1}{k-1}$가지로 충원한다. 충원 가짓수는 누가 위원장이든 일정하므로 곱셈 원리에 의해 $n \cdot \binom{n-1}{k-1}$가지. 같은 대상을 센 두 결과이므로 $$ k\binom{n}{k} = n\binom{n-1}{k-1} $$ 이다. $\blacksquare$ **검산.** $n = 4, k = 2$: 좌변 $2 \cdot \binom{4}{2} = 2 \cdot 6 = 12$, 우변 $4 \cdot \binom{3}{1} = 4 \cdot 3 = 12$ ✓. **복기.** 분할(예제 2.2)$\cdot$나눗셈(예제 2.1)$\cdot$대응(문제 15)에 이어 네 번째 장치 — **같은 대상을 두 순서로 세기**. 세는 대상을 쌍(구조물)으로 잡는 설계가 핵심이고, 이 설계 감각은 연습으로만 생긴다. ### 문제 20 **접근.** 문제 13(대입 증명과 세기 증명을 나란히)과 문제 17(공식 계산과 악수 논증)에서 두 양식을 다 겪었다 — 그 경험을 언어화한다. 마지막 물음의 근거는 §1.6 원리 상자의 문장이다. **풀이.** (예시 답안) 나은 점: 세기 증명은 등식이 **왜** 성립하는지 — 양변이 같은 대상의 어떤 두 관점인지 — 를 드러내므로, 결과를 기억하기 쉽고 비슷한 등식으로 일반화하는 실마리를 준다(문제 17에서 $n(n-1)$과 2의 정체가 보인 것처럼). 못한 점: 알맞은 "세는 대상"과 장치(분할$\cdot$대응$\cdot$순서)를 설계해야 하므로 발상이 필요하고 기계적으로 되지 않는다 — 대수 계산은 통분$\cdot$약분만 따라가면 항상 끝에 도달한다. 근거: 하나의 유한집합의 크기는 세는 방법과 무관하게 하나로 정해진 수이므로, 두 방법이 같은 집합을 센다는 것이 확인되면 두 결과는 같을 수밖에 없다. **복기.** 이 근거 문장이 §1.8에서 등록한 근거 ④(세기 논증의 원리) 그 자체다 — 이번 주의 모든 세기 증명이 마지막 줄에서 이 한 문장에 기대고 있다. --- **다음 주 예고:** 예제 2.2가 인정하고 쓴 사실 — 서로소이면 개수를 더할 수 있다 — 를 덧셈 원리로 정식화하고, 겹침이 있을 때의 정확한 셈법인 포함–배제 원리 $|A \cup B| = |A| + |B| - |A \cap B|$를 증명한다(5주차 문제 13의 빚 회수). 그리고 3부 전체를 총정리 모의시험으로 마감한다. 이번 주의 3단계 틀 — 대상 선언, 장치의 정당성, 결론 — 이 그대로 채점 기준이 된다.