# 13주차 — 조합과 이항정리 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 같은 것을 두 가지 방법으로 세면, 등식이 증명된다. **이 주의 위치**: 50주 과정의 13주차. 12주차의 목록 세기에서 순서를 지워 부분집합을 세고, 세기 논증이라는 새 증명 양식을 얻는다. 고2~3 확률과 통계의 조합$\cdot$이항정리를 증명의 언어로 재건축한다. **원서 대응**: BoP(Book of Proof) 3.4–3.6 (Counting Subsets, Pascal's Triangle, Binomial Theorem) — 병행자 참고용이고, 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. $\binom{n}{k}$의 **정의**(크기 $k$ 부분집합의 개수)를 백지에 쓰고, 공식 $\frac{n!}{k!(n-k)!}$을 순서 지우기 논증으로 유도할 수 있다. 1. 파스칼 공식 $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$를 세기 논증으로 증명할 수 있다. 1. 이항정리를 "괄호마다 하나씩 고르는 선택의 세기"로 설명하고, 전개$\cdot$계수 추출$\cdot$수 대입에 쓸 수 있다. 1. 세기 논증(combinatorial proof)의 3단계 틀을 새 등식에 적용할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (12주차 복습) 1. 반복 없는 길이 $k$ 목록의 개수 공식을 쓰시오. 1. $0! = 1$인 이유를 한 문장으로 쓰시오. 1. 12주차 문제 17(악수 문제): $5 \times 4 = 20$이 틀린 이유를 말로 재현하시오. ### 자주 나오는 세 가지 답 — 3번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 공식 회귀.** "악수는 조합이니까 $\binom{5}{2} = 10$이 맞다"라고 적는다. 값은 옳다. 문제가 물은 것은 값이 아니라 $5 \times 4$가 **무엇을 세는지**의 지목이다 — 그 지목이 빠지면 다음에 목록과 집합이 갈리는 자리에서 같은 실수가 반복된다. 이번 주 §1.1이 정확히 그 지목에서 출발한다. - **유형 2 — 방향만 맞는 서술.** "순서가 상관없는데 순서 있게 세었다"라고 적는다. 방향은 옳다. 빠진 것은 정량화다 — 얼마나 부풀었는가. 나눗셈이 정당한 근거는 "각 쌍이 **정확히 2번씩** 세어졌다"는 한 문장이고, 이번 주의 공식 유도 전체가 이 문장의 일반형($k!$번씩) 위에 선다. - **유형 3 — 재현 실패.** 12주차 해설을 읽을 때는 알았는데 백지에서 나오지 않았다. 읽고 이해한 것과 재구성하는 것 사이의 간격이다. 이번 주 §1.1이 같은 막힘을 처음부터 다시 밟는다. ## 개념 — 조합과 세기 논증 ### 1 목록의 도구로 부분집합을 세면 어디서 막히는가 이번 주의 소재는 "순서 없이 고르기"다. 12주차의 도구만으로 다음 문제를 밀어붙여 보자: 학생 5명 중 청소 당번 2명(직책 없음)을 뽑는 가짓수. :::{admonition} 시도 — 곱셈 원리로 밀어붙이기 :class: quotebox "당번 뽑기는 (첫째 당번, 둘째 당번)의 반복 없는 길이 2 목록이다. 1번째는 5가지, 2번째는 4가지이고 각 단계의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 $5 \times 4 = 20$가지다." ::: 12주차 서술 규범 ①②③을 전부 갖춘 답안이다. 그런데 나열로 검산하면 — 5명을 1~5로 부르면 당번 조합은 $\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{1,5\}$, $\{2,3\}$, $\{2,4\}$, $\{2,5\}$, $\{3,4\}$, $\{3,5\}$, $\{4,5\}$ — 10가지뿐이다(12주차 문제 17의 나열 그대로다). 계산은 한 줄도 틀리지 않았는데 답이 두 배다. 오류는 계산이 아니라 규범 ①의 **선언**에 있다. 당번 두 명에는 직책이 없으므로 뽑기의 결과는 (첫째, 둘째)라는 목록이 아니라 $\{1, 2\}$라는 **집합**이다. 목록 세기는 옳게 실행되었으나, 세어진 것이 원하는 대상이 아니었다. :::{container} quotebox **확인 1.** 목록 20개 중에서 같은 당번 집합 $\{1, 2\}$에 대응하는 목록을 전부 나열해 보자. 몇 개인가? ::: :::{admonition} 답 :class: quotebox dropdown $(1, 2)$와 $(2, 1)$ — 2개다. 크기 2 집합 하나를 일렬로 나열하는 방법의 수 $2! = 2$(12주차 정의 12.2)와 일치한다. 즉 20은 집합 10개를 하나도 빠짐없이 **정확히 2개씩** 부풀려 센 값이다: $20 = 10 \times 2$. 부풀린 배수를 알면 되돌릴 수 있다 — $20 \div 2 = 10$. ::: 막힌 자리가 정확해졌다. 12주차의 도구는 목록을 세고, 이번 주의 대상은 집합이다. 필요한 것은 목록의 셈에서 **순서를 지우는** 장치다. ### 2 순서 지우기 — 표를 채워 규칙을 만들어 보기 방금의 되돌리기가 우연인지, 다른 크기에서도 작동하는지 표로 확인해 보자. 각 행에서 "목록 수 ÷ (부분집합 하나당 목록 수)"를 계산한다. | **$n$개 중 크기 $k$** | **반복 없는 길이 $k$ 목록 수** | **부분집합 하나당 목록 수** | **부분집합 수** | |---|---|---|---| | $n=5$, $k=2$ | $5 \times 4 = 20$ | $2! = 2$ | $20 / 2 = 10$ | | $n=5$, $k=3$ | $5 \times 4 \times 3 = 60$ | $3! = \underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ | | $n=4$, $k=4$ | $4! = 24$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(4)를 채우고, 셋째 행의 결과가 옳은 값인지 나열 없이 판단해 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $6$ (2) $60 / 6 = 10$ (3) $4! = 24$ (4) $24 / 24 = 1$. 셋째 행은 4명 전원을 뽑는 경우다 — 가능한 뽑기는 전체 자신 하나뿐이므로 1이 맞고, 나눗셈이 그 값을 정확히 돌려준다. 세 행이 전부 같은 규칙 — 반복 없는 길이 $k$ 목록의 수를 **$k!$로 나누면** 크기 $k$ 부분집합의 수다. ::: 일반화하자. $n$개짜리 집합에서 — - 반복 없는 길이 $k$ 목록은 $\dfrac{n!}{(n-k)!}$개다 (12주차 문제 12). - 크기 $k$ 부분집합 하나마다, 그것을 일렬로 나열한 목록이 정확히 $k!$개씩 생긴다 — 원소 $k$개를 전부 세우는 가짓수다 (12주차 정의 12.2). - 목록은 순서를 기억하고 부분집합은 기억하지 않으므로, 목록 전체는 각 부분집합을 정확히 $k!$번씩 센 것이다. 12주차 문제 17에서 2로 나눈 "순서 지우기 나눗셈" — **각 대상이 정확히 $m$번씩 세어졌으면 $m$으로 나눈다** — 의 $m = k!$인 일반형이다. 따라서 부분집합의 수는 목록 수를 $k!$로 나눈 값이다. 이 개수에 정식 이름과 기호를 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 나눗셈을 문장으로 굳혔을 뿐이다. ### 정의 13.1 — 조합 (combination / binomial coefficient) [백지 암기 대상] :::{container} quotebox $n$개짜리 집합에서 크기 $k$인 부분집합의 개수를 $\dbinom{n}{k}$로 쓴다. $$ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \qquad (0 \le k \le n) $$ ::: 공식에 범위가 붙어 있는 이유는 $k > n$이면 $(n-k)!$ 자체가 정의되지 않기 때문이다. 그 경우의 값은 공식이 아니라 정의가 직접 준다($= 0$, §1.4). 기호 $\binom{n}{k}$는 "엔 씨 케이"(n choose k) 또는 "엔 개 중 케이 개를 고르는 가짓수"로 읽는다. 읽는 법까지가 정의다. 정의의 본체는 첫 문장 — **부분집합의 개수**라는 뜻 — 이고, 공식은 §1.2의 논증이 증명한 사실이다: $$ \binom{n}{k} = \frac{n!/(n-k)!}{k!} = \frac{n!}{k!\,(n-k)!} $$ :::{container} quotebox **확인 3.** 이 유도가 쓴 재료 두 가지 — 분자 $\frac{n!}{(n-k)!}$과 나누는 수 $k!$ — 는 각각 어디서 온 사실인가? ::: :::{admonition} 답 :class: quotebox dropdown 분자는 12주차 문제 12(반복 없는 길이 $k$ 목록의 수 — 곱셈 원리로 유도)이고, $k!$은 12주차 정의 12.2($k$개를 전부 세우는 가짓수)다. 즉 이번 주의 공식은 무에서 나온 것이 아니라 지난주에 증명해 둔 부품 두 개의 재사용(근거 ④)에 순서 지우기 나눗셈 하나를 얹은 것이다. ::: ### 3 정의 해부 — 조각마다 하는 일 정의의 첫 문장은 네 조각으로 되어 있고, 조각마다 세기에서 맡는 역할이 다르다. 이 정의는 증명 중에서도 세기 논증에 쓰이므로 셋째 열을 세기 중심으로 적는다. | **조각** | **하는 일** | **세기(증명)에서의 역할** | |---|---|---| | "$n$개짜리 집합에서" | 무대의 선언 | 재료 전체의 크기를 고정한다 — 공식의 $n$이 여기서 온다 | | "크기 $k$인" | 자격 제한 | 세는 대상을 한 층으로 고정한다 — 이 조각이 빠지면 층별 정보가 사라진다 | | "부분집합의" | 대상의 정체 | 순서를 묻지 않는다 — 목록으로 바꾸면 $k!$배로 부푼다 | | "개수를 $\binom{n}{k}$로 쓴다" | 기호의 정체 선언 | $\binom{n}{k}$는 명제가 아니라 **수**다 — 등호로 잇고 계산한다 | **조각 교체$\cdot$삭제 실험.** 셋째 조각의 "부분집합"을 "**반복 없는 길이 $k$ 목록**"으로 바꿔 보자. 그러면 $\binom{5}{2}$의 값이 $5 \times 4 = 20$이 되어 §1.1의 붕괴 — 악수 10쌍이 20으로 세어지는 사태 — 가 재연된다. 이번에는 둘째 조각 "크기 $k$인"을 지워 보자. 그러면 세는 대상이 부분집합 전체가 되어 값은 $2^n$(12주차 §1.8)이다 — 층별로 세는 정보가 통째로 사라진다. 조각 하나하나가 이런 붕괴를 막는 조건이다. :::{container} quotebox **확인 4.** 2주차 §1.4에서 $a \mid b$는 수가 아니라 명제라고 못 박았다. $\binom{5}{2}$는 어느 쪽인가. "$\binom{5}{2} = 10$"과 "$5 \mid 10$"에서 등호와 막대가 각각 하는 일을 비교해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $\binom{5}{2}$는 **수**다 — 어떤 유한집합의 원소 개수이므로 값 10을 갖고, "$\binom{5}{2} = 10$"은 수와 수를 잇는 등식이다. 반면 $5 \mid 10$은 명제다 — 값이 아니라 참$\cdot$거짓을 갖는다($10 = 5 \times 2$이므로 참). 새 기호를 만날 때마다 정체(수인가 문장인가)부터 확인하는 습관(2주차)이 여기서 다시 쓰인다. ::: ### 4 끝값들 — 애매하면 정의로 $k$가 0이거나 $n$과 같거나 $n$보다 클 때 $\binom{n}{k}$가 얼마인지는 공식을 외우기 전에 정의로 판정할 수 있어야 한다. :::{container} quotebox **확인 5.** 공식 계산 없이, 정의(부분집합 세기)만으로 다음 값을 정해 보자. (가) $\binom{n}{0}$ (나) $\binom{n}{n}$ (다) $\binom{n}{1}$ (라) $\binom{3}{5}$ ::: :::{admonition} 답 :class: quotebox dropdown (가) $1$ — 크기 0인 부분집합은 $\emptyset$ 하나뿐이다(공집합은 어느 집합의 부분집합이기도 하다 — 4주차 §1.4 끝의 관찰이고, 원소가 하나도 없는 집합은 $\emptyset$뿐이다). (나) $1$ — 크기 $n$인 부분집합은 전체집합 자신 하나뿐이다. (다) $n$ — 크기 1 부분집합 $\{x\}$는 원소 $x$마다 정확히 하나씩 생긴다. (라) $0$ — 3개짜리 집합에는 크기 5인 부분집합이 없다. "개수가 0"도 정의가 주는 정상적인 답이다. ::: 공식과 대조하면 빚 하나가 회수된다. $k = 0$을 공식에 넣으면 $\frac{n!}{0!\,n!} = 1$ — $0! = 1$(12주차 정의 12.2) 덕분에 공식이 끝값에서도 정의와 일치한다. $0! = 0$으로 정했다면 여기서 0으로 나누기가 일어났을 것이다. 한편 $k > n$이면 공식의 $(n-k)!$ 자체가 정의되지 않으므로, 공식은 $0 \le k \le n$에서만 쓴다. $k > n$인 경우의 값은 약속이 아니라 정의가 직접 준다 — 그런 부분집합이 없으므로 $\binom{n}{k} = 0$이다(확인 5의 (라)). ### 5 파스칼 공식 — 표에서 발견하기 $\binom{n}{k}$의 작은 값들을 층층이 쌓아 보자. $n$행에 $\binom{n}{0}$부터 $\binom{n}{n}$까지 적는다. ```text n=0: 1 n=1: 1 1 n=2: 1 2 1 n=3: 1 3 3 1 n=4: 1 ? 6 ? 1 ``` :::{container} quotebox **확인 6.** $n = 4$행의 두 물음표를 채워 행을 완성해 보자. 그리고 완성된 다섯 행에서, 각 안쪽 수와 그 바로 위 두 수 사이의 관계를 찾아 보자. ::: :::{admonition} 답 :class: quotebox dropdown $\binom{4}{1} = 4$(확인 5의 (다)), $\binom{4}{3} = \frac{4!}{3!\,1!} = 4$ — 행은 $1, 4, 6, 4, 1$이다. 관계: 안쪽의 모든 수가 바로 위 두 수의 합이다. $2 = 1 + 1$, $3 = 1 + 2$, $4 = 1 + 3$, $6 = 3 + 3$ — 확인한 모든 자리에서 성립한다. 이 관찰을 식으로 적으면 다음 공식이다. ::: ### 파스칼 공식과 삼각형 [백지 암기 대상] :::{container} quotebox $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \qquad (1 \le k \le n-1) $$ ::: 이 공식을 계단처럼 쌓으면 **파스칼 삼각형**이다: ```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 = 4$행의 $1, 4, 6, 4, 1$은 4주차 문제 14에서 $\{1, 2, 3, 4\}$의 부분집합을 크기별로 셌을 때 나온 바로 그 수열이다 — 그때의 손 세기가 지금의 $\binom{4}{0}, \dots, \binom{4}{4}$였다. 주의할 것이 하나 있다. 위 공식은 아직 **관찰**이다 — $n = 2, 3, 4$의 몇 자리에서 확인했을 뿐이고, 예시 확인은 증명이 아니다(1주차 문제 18). 모든 $n, k$에 대한 증명이 필요하고, 그 증명이 이번 주의 새 양식 — 다음 절 — 의 대표작이 된다(예제 2.2). ### 6 세기 논증 — 새 증명 양식 :::{admonition} 세기 논증의 원리 :class: quotebox 하나의 유한집합을 두 가지 방법으로 세면, 두 결과는 같아야 한다 — 유한집합의 크기는 세는 방법과 무관하게 하나로 정해진 수이기 때문이다. 따라서 "좌변은 집합 $X$를 이렇게 센 것이고, 우변은 같은 $X$를 저렇게 센 것"임을 보이면 등식 좌변 $=$ 우변이 증명된다. ::: 멀리 있는 이야기가 아니다 — §1.2의 공식 유도가 정확히 이 꼴이었다. :::{container} quotebox **확인 7.** §1.2의 유도를 이 양식으로 다시 읽어 보자. 두 방법이 함께 센 "하나의 집합"은 무엇이고, 두 방법은 각각 무엇이었는가? ::: :::{admonition} 답 :class: quotebox dropdown $n$개에서 만든 반복 없는 길이 $k$ 목록 **전체의 집합**이다. 방법 ①: 곱셈 원리로 자리별로 세면 $\frac{n!}{(n-k)!}$개. 방법 ②: 목록을 "어느 부분집합을 나열한 것인가"로 분류하면, 부분집합 $\binom{n}{k}$개마다 정확히 $k!$개씩 — 합해서 $\binom{n}{k} \cdot k!$개. 같은 집합을 센 두 결과이므로 $\binom{n}{k} \, k! = \frac{n!}{(n-k)!}$이고, 양변을 $k!$로 나누면 공식이다. 첫 세기 논증은 이미 끝나 있었다. ::: 같은 등식이라도 대수 계산(팩토리얼 통분)은 기계적으로 진행되는 대신 식이 **왜** 성립하는지 말해 주지 않고, 세기 논증은 양변을 같은 대상의 두 관점으로 드러내므로 성립 이유가 증명 안에 보인다. 두 길의 득실은 문제 13, 17에서 직접 겪은 뒤 문제 20에서 언어화한다. ### 7 이항정리 — 전개는 선택의 세기 조합이 대수의 한복판에 나타나는 자리를 보자. $(x+y)^3$을 분배법칙으로 정직하게 전개하면 — $$ (x+y)^3 = (x+y)(x+y)(x+y) $$ 곱을 펼친 각 항은 **세 괄호에서 $x$ 또는 $y$를 하나씩 골라 곱한 것**이다: $xxx, xxy, xyx, xyy, yxx, yxy, yyx, yyy$. 항 하나가 곧 길이 3의 $x/y$ 목록이고, 반복 허용이므로 전부 $2^3 = 8$개다(12주차 §1.6). :::{container} quotebox **확인 8.** 8개의 목록 중 곱이 $x^2 y$가 되는 것을 전부 나열해 보자. 몇 개이고, 각 목록은 무엇 하나로 완전히 결정되는가? ::: :::{admonition} 답 :class: quotebox dropdown $xxy, xyx, yxx$ — 3개다. 각 목록은 "$y$를 고른 괄호의 위치"(각각 3번째, 2번째, 1번째)로 완전히 결정된다. 위치의 선택은 괄호 3개 중 1개를 고르는 크기 1 부분집합의 선택이므로 가짓수는 $\binom{3}{1} = 3$이다. 그래서 동류항을 정리한 $x^2 y$의 계수가 3이다: $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$. ::: 일반화하면 — $(x+y)^n$의 전개에서 $x^{n-k} y^k$가 되는 목록은 "$y$를 고른 괄호 $k$개의 위치"로 결정되고, 위치의 집합은 괄호 $n$개 중 크기 $k$ 부분집합이므로 그런 목록은 $\binom{n}{k}$개다. **전개가 곧 세기다.** 결과를 한 식으로 적기 위해 합의 기호 하나를 도입한다. :::{admonition} 표기 — $\sum$ (시그마) :class: quotebox 합 $a_0 + a_1 + \cdots + a_n$을 $\sum_{k=0}^{n} a_k$로 줄여 쓴다. "케이가 0부터 엔까지, $a_k$의 합"으로 읽는다. $k$에 $0, 1, \dots, n$을 차례로 넣어 전부 더하라는 지시일 뿐 새 연산이 아니고, 증명에서 펼쳐 적어도 같은 점수다. 이 기호는 이번 주가 첫 등장이다. ::: ### 이항정리 (Binomial Theorem) [백지 암기 대상] :::{container} quotebox $$ (x+y)^n = \sum_{k=0}^{n} \binom{n}{k}\, x^{n-k} y^k $$ ::: 증명은 방금의 논증이 전부다: 전개의 각 항은 $n$개의 괄호에서 하나씩 고른 선택의 기록이고, $x^{n-k}y^k$ 항의 개수는 $y$의 위치 집합의 수 $\binom{n}{k}$다. 계수가 파스칼 삼각형의 $n$행과 일치하므로, 삼각형은 전개 계수의 표이기도 하다. $x, y$는 문자이므로 아무 수나 대입할 수 있다(근거 ③). 대입 한 번마다 항등식이 하나씩 나온다. :::{container} quotebox **확인 9.** 이항정리에 $x = y = 1$을 대입해 보자. 좌변과 우변은 각각 무엇이 되고, 우변의 합이 세고 있는 것은 무엇인가? ::: :::{admonition} 답 :class: quotebox dropdown 좌변은 $(1+1)^n = 2^n$, 우변은 $\sum_{k=0}^{n} \binom{n}{k}$ — 모든 거듭제곱이 1이 되어 계수만 남는다. 우변은 크기 0, 1, …, $n$ 부분집합 수의 총합, 곧 **부분집합 전체의 수**다. 4주차 문제 14에서 $1+4+6+4+1 = 16 = 2^4$로 확인한 관찰의 일반형이고, 정확한 두-방법 서술은 문제 13에서 완성한다. ::: $x = 1, y = -1$을 대입하면 교대합 $\sum_{k=0}^n (-1)^k \binom{n}{k}$이 0이 된다($n \ge 1$) — 유도와 그 해석(짝수 크기 부분집합과 홀수 크기 부분집합의 수가 같다)은 문제 16의 몫이다. ### 8 근거 목록 갱신 — 칸은 그대로 네 개 칸의 개수는 이번 주에도 늘지 않는다. ① 칸에 정의가 하나 추가되고, ④ 칸에 이번 주에 증명한 원리$\cdot$공식들이 등록될 뿐이다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | **정의 13.1(조합)** 추가 | "크기 $k$ 부분집합의 개수" $\leftrightarrow$ $\binom{n}{k}$ 사이를 번역한다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 이번 주에는 등장이 적다 | | ③ 등식의 성질 | 대입 / 전개 / 약분 | 이항정리에 $x = y = 1$을 대입한다 | | ④ 이미 증명한 명제 | **순서 지우기 나눗셈**(각 대상이 정확히 $m$번씩 세어졌으면 $m$으로 나눈다 — §1.2에서 $m = k!$인 꼴을 논증했고, 균등 분할의 일반형은 지금은 인정하고 쓴다), **세기 논증의 원리**(§1.6), 조합 공식(§1.2), **파스칼 공식**(증명은 예제 2.2), **이항정리**(§1.7), 곱셈 원리$\cdot$목록 공식(12주차) | "같은 대상을 두 방법으로 세었으므로 두 결과는 같다"가 이번 주의 표준 문구다 | 인정하고 쓰는 사실이 하나 있다: **서로소인 두(또는 그 이상의) 무리로 나뉘면 개수를 더할 수 있다**(덧셈 원리 — 14주차에서 공식화하고 증명한다). 서로소는 5주차 정의 5.2의 낱말 그대로 — 공통 원소가 없다는 뜻이다. 무리가 셋 이상인 일반형은 두 무리의 논증을 반복해서 얻는데, 그 반복의 정당화가 31주차 귀납법까지 미뤄지므로 두 무리짜리와는 **별개의 인정 사항**이다. 예제 2.2와 문제 12, 13, 14가 이 사실을 명시하고 쓴다(문제 13은 무리가 셋 이상인 경우다). :::{container} quotebox **확인 10.** 어떤 답안에 다음 세 근거 문장이 나왔다. 각각 통과하는가? (가) "각 부분집합이 목록에서 정확히 $3! = 6$번씩 세어졌으므로 6으로 나눈다" (나) 유도 없이 "공식에 의해 $\binom{7}{3} = 35$" (다) "두 경우는 겹치지 않고 전체를 덮으므로 개수를 더한다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 통과 — 근거 ④ 순서 지우기 나눗셈이고, "정확히 몇 번"의 명시가 자격 조건이다. 그 명시가 없는 "적당히 나눈다"는 통과하지 못한다. (나) 통과 — 공식은 §1.2에서 유도를 마쳐 근거 ④에 등록되었다. 12주차 확인 12에서 "순열 공식"이 불통과였던 것과 갈리는 지점이 이 등록 절차다 — 등록 전의 공식 이름은 근거가 아니고, 등록 후에는 근거다. (다) 통과 — 인정하고 쓰는 사실(덧셈 원리)이다. 다만 인정 사실도 이렇게 문장으로 명시했을 때만 근거가 된다 — 말없이 더하면 근거 없는 계산이다. ::: 정의는 외운다 — [백지 암기 대상] 표시가 그 대상이다. 문장을 통째로만 외우지 말고 §1.3의 조각별 이유와 함께 외운다. 조각을 잊어도 이유에서 재구성할 수 있다.