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

내용

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

예제 — 세기 논증을 함께 만들기#

완성된 풀이를 먼저 보이지 않는다. 서술 규범 ①②③을 따라 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 회장·부회장 뽑기#

문제. 학생 5명 중 회장 1명, 부회장 1명을 뽑는 가짓수는? (겸직 불가)

준비 운동 4번이 바로 이 문제였다. 이번에는 규범대로 만든다.

설계 — 쓰기 전에 정하는 두 가지. 증명의 번역표(가정 \(\to\) 출발점, 목표 \(\to\) 도착점)가 세기에서는 다음 꼴이 된다: 세는 대상의 구조가 출발점, 그 개수가 도착점이다.

	말	번역
세는 대상 (출발점)	뽑기의 결과 하나	(회장, 부회장)의 길이 \(\underline{\quad}\) 목록, 반복 \(\underline{\quad}\)
목표 (도착점)	가능한 결과 전부의 수	그런 목록의 개수

확인 13. 표의 두 빈칸을 채워 보자. 그리고 결과가 집합 {갑, 을}이 아니라

목록 (갑, 을)인 이유를 문제의 조건에서 찾아 한 문장으로 적어 보자.

답

길이 2, 반복 금지. 회장 자리와 부회장 자리가 구별되므로 — (갑, 을)과

(을, 갑)은 다른 인사 결과이므로 — 순서 있는 목록이고, 겸직 불가 조건이 같은

사람의 재등장을 막으므로 반복 금지다. 구조 선언(규범 ①)이 끝났다.

규범 ② — 단계별 개수와 무관 확인.

확인 14. 1번째 항목(회장)의 선택지는 5가지다. 2번째 항목(부회장)의

선택지는 몇 가지이고, 그 개수는 1번째 선택과 무관한가?

답

4가지 — 회장으로 뽑힌 1명이 빠진다. 누가 회장이 되든 빠지는 것은 정확히

1명이므로, 후보의 내용은 회장에 따라 달라져도 개수는 4로 일정하다

(§1.4 확인 6). 곱셈 원리의 조건이 충족된다.

규범 ③ — 원리 인용과 계산.

확인 15. 마지막 문장을 완성해 보자: “곱셈 원리에 의해

\(\underline{\quad} \times \underline{\quad} = \underline{\quad}\)가지이다. \(\blacksquare\)”

답

\(5 \times 4 = 20\)가지. 준비 운동 4번의 답 20이 세 문장의 논증을 얻었다.

완성본. 방금 만든 세 줄을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄	왜 이 줄을 쓰는가?
뽑기의 결과는 (회장, 부회장)의 길이 2 목록이다 — 자리가 구별되므로 순서가 있고, 겸직 불가이므로 반복 금지다.	규범 ① 구조 선언. 세는 대상의 정체(정의 12.1)를 문제의 조건으로 확정한다.
회장은 5가지, 부회장은 회장을 제외한 4가지 — 누가 회장이든 개수는 4로 일정하다.	규범 ② 단계별 개수 + 무관 확인. 곱셈 원리의 핵심 조건을 검사하는 줄이다.
곱셈 원리에 의해 \(5 \times 4 = 20\)가지이다. \(\blacksquare\)	규범 ③ 원리 인용(근거 ④)과 계산.

이 세 줄이 옳은지 실험할 수 있다. 학생 수를 3명으로 줄이면 전부 나열이 가능해진다 — 논증과 나열이 같은 답을 주는지 대조해 보자.

확인 16. 학생이 {갑, 을, 병} 3명일 때 (회장, 부회장) 목록을 전부 나열하고,

개수가 같은 논증의 답 \(3 \times 2\)와 일치하는지 확인해 보자.

답

(갑,을), (갑,병), (을,갑), (을,병), (병,갑), (병,을) — 6개. \(3 \times 2 = 6\) ✓.

나열은 작은 사례의 검산 도구로 남고, 논증은 나열이 불가능한 크기까지

답을 보장한다 — 1주차에서 예시 확인(검산)과 문자 증명(보장)이 나눠 맡던

역할 분담이 세기에서도 그대로다.

예제 2.2 — 반복 허용#

문제. 참/거짓 5문항 답안지는 몇 가지인가?

이번에는 설계(규범 ①)만 함께 하고, 서술은 완성본으로 본다.

확인 17. 번역표를 채워 보자. 세는 대상: T/F 두 기호로 된 길이

\(\underline{\quad}\) 목록, 반복 \(\underline{\quad}\). — 반복의 허용 여부는

문제의 어떤 사정에서 읽어 내는가?

답

길이 5, 반복 허용. 1번 문항에 T라고 답했어도 2번 문항에 다시 T라고

답할 수 있다 — 앞 문항의 답이 뒤 문항의 선택지를 줄이지 않는다. 예제

2.1(겸직 불가 = 반복 금지)과 정반대의 사정이고, 이 판단이 \(n^k\)와

\(n(n-1)\cdots\) 중 어느 공식이 작동하는지를 가른다.

풀이. 답안지는 T/F 두 기호로 된 길이 5 목록이다(반복 허용). 매 문항 2가지씩이고 각 단계의 선택지 개수는 앞 답과 무관하다. 곱셈 원리에 의해 \(2^5 = 32\)가지이다. \(\blacksquare\)

4주차 문제 9와 연결된다 — 크기 5인 집합의 부분집합 개수도 \(2^5\)였다. 우연이 아니다: 답안지 하나를 “T라고 답한 문항들의 집합”에 대응시키면 답안지와 부분집합이 1:1이다 — §1.8의 넣음/뺌 대응에서 기호의 이름만 바꾼 것이다.

예제 2.3 — 전부 세우기와 일부 세우기#

문제. 책 7권 중 (a) 7권 전부를 책장에 일렬로 꽂는 가짓수, (b) 3권만 골라 일렬로 꽂는 가짓수는?

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

확인 18. (a)와 (b) 각각에 대해 — 세는 대상은 무슨 목록이고, §1.6 표의

어느 행이 작동하며, (b)의 3번째 항목의 선택지는 몇 가지인가?

답

(a) 7권 전부의 반복 없는 길이 7 목록 — 반복 금지에서 \(k = n\)인 경우, 곧

팩토리얼이다. (b) 7권에서 고른 반복 없는 길이 3 목록 — 반복 금지 행이고,

3번째 항목은 이미 꽂힌 2권이 빠져 \(7 - 2 = 5\)가지다.

풀이. (a) 꽂는 결과는 7권 전부의 반복 없는 길이 7 목록이다. 정의 12.2에 의해 \(7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 5040\)가지이다. (b) 꽂는 결과는 7권에서 고른 반복 없는 길이 3 목록이다. 자리별 선택지는 \(7, 6, 5\)가지로 앞 선택과 개수가 무관하므로, 곱셈 원리에 의해 \(7 \times 6 \times 5 = 210\)가지이다. \(\blacksquare\)

(b)를 팩토리얼로 쓰면

\[ 7 \times 6 \times 5 = \frac{7 \times 6 \times 5 \times 4!}{4!} = \frac{7!}{4!} \]

이다. 일반화하면 — \(n\)개에서 고른 반복 없는 길이 \(k\) 목록의 수는 \(\dfrac{n!}{(n-k)!}\)이다. 이 유도를 문제 12에서 일반 문자로 완성한다.

이번 풀이는 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 세기 답안은 처음부터 끝까지 이런 산문 서너 문장이다.

관찰 — 세 풀이의 같은 뼈대#

예제 2.1, 2.2, 2.3은 소재만 다를 뿐 뼈대가 같다. 대응표의 빈칸을 채워 보자.

확인 19. 빈칸 (1)~(4)를 채워 보자.

① 구조 선언 — 2.1: 길이 2, 반복 금지 / 2.2: \(\underline{\quad(1)\quad}\) / 2.3(b): 길이 3, 반복 금지

② 단계별 개수 — 2.1: 5, 4 / 2.2: \(\underline{\quad(2)\quad}\) / 2.3(b): \(\underline{\quad(3)\quad}\)

③ 원리 인용\(\cdot\)계산 — 2.1: \(5 \times 4 = 20\) / 2.2: \(2^5 = 32\) / 2.3(b): \(\underline{\quad(4)\quad}\)

답

(1) 길이 5, 반복 허용 (2) 매 단계 2가지 (3) 7, 6, 5 (4) \(7 \times 6 \times 5 = 210\).

세 풀이 모두 정확히 이 세 걸음이다 — §1.9에서 규범으로 선언한 것이 실제로

모든 풀이의 뼈대였음을 확인했다.

방금 확인한 뼈대가 곧 이번 주의 틀이다.

백지 암기 대상

세기 서술의 3단계 틀

① 세는 대상의 구조를 선언한다(무엇의, 길이 몇의 목록인가 — 반복 허용

여부까지) \(\to\) ② 단계별 선택지의 개수를 세고, 개수가 앞 단계와 무관함을

확인한다 \(\to\) ③ 곱셈 원리를 인용해 계산한다

빈칸 사다리 — 지지대를 하나씩 빼며#

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 공식과 조건의 빈칸#

(1) 길이 \(k\), 기호 \(n\)종, 반복 허용 목록의 수: \(\underline{\quad}\) (2) \(n\)개 전부의 반복 없는 나열의 수: \(\underline{\quad}\) (3) \(0! = \underline{\quad}\) (이유: 빈 목록이 \(\underline{\quad}\)개 있으므로) (4) \(\dfrac{9!}{7!} = \underline{\quad}\) (계산) (5) 곱셈 원리의 핵심 조건: 각 단계의 선택지 \(\underline{\qquad}\)가 앞 단계의 결과와 무관해야 한다.

훈련 2 ●●○ — 서술과 근거를 함께#

이번에는 서술 규범의 문장과 근거 문구도 빈칸이다.

문제. 숫자 0~9로 만든 세 자리 비밀번호 중 같은 숫자를 두 번 쓰지 않는 것은 몇 가지인가?

서술. 비밀번호는 열 개의 숫자 기호로 된 길이 \(\underline{\quad(1)\quad}\) 목록이고, 같은 숫자 금지 조건에 의해 반복 \(\underline{\quad(2)\quad}\)다. 자리별 선택지는 1번째 \(10\)가지, 2번째 \(\underline{\quad(3)\quad}\)가지, 3번째 \(\underline{\quad(4)\quad}\)가지이고, 각 단계의 선택지 \(\underline{\quad(5)\quad}\)는 앞 선택과 무관하다. \(\underline{\quad(6)\quad}\)에 의해 \(10 \times \underline{\quad(3)\quad} \times \underline{\quad(4)\quad} = \underline{\quad(7)\quad}\)가지이다. \(\blacksquare\)

훈련 3 ●●● — 뼈대만 남기고#

명제. \(|A| = n\)이면 \(A\)의 부분집합은 \(2^n\)개다.

논증의 뼈대. 세기 서술 3단계 틀의 각 칸을 통째로 채운다. (§1.8을 보지 않고 쓴 뒤에 대조한다.)

① 대응 제작(구조 선언): \(\underline{\quad(1)\quad}\)
② 단계별 개수와 무관 확인: \(\underline{\quad(2)\quad}\)
③ 원리 인용과 결론: \(\underline{\quad(3)\quad}\)

(이 훈련이 문제 13의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 모든 답에 “무엇의 목록인지 + 곱셈 원리”를 한 줄이라도 서술한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “답: 20”은 0점이고, “(회장, 부회장)의 길이 2

목록이고 자리별 5, 4가지이므로 곱셈 원리에 의해 20가지”가 만점이다.

서술 규범 ①②③(§1.9)이 채점표다. 난이도와 무관하게, 힌트 상자는 5분 이상

막힌 뒤에만 연다.

기본 ●○○#

1. 다음을 계산하시오. (a) \(6!\) (b) \(\dfrac{8!}{6!}\) (c) \(\dfrac{10!}{8! \, 2!}\)

힌트

나눗셈 꼴은 전부 전개하지 않는다 — \(8! = 8 \times 7 \times 6!\)처럼 겹치는

꼬리를 드러내 약분부터 한다.

2. 자음 4종, 모음 3종에서 (자음, 모음, 자음) 꼴 글자를 만드는 가짓수는? (같은 자음 재사용 허용)

힌트

규범 ① 구조 선언부터 — (자음, 모음, 자음)의 길이 3 목록이다. “재사용

허용”이라는 조건이 반복 허용의 신호이고, 3번째 자리의 선택지 개수를 정한다.

3. 참/거짓 4문항 + 삼지선다 2문항으로 된 시험의 답안지 가짓수는?

힌트

자리마다 선택지 개수가 달라도 곱셈 원리는 그대로 작동한다 — 코드 문제

(§1.9, \(26 \times 10 \times 10\))가 이미 그랬다. 답안지가 길이 몇의 목록인지부터

선언한다.

4. 다음 중 같은 것끼리 짝지으시오: \((1, 2, 2)\), \(\{1, 2, 2\}\), \((2, 1, 2)\), \(\{2, 1\}\), \((1, 2)\) (목록\(\cdot\)집합의 상등 기준을 각각 적용)

힌트

목록은 길이와 위치별 항목까지, 집합은 원소만 본다(§1.3 확인 4에서 두 판정을

연습했다). 다섯 대상을 목록과 집합으로 먼저 분류하면 비교할 짝이 줄어든다.

5. \(A = \{a, b, c\}\)에서 길이 2 목록을 (a) 반복 허용으로 모두 나열하고 개수를 확인하시오. (b) 반복 금지로 모두 나열하고 개수를 확인하시오.

힌트

빠뜨림\(\cdot\)겹침 없이 나열하려면 순서 규칙이 필요하다 — 1번째 항목별로 묶어

\(a\)로 시작하는 것부터 차례로 적는다(§1.4의 격자가 그 규칙이다). 다 센 뒤

공식(\(3^2\), \(3 \times 2\))과 대조한다.

6. 지역번호(3자리, 0으로 시작 안 함) + 국번(4자리) 전화번호의 가짓수를 곱셈 원리로 서술해 구하시오.

힌트

“0으로 시작 안 함”은 첫 자리의 선택지 개수만 줄인다 — 나머지 자리는 10가지

그대로다. 자리별 개수를 각각 명시하고 곱한다.

표준 ●●○#

7. 학생 5명을 일렬로 세우는 가짓수를 구하고, 그중 특정 학생 A가 맨 앞에 서는 경우의 수를 구하시오.

힌트

전부 세우기는 \(n!\)(정의 12.2). 고정 조건은 그 자리의 선택지를 1가지로 만든다 —

맨 앞이 정해지면 남는 것은 몇 명의 전부 세우기인가.

8. 학생 5명 중 A와 B가 서로 이웃하여 서는 경우의 수를 구하시오. (힌트: 둘을 한 묶음으로)

힌트

A와 B를 한 덩어리로 보면 배열할 대상이 [AB묶음]과 나머지 3명 — 4개가 된다.

다 센 뒤, 묶음 내부에서 A와 B의 자리를 바꾸는 경우를 잊지 않는다.

9. 세 자리 자연수는 모두 몇 개인가? 곱셈 원리 서술과 함께 구하고, “첫 자리가 특별한 이유”를 한 문장으로 쓰시오.

10. 숫자 1, 2, 3, 4, 5를 한 번씩 써서 만든 다섯 자리 수 중 짝수는 몇 개인가? (힌트: 어느 자리를 먼저 정할지가 요령)

힌트

제약이 가장 센 자리(일의 자리 — 짝수여야 한다)부터 정한다. 만의 자리부터

정하면 일의 자리의 선택지 개수가 앞 선택에 따라 달라져 곱셈 원리의 조건이

깨진다 — 순서를 바꾸는 것만으로 조건이 살아난다.

11. \(|A| = 3\), \(|B| = 5\)일 때 \(|A \times B|\)와 \(|B \times B \times B|\)를 구하고, 각각 어떤 목록의 개수인지 쓰시오.

12. 반복 없는 길이 \(k\) 목록의 수가 \(\dfrac{n!}{(n-k)!}\)임을 곱셈 원리로 유도하시오. (\(k\)번째 항의 선택지가 몇 가지인지 명시할 것)

힌트

\(k\)번째 항의 선택지는 확인 8에서 셌다 — 이미 쓴 기호 \(k-1\)개가 빠진다.

곱 \(n(n-1)\cdots(n-k+1)\)을 팩토리얼 분수로 바꾸려면

\(\frac{(n-k)!}{(n-k)!}\)을 곱한다(근거 ③ — 1을 곱하는 변형).

13. \(|\mathcal{P}(A)| = 2^{|A|}\)의 증명(개념 절의 목록 대응)을 백지에 재현하시오.

힌트

훈련 3의 뼈대 그대로다. 대응의 두 방향 — 부분집합에서 목록으로, 목록에서

부분집합으로 — 을 각각 한 문장씩 적어야 “빠짐도 겹침도 없다”가 서술된다.

14. 홀수 숫자(1, 3, 5, 7, 9)만으로 이루어진 네 자리 수는 몇 개인가? 그중 각 자리 숫자가 모두 다른 것은 몇 개인가?

힌트

두 물음은 §1.6 표의 두 행(반복 허용 / 반복 금지)의 대비다 — 재료(기호 5종)와

길이(4)는 같고 조건만 다르다.

도전 ●●●#

새 도구 — 전체에서 빼기 (여사건 세기)

“적어도 하나 ~”를 정면으로 세면 경우가 여러 갈래로 갈라진다(1개인 경우,

2개인 경우, …). 방향을 바꾼다: 조건의 부정(“하나도 ~ 아님”)이 한 덩어리로

세어지면, 전체에서 그 개수를 뺀 것이 답이다. “적어도 하나”(\(\exists\))의

부정이 “전부 아님”(\(\forall\neg\))이라는 11주차 부정 규칙이 세기 전략이 되는

지점이다. 빼기의 정당화(전체 = 조건을 만족하는 것 + 만족하지 않는 것,

겹침 없이)는 14주차 덧셈 원리에서 정식화한다 — 지금은 인정하고 쓴다.

15. 길이 5의 이진 문자열(0/1) 중 적어도 하나의 1을 포함하는 것은 몇 개인가? (힌트: “적어도 하나”의 부정은 “하나도 없다” — 11주차 부정 규칙을 세기에 적용: 전체에서 나쁜 경우를 빼기.)

힌트

전체 개수는 예제 2.2에서 셌다. “1이 하나도 없는” 문자열이 몇 개인지 —

나열해 보면 짧다.

16. 알파벳 \(\{a, b, c\}\)로 만든 길이 5의 회문(palindrome: 앞뒤로 읽어도 같은 문자열, 예: abcba)은 몇 개인가? (힌트: 회문은 어느 자리들이 자유로운가?)

힌트

abcba에서 4번째 자리는 2번째와, 5번째 자리는 1번째와 같아야 한다 — 스스로

고를 수 있는 자리가 몇 개인지부터 센다. 자유로운 자리들의 목록과 회문이

1:1로 대응한다.

17. 다음 풀이의 오류를 찾으시오: “5명 중 악수할 2명을 뽑는 가짓수는, 첫 사람 5가지, 둘째 사람 4가지이므로 \(5 \times 4 = 20\)가지다.” (실제로 악수 쌍은 10가지이다. 무엇이 두 번씩 세어졌는가? — 13주차의 예고)

힌트

\(5 \times 4\) 자체는 옳은 세기다 — 문제는 그것이 세는 대상의 정체다. 규범 ①로

돌아가 선언해 보자: \(5 \times 4\)가 세는 것은 목록인가 집합인가. 그리고 악수

쌍은 목록인가 집합인가.

18. \(|A| = 3\), \(|B| = 4\)일 때, \(A\)의 각 원소에 \(B\)의 원소를 하나씩 배정하는 방법(= \(A\)에서 \(B\)로 가는 함수, 40주차 예고)은 몇 가지인가? 어떤 목록과 대응되는지 서술하시오.

19. 문제 18에서 서로 다른 원소에 서로 다른 값을 배정하는 방법(= 단사함수, 41주차 예고)은 몇 가지인가?

힌트

“서로 다른 값” 조건이 §1.6 표의 어느 행으로 번역되는지부터 정한다 — 문제

18과 재료는 같고 조건 하나만 바뀌었다.

20. (서술) 곱셈 원리가 적용되지 않는 상황의 예를 하나 설계하시오: 2단계 선택인데, 1단계의 결과에 따라 2단계의 선택지 개수가 달라지는 상황. 그리고 그런 경우 어떻게 세야 할지(경우 나누기) 한 문장으로 제안하시오.

힌트

곱셈 원리의 핵심 조건(§1.4)을 일부러 부수면 된다 — 1단계에서 무엇을

골랐는지에 따라 2단계의 가짓수 자체가 달라지는 규칙(조건부 제한)을 하나

넣는다. 격자로 그리면 행마다 칸 수가 다른 그림이 나온다.

백지 재현 — 복습 프로토콜#

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 세기 서술의 3단계 틀과 §1.6의 표(반복 허용/금지)만 펴 놓고, 예제 2.1과 §1.8의 \(2^n\) 논증을 처음부터 끝까지 적는다. 정의와 본문은 보지 않는다.

2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다:

목록의 정의(순서 있음, 중복 허용)와 상등 기준, 집합과의 차이를 썼다.
곱셈 원리를 핵심 조건(“선택지의 개수가 앞 단계와 무관”)까지 포함해 진술했다.
\(n^k\) / \(\dfrac{n!}{(n-k)!}\) / \(n!\)이 각각 어떤 세기인지 구분해 썼다.
\(0! = 1\)의 이유를 빈 목록으로 설명했다.
\(|\mathcal{P}(A)| = 2^n\)의 논증(넣음/뺌 목록 대응)을 재현했다.
세기 답안의 서술 규범 ①②③을 적고, 예제 2.1을 그 규범대로 다시 썼다.

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점	처방
구조 선언 문장이 나오지 않는다	§1.9 규범 ①과 예제 2.1 확인 13 — 길이\(\cdot\)반복 여부를 문제의 조건에서 읽는다
곱셈인지 아닌지 판단이 안 된다	§1.4 격자 — 행마다 칸 수가 같은가를 묻는다. 다르면 문제 20의 상황이다
반복 허용/금지 판단이 흔들린다	예제 2.2 확인 17 — 앞 선택이 뒤 선택지를 줄이는지를 조건에서 찾는다
\(n - k + 1\)이 자꾸 \(n - k\)가 된다	§1.6 확인 8 — 빼는 것은 자리 번호가 아니라 이미 쓴 개수 \(k - 1\)이다
\(2^n\) 논증이 재현되지 않는다	§1.8 확인 10 — 구체 사례(\(n = 3\))의 대응부터 다시 만든다

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) \(n^k\) (2) \(n!\) (3) \(1\), \(1\) (4) \(\dfrac{9!}{7!} = \dfrac{9 \times 8 \times 7!}{7!} = 9 \times 8 = 72\) (5) 개수(가짓수)

※ (5)가 이번 주의 급소다 — “선택지”가 아니라 “선택지의 개수”가 무관해야 한다. 내용은 달라져도 된다(확인 6).

빈칸 사다리 — 훈련 2#

(1) \(3\) (2) 금지 (3) \(9\) (4) \(8\) (5) 개수 (6) 곱셈 원리 (7) \(10 \times 9 \times 8 = 720\)

※ (3)(4)에서 단계마다 1씩 줄어드는 것이 반복 금지의 표식이다. 3번째 자리는 이미 쓴 숫자 2개가 빠져 \(10 - 2 = 8\)가지 — 확인 8의 \(k - 1\) 규칙 그대로다.

빈칸 사다리 — 훈련 3#

(1) \(A\)의 원소를 \(x_1, \dots, x_n\)으로 나열하면, 부분집합 \(X \subseteq A\)마다 “각 \(x_i\)를 넣었는가/뺐는가”의 길이 \(n\) 목록이 하나 정해지고, 거꾸로 그런 목록마다 부분집합이 정확히 하나 정해진다 — 부분집합과 넣음/뺌 목록은 1:1이다. (2) 목록의 각 자리는 넣음/뺌의 2가지이고(반복 허용), 각 자리의 선택지 개수는 앞 자리의 선택과 무관하다. (3) 곱셈 원리에 의해 목록은 \(2^n\)개이고, 1:1 대응에 의해 부분집합도 \(2^n\)개다. \(\blacksquare\)

※ ①의 “거꾸로” 문장을 빠뜨리는 경우가 많다 — 그 문장이 없으면 “목록이 부분집합보다 많을(또는 적을) 가능성”이 배제되지 않아 세기가 옮겨지지 않는다.

문제 1#

접근. 팩토리얼은 정의대로 전부 전개하면 수가 빠르게 커진다. 나눗셈 꼴은 분자를 분모의 팩토리얼이 나올 때까지만 전개해 꼬리를 약분하는 것이 표준 요령이다 — \(8! = 8 \times 7 \times 6!\)처럼.

풀이. (a) \(6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\). (b) \(\dfrac{8!}{6!} = \dfrac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56\). (c) \(\dfrac{10!}{8! \, 2!} = \dfrac{10 \times 9 \times 8!}{8! \times 2} = \dfrac{10 \times 9}{2} = \dfrac{90}{2} = 45\).

복기. 꼬리 약분 — \(\frac{n!}{(n-k)!}\) 꼴은 항상 \(n(n-1)\cdots(n-k+1)\)로 줄어든다(문제 12의 공식을 거꾸로 읽은 것). (c)의 값 45는 13주차에서 \(\binom{10}{2}\)라는 이름을 얻고 다시 나타난다.

문제 2#

접근. 규범 ① 구조 선언부터: (자음, 모음, 자음)의 길이 3 목록이고, “재사용 허용”이 반복 허용의 신호다. 자리마다 뽑는 기호의 집합이 다르지만(자음/모음), 곱셈 원리는 자리별 개수만 정확하면 그대로 작동한다.

풀이. 글자는 (자음, 모음, 자음)의 길이 3 목록이다(자음 재사용 허용). 1번째는 자음 4가지, 2번째는 모음 3가지, 3번째는 자음 4가지 — 재사용이 허용되므로 1번째에 무엇을 썼든 4가지 그대로이고, 각 단계의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 \(4 \times 3 \times 4 = 48\)가지이다. \(\blacksquare\)

복기. 자리마다 기호의 종류가 달라도 되고(§1.9의 코드), 같은 종류가 두 번 나와도 된다(1\(\cdot\)3번째) — 곱셈 원리가 요구하는 것은 오직 자리별 개수다.

문제 3#

접근. 답안지는 앞 4자리와 뒤 2자리의 규칙이 다른 길이 6 목록이다. 자리마다 선택지 개수가 달라도 — 2, 2, 2, 2, 3, 3 — 곱셈 원리는 각 자리의 개수를 그대로 곱하면 된다.

풀이. 답안지는 (1번 답, …, 4번 답, 5번 답, 6번 답)의 길이 6 목록이다. 앞 4자리는 각 T/F의 2가지, 뒤 2자리는 각 3가지이고, 각 자리의 선택지 개수는 앞 답과 무관하다. 곱셈 원리에 의해

\[ 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2 = 16 \times 9 = 144 \]

가지이다. \(\blacksquare\)

검산. 참/거짓 4문항만이면 \(2^4 = 16\)(예제 2.2의 축소판), 삼지선다 2문항만이면 \(3^2 = 9\) — 두 부분이 독립으로 이어 붙으므로 \(16 \times 9\), 앞의 계산과 일치한다.

문제 4#

접근. 다섯 대상을 먼저 목록과 집합으로 분류한다 — 소괄호 셋은 목록, 중괄호 둘은 집합. 목록끼리는 길이부터, 같으면 위치별 항목을 대조하고(정의 12.1), 집합끼리는 원소만 대조한다(3주차). 종류가 다른 것끼리는 같을 수 없다.

풀이. 같은 것은 \(\{1, 2, 2\} = \{2, 1\}\) 한 쌍뿐이다 — 집합의 상등은 원소만 보고, 둘 다 원소가 1과 2다(중복 표기는 무의미, 순서는 무관). 나머지는 전부 서로 다르다: \((1, 2, 2) \neq (2, 1, 2)\) — 길이는 3으로 같지만 1번째 항목이 \(1 \neq 2\). \((1, 2)\)는 길이가 2이므로 길이 3인 두 목록 어느 쪽과도 다르다(상등의 1차 관문). 집합과 목록은 종류가 다른 대상이므로 \(\{2, 1\}\)과 \((1, 2)\)도 다르다 — 원소가 같아 보여도 한쪽은 순서를 잊고 한쪽은 기억한다.

복기. 상등 판정의 순서: 종류(집합/목록) \(\to\) 길이 \(\to\) 위치별 항목. 이 순서로 검사하면 판정이 기계가 된다.

문제 5#

접근. 작은 사례의 전수 나열 — 공식과 개수가 맞는지 대조하는 검산 습관이다 (예제 2.1 확인 16). 빠뜨림\(\cdot\)겹침을 막는 나열 규칙은 1번째 항목별로 묶기다.

풀이. (a) 반복 허용, 1번째 항목별로 묶어 나열하면 —

\[ (a,a),\ (a,b),\ (a,c),\ (b,a),\ (b,b),\ (b,c),\ (c,a),\ (c,b),\ (c,c) \]

모두 9개. 공식으로는 매 자리 3가지의 길이 2 목록이므로 \(3^2 = 9\) ✓. (b) 반복 금지 — (a)의 나열에서 같은 항목이 겹치는 \((a,a), (b,b), (c,c)\) 세 개를 지우면

\[ (a,b),\ (a,c),\ (b,a),\ (b,c),\ (c,a),\ (c,b) \]

모두 6개. 공식으로는 \(3 \times 2 = 6\) ✓.

복기. 나열과 공식이 서로를 검사한다 — 나열은 공식의 검산이고, 공식은 나열의 빠뜨림 탐지기다. 새 유형을 만나면 작은 사례로 이 대조를 한 번 하는 습관이 세기 오류의 대부분을 걸러 낸다.

문제 6#

접근. 번호 전체를 하나의 목록으로 선언한다 — 지역 3자리 + 국번 4자리 = 길이 7 목록. “0으로 시작 안 함”은 첫 자리의 선택지 개수만 9로 줄이고, 나머지 여섯 자리는 10가지 그대로다.

풀이. 전화번호는 숫자 기호로 된 길이 7 목록이다(지역 3자리 + 국번 4자리, 반복 허용). 지역의 첫 자리는 0을 뺀 \(1\)~\(9\)의 9가지, 나머지 여섯 자리는 각 \(0\)~\(9\)의 10가지이고, 각 자리의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해

\[ 9 \times 10 \times 10 \times 10 \times 10 \times 10 \times 10 = 9 \times 10^6 = 9{,}000{,}000 \]

가지이다. \(\blacksquare\)

검산. 제한 없는 길이 7 목록은 \(10^7\)개인데, 첫 자리 후보가 10 중 9로 줄었으므로 답은 그 \(\frac{9}{10}\) — \(10^7 \times \frac{9}{10} = 9 \times 10^6\)과 일치한다.

문제 7#

접근. 전반부는 전부 세우기 = \(n!\)(정의 12.2). 후반부의 고정 조건은 그 자리의 선택지를 1가지로 만들어 곱셈 원리에 흡수시킨다 — 맨 앞이 A로 정해지면 남는 것은 나머지 4명의 전부 세우기다.

풀이. 세우는 결과는 5명 전부의 반복 없는 길이 5 목록이므로, 그 수는

\[ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \]

가지이다. A가 맨 앞에 서는 경우 — 맨 앞은 A의 1가지, 나머지 네 자리는 남은 4명의 반복 없는 나열로 \(4! = 24\)가지이고, 각 단계의 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 \(1 \times 4! = 24\)가지이다. \(\blacksquare\)

검산. 맨 앞에 서는 사람으로 전체 120가지를 나누면 다섯 사람이 각각 같은 몫을 가지므로 한 사람 몫은 \(120 \div 5 = 24\) — 일치한다.

복기. “고정 조건 = 선택지 1가지”의 번역은 이후 모든 배치 문제에서 재사용된다. 조건은 세기를 어렵게 하는 것이 아니라 어느 자리의 개수를 바꾸는 것뿐이다.

문제 8#

접근. “이웃” 조건은 자리 하나의 개수 조정으로는 번역되지 않는다 — 대상 자체를 재정의한다: A와 B를 한 덩어리로 묶으면 “이웃”이 저절로 보장되고, 배열할 대상이 [AB묶음]과 나머지 3명, 합해서 4개가 된다. 마지막에 묶음 내부의 배치를 곱하는 것을 잊지 않는다.

풀이. A와 B를 한 묶음으로 보면, 세우는 결과는 [묶음], C, D, E 네 대상의 반복 없는 길이 4 목록 — \(4! = 24\)가지다. 묶음 내부의 배치는 (A, B)와 (B, A)의 2가지이고, 외부 배열이 무엇이든 내부 배치의 개수는 2로 일정하다. 곱셈 원리에 의해 \(4! \times 2 = 24 \times 2 = 48\)가지이다. \(\blacksquare\)

검산. 전체 \(5! = 120\) 중 A\(\cdot\)B가 이웃하는 것이 48 — 이웃하지 않는 것은 72로, 이웃하는 쪽이 적다. 다섯 자리 중 A\(\cdot\)B가 앉을 자리 쌍은 이웃 4쌍 대 비이웃 6쌍이므로 비율 \(48 : 72 = 4 : 6\)과 정확히 맞는다.

복기. 묶음 기법 — 붙어야 하는 대상들을 한 항목으로 재정의하고, 마지막에 묶음 내부의 배치 수를 곱한다. 조건을 “대상의 재정의”로 흡수하는 이 기술은 이후 세기 주차에서 반복해 쓴다.

문제 9#

접근. 세 자리 수를 (백, 십, 일)의 길이 3 목록으로 선언하면, 첫 자리만 규칙이 다르다 — 0이 오면 세 자리 수가 아니게 되기 때문이다. 문제 6과 같은 “첫 자리 특별” 유형이다.

풀이. 세 자리 자연수는 (백의 자리, 십의 자리, 일의 자리)의 길이 3 목록이다(반복 허용). 백의 자리는 \(1\)~\(9\)의 9가지(0이면 세 자리가 아니게 된다), 십\(\cdot\)일의 자리는 각 \(0\)~\(9\)의 10가지이고, 각 자리의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 \(9 \times 10 \times 10 = 900\)개이다. \(\blacksquare\) 첫 자리가 특별한 이유: 첫 자리에 0이 오면 자릿수 자체가 무너져 “세 자리 수”라는 세기 대상에서 벗어나기 때문이다 — 규범 ①의 구조 선언이 첫 자리의 선택지를 결정한다.

검산. 세 자리 수는 100부터 999까지이므로 \(999 - 100 + 1 = 900\) ✓.

문제 10#

접근. “짝수”라는 제약은 일의 자리에만 걸린다. 제약이 가장 센 자리부터 정하는 것이 요령이다 — 그래야 각 단계의 선택지 개수가 일정해져 곱셈 원리가 깔끔히 적용된다. 만의 자리부터 정하면 일의 자리의 선택지가 “앞에서 짝수를 써 버렸는가”에 따라 달라져 조건이 깨진다.

풀이. 만들 수는 1~5를 한 번씩 쓴 반복 없는 길이 5 목록 중 일의 자리가 짝수인 것이다. 일의 자리부터 정한다: 짝수는 2와 4의 2가지. 남은 네 자리는 남은 숫자 4개의 반복 없는 나열로 \(4! = 24\)가지 — 일의 자리에 무엇을 골랐든 남는 숫자는 4개이므로 개수는 일정하다. 곱셈 원리에 의해 \(2 \times 4! = 2 \times 24 = 48\)개이다. \(\blacksquare\)

검산. 전체는 \(5! = 120\)개이고, 일의 자리 후보 다섯 숫자가 대칭이므로 일의 자리가 특정 숫자인 것은 각 \(24\)개씩 — 짝수 두 숫자 몫은 \(24 \times 2 = 48\) ✓.

복기. 제약이 센 자리 먼저 — 단계의 순서를 바꾸는 것은 세는 대상을 바꾸지 않으면서 곱셈 원리의 조건을 살려 내는 설계 기술이다.

문제 11#

접근. \(\times\)는 목록 생성 기계다 — 성분의 수가 곧 목록의 길이. 두 크기 모두 §1.5의 사실(과 그 반복)로 계산하고, “어떤 목록의 개수인가”를 규범 ①의 문장으로 붙인다.

풀이. \(|A \times B| = |A| \cdot |B| = 3 \times 5 = 15\) — (\(A\)의 원소, \(B\)의 원소)인 길이 2 목록의 개수다(§1.5). \(|B \times B \times B| = 5 \times 5 \times 5 = 5^3 = 125\) — \(B\)의 원소로 된 길이 3 반복 허용 목록의 개수다. 세 성분이 모두 같은 집합 \(B\)이므로 매 자리 5가지 그대로이고(반복 허용 — \((b, b, b)\) 같은 원소도 \(B^3\)의 정당한 원소다), 곱셈 원리에 의해 \(5^3\)이다.

복기. \(A \times B\)의 크기 계산은 이제 “인정하고 쓰는 사실”이 아니라 근거 ④(이번 주에 증명)다 — 6주차부터 진 빚이 이 문제로 상환 확인된다.

문제 12#

접근. 단계별 선택지를 일반 문자로 센다: 1번째 \(n\), 2번째 \(n - 1\), …, \(k\)번째는 이미 쓴 \(k-1\)개가 빠져 \(n - (k-1)\)가지(확인 8). 곱을 팩토리얼 분수로 정리할 때는 1을 곱하는 변형 — \(\frac{(n-k)!}{(n-k)!}\) — 을 쓴다.

풀이. \(n\)개의 기호에서 반복 없이 길이 \(k\) 목록을 만든다. 1번째 항목의 선택지는 \(n\)가지. 2번째는 이미 쓴 1개가 빠져 \(n - 1\)가지. 일반으로 \(i\)번째는 이미 쓴 \(i - 1\)개가 빠져 \(n - (i - 1)\)가지이고, 앞에서 무엇을 썼든 빠지는 개수는 정확히 \(i - 1\)이므로 선택지의 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 총수는

\[ n \times (n-1) \times \cdots \times (n - k + 1) \]

이다. 여기에 \(\dfrac{(n-k)!}{(n-k)!} = 1\)을 곱하면(근거 ③) 분자가 \(n\)부터 \(1\)까지의 곱으로 이어져

\[ n(n-1)\cdots(n-k+1) \times \frac{(n-k)!}{(n-k)!} = \frac{n(n-1)\cdots(n-k+1) \times (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!} \]

이다. \(\blacksquare\)

검산. \(k = n\)이면 \(\dfrac{n!}{0!} = \dfrac{n!}{1} = n!\) — 전부 세우기와 일치한다. \(0! = 1\)로 정의한 덕분에 공식이 끝 사례까지 작동한다(§1.7). \(n = 7\), \(k = 3\)이면 \(\dfrac{7!}{4!} = 210\) — 예제 2.3(b)와 일치한다 ✓.

복기. 준비 운동 유형 2의 공식 \({}_n\mathrm{P}_k\)가 바로 이 값이다 — 이제 유도를 마쳤으므로 근거 ④로 등록되어, 이름이 아니라 논증으로 쓸 수 있다.

문제 13#

접근. 훈련 3의 뼈대 그대로 — ① 부분집합과 넣음/뺌 목록의 1:1 대응 제작 (두 방향 모두 서술) ② 목록 쪽의 단계별 개수 ③ 곱셈 원리 인용과 결론. 세기 어려운 대상을 세기 쉬운 대상에 실어 나르는 것이 논증의 전부다.

풀이. \(|A| = n\)이라 하고 \(A\)의 원소를 \(x_1, \dots, x_n\)으로 나열하자. 부분집합 \(X \subseteq A\)마다 길이 \(n\) 목록 \((d_1, \dots, d_n)\)을 다음 규칙으로 만든다: \(x_i \in X\)이면 \(d_i = \) 넣음, \(x_i \notin X\)이면 \(d_i = \) 뺌. 거꾸로 넣음/뺌 기호의 길이 \(n\) 목록 \((d_1, \dots, d_n)\) 하나마다 부분집합 \(X = \{x_i : d_i = \text{넣음}\}\)이 정확히 하나 정해지고, 두 규칙은 서로 역이다 — 따라서 부분집합과 목록은 빠짐도 겹침도 없이 1:1로 대응하고, 부분집합의 수는 목록의 수와 같다. 목록의 각 자리는 넣음/뺌의 2가지이고 각 자리의 선택지 개수는 앞 자리와 무관하므로, 곱셈 원리에 의해 목록은 \(2^n\)개다. 따라서 \(|\mathcal{P}(A)| = 2^n\)이다. \(\blacksquare\)

검산. \(n = 0\): 빈 목록 1개 \(\leftrightarrow\) \(\emptyset\) 1개 — 4주차의 \(\mathcal{P}(\emptyset) = \{\emptyset\}\)(크기 1)과 일치하고, \(2^0 = 1\) ✓.

복기. 대응으로 세기 — 세기 어려운 대상을 세기 쉬운 대상에 1:1로 실어 나른다. 이 발상은 문제 16(회문), 문제 18(함수)에서 곧바로 재사용되고, 41주차 (단사\(\cdot\)전단사)를 거쳐 48주차(대등)에서 무한집합의 크기 비교로까지 자란다.

문제 14#

접근. 두 물음은 §1.6 표의 두 행 — 반복 허용과 반복 금지 — 의 대비다. 재료는 같은 기호 5종(1, 3, 5, 7, 9), 길이도 같은 4이고, 조건 하나만 다르다. 첫 자리 걱정(문제 9)은 필요 없다 — 후보에 0이 아예 없다.

풀이. 네 자리 수는 (천, 백, 십, 일)의 길이 4 목록이고, 기호는 홀수 숫자 5종이다. 0이 후보에 없으므로 첫 자리도 5가지 전부 가능하다. 전반부(반복 허용): 매 자리 5가지, 각 자리의 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 \(5^4 = 625\)개이다. 후반부(모두 다름 = 반복 금지): 자리별 선택지는 \(5, 4, 3, 2\)가지 — \(i\)번째 자리에서 이미 쓴 \(i-1\)개가 빠진다. 곱셈 원리에 의해 \(5 \times 4 \times 3 \times 2 = 120\)개이다. \(\blacksquare\)

복기. 같은 재료에서 조건 하나로 \(n^k\)와 \(n(n-1)\cdots(n-k+1)\)이 갈린다 — 문제를 받으면 “앞 선택이 뒤 선택지를 줄이는가”부터 묻는 습관이 두 공식의 선택을 자동화한다.

문제 15#

접근. “적어도 하나의 1”을 정면으로 세면 1이 1개인 경우, 2개인 경우, …로 경우가 다섯 갈래다. 부정 — “1이 하나도 없다” — 은 단 한 갈래다. 전체에서 나쁜 경우를 빼는 여사건 전략(§4 도입 상자)을 쓴다. “적어도 하나”(\(\exists\))의 부정이 “전부 아님”이라는 11주차 부정 규칙이 세기 전략으로 번역되는 자리다.

풀이. 전체 — 길이 5의 이진 문자열은 매 자리 0/1의 2가지, 반복 허용이므로 곱셈 원리에 의해 \(2^5 = 32\)개다(예제 2.2와 같은 세기). 나쁜 경우 — 1이 하나도 없는 문자열은 다섯 자리가 전부 0인 \((0,0,0,0,0)\) 단 1개다. 전체는 “적어도 하나의 1을 포함”과 “1이 하나도 없음”으로 겹침 없이 나뉘므로(지금은 인정하고 쓴다 — 14주차 덧셈 원리), 구하는 개수는

\[ 32 - 1 = 31 \]

개이다. \(\blacksquare\)

검산. 길이 2로 줄이면 전체 4개 중 \(00\) 하나를 뺀 \(01, 10, 11\)의 3개 — 공식 \(2^2 - 1 = 3\) ✓.

복기. 전체에서 빼기 — “적어도 하나”를 만나면 부정을 먼저 세어 본다. 부정 규칙(11주차)이 계산 전략이 되는 이 전환은 14주차에서 정식 도구가 된다.

문제 16#

접근. 회문의 조건 “앞뒤로 읽어도 같다”를 자리의 언어로 번역한다: 5번째 자리는 1번째와, 4번째 자리는 2번째와 같아야 한다. 그러면 스스로 고를 수 있는 자리는 몇 개인가 — 자유 자리의 목록과 회문이 1:1로 대응한다(문제 13의 대응 발상).

풀이. 길이 5의 문자열 \((c_1, c_2, c_3, c_4, c_5)\)가 회문일 조건은 \(c_5 = c_1\)이고 \(c_4 = c_2\)인 것이다(\(c_3\)은 스스로와 같으므로 조건이 없다). 따라서 \(c_1, c_2, c_3\)을 정하면 \(c_4, c_5\)는 자동으로 결정되고, 거꾸로 회문 하나마다 그 앞쪽 세 자리가 하나로 정해진다 — 회문과 (1, 2, 3번째 자리)의 길이 3 목록이 1:1로 대응한다. 그 목록은 기호 3종(\(a, b, c\)), 반복 허용이므로 곱셈 원리에 의해 \(3^3 = 27\)개 — 회문도 27개이다. \(\blacksquare\)

검산. 길이 3의 회문(자유 자리 2개)이면 \(3^2 = 9\)개 — \(aba\), \(aca\), \(aaa\) 등 직접 나열로 9개가 맞는지 작은 사례에서 확인할 수 있다.

복기. 제약 조건은 자유 자리의 개수를 줄인다 — “몇 자리가 진짜 선택인가”를 먼저 세는 것이 회문형 문제의 표준 접근이다.

문제 17#

접근. \(5 \times 4 = 20\)이라는 계산 자체는 오류가 아니다 — 규범 ①로 돌아가 그것이 무엇을 세는지 선언해 보면, 세는 대상이 문제의 대상과 어긋나 있음이 드러난다. 목록과 집합의 구분(정의 12.1)이 급소다.

풀이. \(5 \times 4\)가 세는 것은 (첫 사람, 둘째 사람)의 반복 없는 길이 2 목록의 수다. 그런데 악수 쌍은 \(\{A, B\}\)라는 집합이다 — 누가 먼저 손을 내밀었는지는 악수를 구별하지 않는다. 목록 \((A, B)\)와 \((B, A)\)는 서로 다르지만 같은 악수 쌍 \(\{A, B\}\)에 대응하므로, \(5 \times 4 = 20\)은 모든 쌍을 정확히 두 번씩 센 것이다. 각 쌍이 정확히 2번씩 세어졌으므로 실제 쌍의 수는 \(20 \div 2 = 10\)이다.

검산. 5명을 1~5로 부르면 쌍은 \(\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}\) — 나열해도 10개다 ✓.

복기. 순서 지우기 나눗셈 — 목록으로 일단 세고, 각 대상이 정확히 \(m\)번씩 세어졌으면 \(m\)으로 나눈다. 이 한 수가 다음 주 조합 \(\binom{n}{k}\)의 탄생 원리다 — 13주차에서 \(m = k!\)의 일반형으로 다시 만난다.

문제 18#

접근. “각 원소에 하나씩 배정”을 목록으로 번역한다 — \(A = \{a_1, a_2, a_3\}\) 이라 하면 배정 결과 하나는 (\(a_1\)의 값, \(a_2\)의 값, \(a_3\)의 값)이라는 길이 3 목록으로 완전히 기록되고, 거꾸로 그런 목록 하나가 배정 하나를 정한다. 대응으로 세기(문제 13)의 재등장이다.

풀이. \(A = \{a_1, a_2, a_3\}\)이라 하자. 배정 하나는 (\(a_1\)에 배정한 값, \(a_2\)에 배정한 값, \(a_3\)에 배정한 값)이라는, \(B\)의 원소로 된 길이 3 목록과 1:1로 대응한다. 서로 다른 원소에 같은 값을 배정해도 되므로 반복 허용이고, 각 자리의 선택지는 \(|B| = 4\)가지로 앞 선택과 무관하다. 곱셈 원리에 의해 \(4 \times 4 \times 4 = 4^3 = 64\)가지이다. \(\blacksquare\)

복기. 함수 = 출력 목록 — 입력마다 출력 하나를 정하는 것이 함수이고, 그 전모는 출력들의 목록 하나로 기록된다. 일반으로 \(|A| = m\), \(|B| = n\)이면 함수는 \(n^m\)개 — 40주차에서 함수의 정의와 함께 이 세기를 회수한다.

문제 19#

접근. 문제 18에서 조건 하나만 바뀌었다 — “서로 다른 원소에 서로 다른 값” 은 출력 목록에 같은 값이 두 번 나올 수 없다는 뜻, 곧 반복 금지다. §1.6 표의 행이 바뀌는 것뿐이다.

풀이. 배정은 문제 18의 대응 그대로 \(B\)의 원소로 된 길이 3 목록인데, 이번엔 반복 금지다. 자리별 선택지는 \(4, 3, 2\)가지 — \(i\)번째 자리에서 이미 배정한 \(i - 1\)개의 값이 빠진다 — 이고 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 \(4 \times 3 \times 2 = 24\)가지이다. \(\blacksquare\)

복기. 일반으로 \(|A| = k\), \(|B| = n\)이면 단사 배정은 반복 없는 길이 \(k\) 목록의 수 \(\dfrac{n!}{(n-k)!}\)가지(문제 12의 공식)다 — 41주차에서 단사함수의 정의와 함께 재회한다. 문제 18(반복 허용)과 이 문제(반복 금지)의 대비가 “함수 대 단사함수”의 세기 버전이다.

문제 20#

접근. 곱셈 원리의 핵심 조건 — 각 단계의 선택지 개수가 앞 단계의 결과와 무관 — 을 일부러 부수는 상황을 조작해 만든다. 1단계의 선택에 따라 2단계의 가짓수 자체가 달라지는 조건부 규칙(특정 선택 뒤의 제한이나 특전) 하나면 된다. 격자로 그리면 행마다 칸 수가 다른, 직사각형이 아닌 그림이 나온다.

풀이. (예시 답안) 식당에서 밥 또는 빵을 고른 뒤 음료를 고르는데, 밥을 고르면 음료 3종 중에서, 빵을 고르면 음료 5종 중에서 고를 수 있다고 하자. 2단계의 선택지 개수(3 대 5)가 1단계의 결과에 의존하므로, 곱셈 원리를 전체에 통째로 적용할 수 없다 — \(2 \times 3\)도 \(2 \times 5\)도 답이 아니다. 세는 방법: 1단계의 결과별로 경우를 나눈다. 밥인 경우는 \(1 \times 3 = 3\)가지, 빵인 경우는 \(1 \times 5 = 5\)가지 — 각 경우 안에서는 개수가 일정해 곱셈 원리가 작동한다 — 이고, 두 경우는 겹치지 않고 전체를 덮으므로 합해서 \(3 + 5 = 8\)가지이다.

복기. 곱셈 원리는 “단계”로 쪼갤 때, 덧셈은 “경우”로 쪼갤 때 쓴다. 단계 쪼개기가 무너지는 지점(개수의 의존)이 곧 경우 쪼개기로 전환하는 신호다. 겹침 없이 나눠 더하기의 정당화(덧셈 원리)는 14주차에서, 경우 나누기의 본격 훈련은 17주차에서 한다.

다음 주 예고: 순서를 지우면 무엇이 남는가 — 조합 \(\binom{n}{k}\)다. 문제 17에서 2로 나눈 “순서 지우기 나눗셈”이 \(k!\)로 나누는 일반 공식이 되고, 같은 대상을 두 가지 방법으로 세어 등식을 증명하는 세기 논증(combinatorial proof)이라는 새 증명 기법을 만난다. 파스칼 삼각형과 이항정리(고2 연계)가 전부 거기서 나온다. 이번 주의 서술 규범 — 무엇을 세는지 먼저 선언한다 — 이 그대로 다음 주의 증명 도구가 된다.