13주차 · 강의 — 예제 · 연습 · 해설

13주차 · 강의 — 예제 · 연습 · 해설#

예제 — 조합과 파스칼 공식을 함께 만들기#

완성된 풀이를 먼저 보이지 않는다. 설계부터 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 조합 계산과 그 의미#

문제. 5명 중 대표 2명(직책 없음)을 뽑는 가짓수를 구하시오.

설계 — 쓰기 전에 정하는 두 가지. 세기 답안의 출발점은 세는 대상의 선언(12주차 규범 ①)이고, 도착점은 개수와 그 근거다. 번역표로 정리하면 —

말

세기 언어 번역

세는 대상 (출발점)

대표 2명의 뽑기 결과

5명 집합의 크기 2 \(\underline{\quad(?)\quad}\)

목표 (도착점)

가능한 뽑기 전부의 수

그런 부분집합의 개수

전략 (셀 방법)

바로 세기 어려우면 목록을 경유

목록으로 세고, 각 대상이 정확히 몇 번 세어졌는지로 나눈다

확인 11. 대상 칸의 빈칸을 채워 보자. 문제 문장의 어느 조건이 이 번역을 결정하는가?

답

부분집합이다. 결정하는 조건은 “직책 없음” — 직책이 있으면 (회장,

부회장)처럼 순서 있는 목록이고(12주차 예제 2.1), 없으면 \(\{A, B\}\)라는

집합이다. §1.1이 보여 주었듯 이 선언이 틀리면 이후 계산이 전부 옳아도

답이 두 배가 된다 — 목록인가 집합인가가 세기 답안의 첫 갈림길이다.

1단계 — 대상을 선언한다. 첫 문장의 임무는 세는 대상의 정체를 못 박는 것이다.

확인 12. 첫 문장을 완성해 보자: “뽑는 결과는 5명 집합의 크기 \(\underline{\quad}\)인 \(\underline{\qquad}\)이다.”

답

“크기 2인 부분집합이다.” 확인 11의 번역을 답안의 첫 줄로 옮겼을

뿐이다 — 설계가 되어 있으면 첫 문장은 창작이 아니라 옮겨 적기다.

2단계 — 목록으로 일단 센다. 부분집합은 바로 세기 어렵지만 목록은 12주차 도구로 세어진다. 일부러 순서를 붙여 세는 것이다.

확인 13. 둘째 문장을 완성해 보자: “순서 있는 목록으로는 \(\underline{\quad} \times \underline{\quad} = \underline{\quad}\)개다.”

답

\(5 \times 4 = 20\)개. (첫째, 둘째)의 반복 없는 길이 2 목록 — 1번째 5가지,

2번째 4가지, 곱셈 원리(근거 ④). §1.1의 시도와 같은 계산이지만, 이번에는

이것이 최종 답이 아니라 경유지임을 알고 세는 점이 다르다.

3단계 — 몇 번씩 세어졌는지 확인한다. 나눗셈의 자격을 만드는 문장이다.

확인 14. 셋째 문장을 완성해 보자: “각 부분집합 \(\{A, B\}\)는 목록 \(\underline{\quad}\)와 \(\underline{\quad}\)의 \(\underline{\quad}\)개로 중복 계산되었다.”

답

\((A, B)\)와 \((B, A)\) — \(2! = 2\)개. 크기 2 집합 하나를 나열하는 가짓수다.

“정확히 2개씩”이라는 균일성이 핵심이다 — 부분집합마다 부푼 배수가

다르다면 한 번의 나눗셈으로 되돌릴 수 없다(문제 18의 일직선 조건이

정확히 이 균일성을 지키는 장치다).

4단계 — 나누어 마무리한다.

확인 15. 마지막 문장을 완성해 보자: “따라서 \(\binom{5}{2} = \underline{\quad} \div \underline{\quad} = \underline{\quad}\)가지이다.”

답

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

이번에는 설계만 함께 하고, 증명 본문은 완성본으로 본다. 세기 논증의 설계는 두 가지를 정하는 일이다 — ① 두 변이 함께 세는 하나의 집합 ② 우변의 모양을 만들어 줄 세기 방식.

확인 16. 좌변 \(\binom{n}{k}\)가 세는 집합은 무엇인가. 그리고 우변이 두 항의 합이라는 사실은, 그 집합을 어떻게 다루라는 신호인가?

답

좌변은 \(n\)명 집합의 크기 \(k\) 부분집합 전체를 센다. 우변의 합 꼴은 그

전체를 겹치지 않는 두 무리로 쪼개어(서로소 분할) 각각 세라는 신호다 —

서로소인 두 무리로 나뉘면 개수를 더할 수 있다(덧셈 원리, 14주차에서

공식화 — 지금은 인정하고 쓴다). 세기 논증의 설계는 이렇게 목표 식의

생김새에서 거꾸로 읽어 낸다.

확인 17. 우변의 두 항은 둘 다 \(n-1\)명에서 뽑는 개수다 — 한 사람이 특별 취급된다는 신호다. 그 한 사람(갑이라 부르자)을 기준으로, 크기 \(k\) 뽑기 전체를 어떻게 두 무리로 나누면 되는가?

답

“갑을 포함하는 뽑기”와 “갑을 포함하지 않는 뽑기”로 나눈다. 어떤 뽑기든

갑을 포함하거나 포함하지 않거나 둘 중 정확히 하나이므로, 두 무리는 겹치지

않고 전체를 덮는다. 갑 포함 무리: 갑은 확정이니 나머지 \(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\)의 계수를 구하시오.

이번에는 설계부터 스스로 해 보자.

확인 18. 설계 두 가지를 정해 보자. ① 전개의 계수 다섯 개는 어디서 얻는가. ② \((2x-1)^5\)에 이항정리를 적용하려면 정리의 \(x, y\) 자리에 각각 무엇을 넣어야 하는가.

답

① 파스칼 삼각형의 \(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}\)

확인 19. 표의 빈칸 (1)(2)(3)을 채워 보자.

답

(1) \(n\)명 집합의 크기 \(k\) 부분집합 전체 (2) \(2\) (\(= 2!\)) (3) 겹치지.

장치는 달라도 — 중복 배수로 나누기, 서로소 분할로 더하기 — 세 걸음은

같다: 무엇을 세는지 선언하고, 장치의 정당성을 명시하고, 두 셈을 잇는다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

세기 논증의 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단계 틀(관찰 절)의 ①부터 적고 시작한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “10가지(맞음)”는 0점이고, 세는 대상의

선언과 장치의 정당성(“각 쌍이 정확히 2번씩 세어졌으므로 2로 나눈다”)까지

적어야 만점이다. 세기 증명 문제는 3단계 틀 ①②③이 그대로 채점표다.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. 계산하시오. (a) \(\binom{6}{2}\) (b) \(\binom{7}{3}\) (c) \(\binom{10}{4}\)

힌트

\(\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\)을 각각 “부분집합 세기”의 언어로 설명하시오 (공식 계산 금지).

힌트

각 값이 “어떤 부분집합들”의 개수인지 직접 나열해 본다 — 확인 5에서 한 번

했다. 크기 0인 부분집합은 무엇 하나뿐인가.

3. 파스칼 삼각형을 \(n = 0\)부터 \(n = 6\)행까지 그리시오.

힌트

양 끝은 1, 안쪽은 바로 위 두 수의 합 — 파스칼 공식이 곧 작도 규칙이다.

\(n = 5\)행까지는 §1.5에 있으므로 \(n = 6\)행만 새로 계산하면 된다.

4. \(\binom{8}{3}\)과 \(\binom{8}{5}\)를 각각 계산해 같음을 확인하고, 같은 이유를 한 문장으로 쓰시오 (계산 아닌 세기 언어로).

힌트

8명 중 3명을 뽑는 일이 끝나는 순간, 뽑히지 않은 사람들에게도 어떤 일이

완결된다 — 몇 명이 남는가. “뽑기”와 “남기기”가 별개의 선택인지 생각해 본다.

5. 로또는 45개 번호 중 6개를 (순서 없이) 고른다. 가짓수를 조합 기호와 공식으로 쓰시오. (참고: 값은 \(8{,}145{,}060\))

힌트

“순서 없이”가 대상 선언을 결정한다 — 크기 6 부분집합이다. 기호와 공식만

요구되므로 값 계산은 검산용이다. 분자에 6개를 내려 쓰고 \(6! = 720\)으로

나눈다.

6. 학생 5명 중 청소 당번 2명을 뽑는 가짓수를 예제 2.1의 4단계 서술(대상 선언 \(\to\) 목록 세기 \(\to\) 중복 배수 \(\to\) 나누기)로 구하시오.

힌트

값을 아는 것과 서술이 되는 것은 다르다 — 이 문제의 목적은 서술 순서의

재현이다. 첫 문장은 “결과는 …의 크기 … 부분집합이다”로 시작한다.

표준 ●●○#

7. 남자 5명, 여자 4명 중 남자 2명과 여자 2명으로 위원회를 만드는 가짓수를 곱셈 원리와 조합으로 구하시오.

힌트

(남자 선택, 여자 선택)의 2단계다 — 각 단계 안은 조합, 단계 사이는 곱셈

원리. 곱셈 원리를 쓰려면 여자 쪽 가짓수가 남자 쪽 선택과 무관함을 한 마디

확인해야 한다(12주차 규범 ②).

8. 이항정리로 \((x + y)^4\)과 \((a - b)^4\)을 전개하시오.

힌트

계수는 둘 다 파스칼 \(n = 4\)행이다. \((a-b)^4\)은 \(y\) 자리에 \(-b\)를 넣은 것 —

\((-b)^k = (-1)^k b^k\)이므로 부호가 한 칸씩 교대한다.

9. \((2x - 1)^5\)의 전개에서 \(x^4\)의 계수와 상수항을 구하시오.

힌트

예제 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)로 한 칸씩만 이동한다. 최단 경로의 수를 “목록과 위치 선택”의 언어로 구하시오.

힌트

최단 경로 하나는 R 4개와 U 3개를 섞어 적은 길이 7 문자열과 1:1로 대응한다.

문자열은 “U가 놓일 자리”만 정하면 완전히 결정된다 — 7자리 중 3자리를 고르는

일은 어떤 세기인가.

11. 공식 \(\binom{n}{k} = \dfrac{n!}{k!(n-k)!}\)을 순서 지우기 논증으로 유도하시오 (개념 절 재현 — 백지에서).

힌트

세 문장이면 된다: ① 반복 없는 길이 \(k\) 목록의 수(12주차 문제 12) ② 부분집합

하나당 목록이 정확히 몇 개씩 생기는지 ③ 나눗셈. 훈련 1이 \(n = 7, k = 3\)으로

한 예행연습이다.

12. \(\binom{5}{2} = \binom{4}{1} + \binom{4}{2}\)를 (a) 수치로 확인하고, (b) 예제 2.2의 세기 증명을 이 경우(\(5\)명 중 \(2\)명, 기준 인물 ‘갑’)로 다시 서술하시오.

힌트

(b)는 예제 2.2의 완성본을 \(n = 5\), \(k = 2\)로 옮겨 적는 일이다. 기준 인물

‘갑’을 먼저 세우고, “겹치지 않고 전체를 덮는다”는 문장을 빠뜨리지 않는다 —

그 문장이 덧셈의 자격이다.

13. \(\sum_{k=0}^{n} \binom{n}{k} = 2^n\)을 두 가지 방법으로 증명하시오: (a) 이항정리에 대입 (b) 양변이 같은 대상(무엇?)을 세고 있음을 지적.

힌트

(a)는 확인 9에서 했다 — 어떤 수를 대입하면 거듭제곱이 전부 사라지는가.

(b)의 “같은 대상”은 \(n\)원소 집합의 부분집합 전체다. 좌변은 그것을 크기별로,

우변은 원소별 넣음/뺌 목록으로(12주차 문제 13) 센다.

14. 10명 중 대표 3명을 뽑는다. (a) 특정인 A를 반드시 포함하는 경우의 수, (b) A를 포함하지 않는 경우의 수를 구하고, (c) 두 값의 합이 \(\binom{10}{3}\)과 같음을 확인한 뒤 이것이 어느 공식의 사례인지 말하시오.

힌트

(a)는 A가 확정이므로 남은 선택만 센다. (c)에서 “포함/미포함이 전체를 겹침

없이 덮는다”는 문장까지 적으면, 이 문제 전체가 어떤 증명의 수치판인지

보인다 — 예제 2.2를 다시 본다.

도전 ●●●#

새 도구 — 대응으로 세기

두 집합의 원소들이 하나씩 빠짐없이 짝지어지면(1:1 대응) 두 집합의 크기는

같다. 12주차 §1.8에서 부분집합과 넣음/뺌 목록을 짝지어 \(2^n\)을 얻은 것이

이 논법이었다. 대응으로 개수가 같음을 보이는 서술의 완결 조건은 세 가지다:

① 대응 규칙을 제시한다 ② 서로 다른 것은 서로 다른 것에 대응함을 확인한다

③ 상대편 어느 것도 빠지지 않음을 확인한다. (이 논법의 정식 언어 — 전단사 —

는 41주차에서 세운다. 지금은 세 조건의 서술로 충분하다.)

15. \(\binom{n}{k} = \binom{n}{n-k}\)의 세기 증명을 쓰시오. (힌트: \(k\)명을 “뽑는 것”과 \(n-k\)명을 “남기는 것” 사이의 대응)

힌트

크기 \(k\) 선택 하나마다 “남겨진 사람들의 집합”이 하나 정해진다 — 이것이

대응 규칙이다. 위 상자의 조건 ②③을 이 대응에 대해 확인하면 끝난다.

문제 4에서 수치로 만진 것의 일반화이고, 훈련 3이 \(k = n-1\)인 특수 사례였다.

16. \(n \ge 1\)일 때 \(\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0\)을 이항정리로 증명하고, 이 등식을 “홀수 크기 부분집합의 수와 짝수 크기 부분집합의 수”에 대한 문장으로 해석하시오.

힌트

좌변이 이항정리의 우변 꼴이 되는 대입은 \(x = 1, y = -1\)이다. 해석에서는

\((-1)^k\)의 부호에 따라 항을 두 무리로 나눠 음수 항을 반대편으로 넘긴다.

\(n \ge 1\) 조건이 왜 필요한지도 확인해 본다 — \(n = 0\)이면 좌변이 얼마인가.

17. \(\binom{n}{2} = \dfrac{n(n-1)}{2}\)을 두 가지 방법으로 증명하시오: (a) 공식 계산 (b) 악수 논증(12주차 문제 17의 일반화).

힌트

(b)는 예제 2.1의 4단계 서술을 \(n\)명으로 일반화하는 것이다 — 목록

\(n(n-1)\)개, 쌍 하나당 정확히 2개씩. 문자 \(n\)이 들어와도 서술은 한 글자도

달라지지 않는다.

18. 평면 위에 어느 세 점도 한 직선 위에 있지 않은 \(n\)개의 점이 있다. (a) 두 점을 잇는 직선의 개수, (b) 세 점으로 만드는 삼각형의 개수를 조합으로 표현하고, \(n = 5\)일 때 값을 구하시오.

힌트

“두 점이 직선 하나를 결정한다”가 대응 규칙이다 — 크기 2 부분집합과 직선이

1:1로 짝지어지려면 어떤 조건이 지켜져야 하는가. 문제가 준 일직선 조건이

무엇을 막고 있는지 생각하며 쓴다.

19. 등식 \(k\binom{n}{k} = n\binom{n-1}{k-1}\)의 세기 증명을 쓰시오. (힌트: “\(n\)명 중 위원 \(k\)명을 뽑고 그중 위원장 1명을 정하는” 가짓수를 두 가지 순서로 세기: ① 위원회 먼저 ② 위원장 먼저)

힌트

세는 대상은 (위원회, 위원장) 쌍 전체다 — 3단계 틀 ①에 이 선언부터 적는다.

방법 ①은 좌변, 방법 ②는 우변이 되도록 각 단계의 가짓수를 곱셈 원리로

세면, 결론은 “같은 대상을 센 두 결과”라는 표준 문구로 닫힌다.

20. (서술) 세기 증명(combinatorial proof)이 대수 계산 증명보다 나은 점과 못한 점을 각각 한 가지씩 쓰시오. 그리고 “같은 것을 두 번 센다”가 등식의 증명이 되는 근거를 한 문장으로 쓰시오.

힌트

문제 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\)행만 새로 만든다.

풀이.

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단계 틀 — 대상 선언, 장치의 정당성, 결론 — 이 그대로 채점 기준이 된다.