12주차 — 목록과 곱셈 원리

12주차 — 목록과 곱셈 원리#

이 주의 길잡이

핵심 문장: 세기의 답은 숫자가 아니라 “왜 그 곱셈인가”라는 논증이다.

이 주의 위치: 50주 과정의 12주차. 3부(세기)의 첫 주 — 고2~3 확률과 통계의 경우의 수\(\cdot\)순열이 여기서 재건축되고, 4주차와 6주차에서 인정하고 쓰던 크기 사실 두 개를 회수한다.

원서 대응: BoP(Book of Proof) 3.1 (Lists), 3.2 (Multiplication Principle), 3.3 (Factorials 일부). 원서 없이 읽을 수 있다.

이번 주 목표#

  1. 목록(list)의 정의를 백지에 쓰고, 상등 기준으로 집합과 구분할 수 있다.

  2. 곱셈 원리로 세기 문제를 풀되, 답이 나오는 이유를 문장으로 서술할 수 있다.

  3. 팩토리얼 \(n!\)과 반복 없는 목록의 개수 \(n(n-1)\cdots(n-k+1)\)을 유도할 수 있다.

  4. \(|A \times B| = |A| \cdot |B|\)(6주차)와 \(|\mathcal{P}(A)| = 2^n\)(4주차) — 미뤄 둔 두 크기 사실에 곱셈 원리의 논증을 붙일 수 있다.

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

준비 운동 (11주차 복습)#

  1. “\(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y^3 = x\)”의 부정을 만드시오.

  2. modus tollens의 전제와 결론을 쓰시오.

  3. 지난주 모의시험 오답 1개를 백지에서 다시 푸시오.

  4. (진단) 학생 5명 중 회장 1명과 부회장 1명을 뽑는 방법의 수를 구하고, 그 답이

나오는 이유를 두 문장으로 서술해 보자. (겸직은 불가하다. 이번 주가 끝나기 전에 이 기록을 다시 본다.)

자주 나오는 세 가지 답 — 4번 문항#

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

  • 유형 1 — 답만 제시. “20가지”라고 적고 끝낸다. 답은 옳다. 빠진 것은 이유다 —

이번 주의 채점 기준은 답의 숫자가 아니라 “무엇을 세었고 왜 곱했는가”의 서술이고, 그 서술의 형식(서술 규범, §1.9)이 이번 주에 처음 제시된다.

  • 유형 2 — 공식 인용. “순열이므로 \(5 \times 4 = 20\)” 또는 “\({}_5\mathrm{P}_2 = 20\)”이라고

적는다. 계산은 옳다. 문제는 공식의 이름이 근거의 자리를 대신 차지하고 있다는 것이다 — 그 공식이 왜 그 값을 주는지 물으면 답할 재료가 없다. 이번 주에 그 공식이 곱셈 원리에서 유도되는 과정 전체를 재건한다(문제 12).

  • 유형 3 — 나열 시도. (갑,을), (갑,병), … 을 전부 적어 세거나, 적다가 멈춘다.

나열 자체는 옳은 방법이고 검산의 표준 도구이기도 하다(예제 2.1에서 그렇게 쓴다). 문제는 크기가 조금만 커져도 나열이 실행 불가능해진다는 것이다 — 나열을 대신하는 원리가 이번 주의 곱셈 원리다.

개념 — 목록과 곱셈 원리#

1 나열로 세기를 시도하면 어디서 막히는가#

이번 주의 물음은 “몇 가지인가?”이다. 이미 아는 방법 — 전부 나열해서 세기 — 만으로 다음 문제를 밀어붙여 보자.

시도 — 전부 나열로 밀어붙이기

문제: 대문자 1개와 숫자 2개를 이어 붙인 코드(예: A07, K99)는 몇 가지인가?

“A00, A01, A02, …, A99 — 여기까지 100개. 다음은 B00, B01, …, B99 — 또 100개.

다음은 C00, … “

여기서 멈춘다. 이 방식은 두 군데서 무너진다. 첫째, 끝까지 가려면 문자 26종마다 100개씩, 2600개를 적어야 한다 — 적는 것 자체가 실행 불가능에 가깝고, 참/거짓 20문항 답안지처럼 백만 단위가 되면 아예 불가능하다. 둘째, 다 적었다 해도 “빠뜨린 것도 겹친 것도 없다”를 무엇이 보장하는가 — 나열이 세기가 되려면 그 보장이 따로 필요하다. 필요한 것은 나열하지 않고 개수를 확정하는 논증이고, 그 논증을 세우려면 먼저 세는 대상이 정확히 무엇인지의 언어가 필요하다.

확인 1. 코드 A07을 (A, 0, 7)이라는 나열로 적어 보자. (A, 0, 7)과 (A, 7, 0)은

같은 코드인가? 그리고 (B, 2, 2)처럼 같은 기호가 두 번 나오는 코드도 있는가?

답

다른 코드다 — A07과 A70은 다르다. 항목의 순서가 결과를 바꾼다.

(B, 2, 2) 같은 코드도 있다 — B22는 정상적인 코드다. 같은 기호의 중복이

허용된다. “순서가 있고 중복이 허용되는 나열” — 이 두 특징이 세는 대상의

정체이고, §1.2에서 이 정체에 이름을 붙인다.

2 세는 대상의 언어 — 정의를 만들어 보기#

일상에서 “몇 가지인가?”를 묻게 되는 대상들을 모아, 방금의 두 특징으로 판정해 보자.

대상

순서가 중요한가

중복이 허용되는가

비밀번호 1417

예 (1471과 다르다)

예 (1이 두 번)

단어 book

예 (obok과 다르다)

\(\underline{\quad(1)\quad}\)

좌표 \((2, 5)\)

\(\underline{\quad(2)\quad}\)

예 (\((3,3)\)도 좌표다)

당첨 번호의 모임 \(\{3, 17, 29\}\)

아니오 (뽑힌 순서는 잊는다)

\(\underline{\quad(3)\quad}\)

확인 2. 빈칸 (1)(2)(3)을 채우고, 마지막 행이 앞의 세 행과 무엇이 다른지

한 문장으로 적어 보자.

답

(1) 예 — o가 두 번 나온다. (2) 예 — \((2,5)\)와 \((5,2)\)는 다른 점이다(6주차

순서쌍의 상등 기준). (3) 아니오 — 같은 번호가 두 번 뽑히는 일은 없고, 집합

표기에서 중복은 무의미하다(3주차). 앞의 세 행은 순서 있음\(\cdot\)중복 허용의

나열이고, 마지막 행만 집합이다. “몇 가지인가?”의 대부분은 앞의 세 행

같은 대상 — 순서 있고 중복 허용되는 나열 — 을 세는 문제다.

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

정의 12.1 — 목록 (list) [백지 암기 대상]#

목록은 순서가 있고 중복이 허용되는 대상들의 나열이다. \((a, b, c)\)처럼 쓰고,

항목의 개수를 길이(length)라 한다.

두 목록이 같다는 것은, 길이가 같고 같은 위치의 항목이 모두 같다는 뜻이다.

\((a, b, c)\)는 “에이, 비, 씨의 목록” 또는 그냥 “에이 비 씨”로 읽는다. 6주차의 순서쌍 \((a, b)\)는 길이 2인 목록이다 — 표기가 같은 것은 우연이 아니라, 순서쌍이 목록의 특수한 경우이기 때문이다. 집합과의 대비를 한 번 더 고정해 두자.

집합 \(\{a, b\}\)

목록 \((a, b)\)

순서

무관: \(\{1, 2\} = \{2, 1\}\)

중요: \((1, 2) \neq (2, 1)\)

중복

무의미: \(\{1, 1\} = \{1\}\)

유의미: \((1, 1)\)은 길이 2

상등 기준

원소가 같으면 같다

길이와 위치별 항목까지 같아야 같다

3 정의 해부 — 조각마다 하는 일#

정의 12.1의 조각마다 세기에서 맡는 역할이 다르다. 이 정의의 용도는 계산이 아니라 판정(두 나열이 같은 결과인가 다른 결과인가)이므로, 셋째 열을 판정 중심으로 적는다.

조각

하는 일

판정에서의 역할

“순서가 있고”

위치에 의미 부여

\((1,2)\)와 \((2,1)\)을 서로 다른 것으로 센다

“중복이 허용되는”

같은 항목의 재등장 허가

\((1,1)\) 같은 결과를 세기 대상에 포함시킨다

“길이가 같고”

상등의 1차 관문

길이가 다르면 비교할 것도 없이 다르다

“같은 위치의 항목이 모두 같다”

상등의 2차 관문

위치 하나라도 어긋나면 다른 목록이다

조각 삭제 실험. 첫째 조각의 “순서”를 지워 보자. 그러면 \((1, 2) = (2, 1)\)이 되어 목록은 집합과 구별되지 않는다. 준비 운동 4번에서 (갑, 을)과 (을, 갑)은 “갑 회장\(\cdot\)을 부회장”과 “을 회장\(\cdot\)갑 부회장” — 명백히 다른 결과다. 순서 조각이 빠지면 이 둘을 하나로 세게 되어 20이 아니라 10이 나온다.

확인 3. 이번에는 둘째 조각의 “중복 허용”을 지워 보자. 참/거짓 5문항

답안지 중 무엇이 세기 대상에서 사라지는가?

답

(T, T, T, T, T)처럼 같은 답이 두 번 이상 나오는 답안지 전부가 사라진다.

남는 것은 다섯 항목이 전부 다른 답안지뿐인데, 기호가 T와 F 두 종류라 길이

5에서 그런 답안지는 아예 없다 — 세기 대상이 통째로 비어 버린다. 어느

조각을 지워도 세는 대상 자체가 달라지므로, 세기의 첫 동작은 언제나 “지금

세는 것이 어떤 목록인가”의 확인이다.

확인 4. 상등 기준으로 판정해 보자. (가) \((1, 2, 2)\)와 \((2, 1, 2)\)는 같은가?

(나) \(\{1, 2, 2\}\)와 \(\{2, 1\}\)은 같은가?

답

(가) 다르다 — 길이는 3으로 같지만 1번째 항목이 \(1 \neq 2\)로 어긋난다.

(나) 같다 — 집합의 상등은 원소만 보고, 둘 다 원소가 1과 2다(중복 표기는

무의미, 순서는 무관 — 3주차). 같은 재료라도 목록으로 보는가 집합으로

보는가에 따라 판정이 뒤집힌다. 문제 4에서 이 판정을 한 벌 전체로 연습한다.

4 두 단계 선택 — 곱셈이 나오는 자리#

세는 대상의 언어가 생겼으니, 나열 없이 개수를 확정하는 논증을 만들 차례다. 작은 사례부터 — \(A = \{a, b\}\)의 원소 하나와 \(B = \{1, 2, 3\}\)의 원소 하나로 길이 2 목록 (1번째는 \(A\)에서, 2번째는 \(B\)에서)을 만든다. 전부를 격자에 나열해 보자.

1번째 \(\backslash\) 2번째

\(1\)

\(2\)

\(3\)

\(a\)

\((a, 1)\)

\((a, 2)\)

\((a, 3)\)

\(b\)

\(\underline{\quad(1)\quad}\)

\(\underline{\quad(2)\quad}\)

\(\underline{\quad(3)\quad}\)

확인 5. 빈칸 (1)(2)(3)을 채우고, 목록의 총수를 덧셈식으로 한 번,

곱셈식으로 한 번 적어 보자.

답

(1) \((b, 1)\) (2) \((b, 2)\) (3) \((b, 3)\). 총수는 행별로 세면 \(3 + 3 = 6\),

곱셈으로 쓰면 \(2 \times 3 = 6\). 두 식은 같은 셈이다 — 1번째 항목 하나마다

2번째의 가능성 3개가 통째로 한 행씩 붙고, 같은 수 3을 행의 개수 2번

더하는 것이 곱셈 \(2 \times 3\)의 정의이기 때문이다. 여기가 세기에서 곱셈이

나오는 자리다 — 덧셈이 아니라 곱셈인 이유는 “행마다 같은 개수”라는 사실

하나에 걸려 있다.

방금의 관찰을 일반의 길이로 확장해 이름을 붙인다. 원리 자체에 새로운 계산은 없다 — 격자에서 한 “행마다 같은 개수의 반복 덧셈”을 곱셈으로 요약했을 뿐이다.

곱셈 원리 (Multiplication Principle) [백지 암기 대상]#

길이 \(k\)의 목록을 만들 때, 1번째 항목의 선택지가 \(a_1\)가지, (1번째 선택과

무관하게) 2번째가 \(a_2\)가지, …, \(k\)번째가 \(a_k\)가지이면, 가능한 목록의 총수는

\[ a_1 \times a_2 \times \cdots \times a_k \]

핵심 조건. 각 단계의 선택지 개수가 앞 단계의 결과와 무관하게 일정해야 한다. 무엇을 골랐는지(선택지의 내용)는 앞 단계에 따라 달라져도 되고, 몇 가지인지(선택지의 개수)만 같으면 된다. 격자의 언어로 말하면 — 행마다 칸의 개수가 같아야 “행 수 \(\times\) 칸 수”가 성립한다.

확인 6. 준비 운동 4번(회장\(\cdot\)부회장)에서 2번째 항목(부회장)의 선택지는,

회장이 갑이면 {을, 병, 정, 무}이고 회장이 을이면 {갑, 병, 정, 무}다 — 앞

단계의 결과에 따라 달라진다. 그런데도 곱셈 원리를 쓸 수 있는 이유는

무엇인가?

답

원리가 요구하는 것은 내용의 무관이 아니라 개수의 무관이기 때문이다.

회장이 누구든 부회장 후보는 정확히 4명 — 선택지의 집합은 매번 다르지만

크기는 4로 일정하다. 따라서 \(5 \times 4\)가 성립한다. 반대로 개수 자체가 앞

결과에 따라 달라지는 상황에서는 원리가 통째로 무너진다 — 그런 상황을

문제 20에서 직접 설계해 본다.

일반 \(k\)단계의 곱셈 원리는 두 단계 논증(격자)을 \(k - 1\)번 반복한 것이다 — 길이 3은 “길이 2 목록 하나마다 3번째 항목이 \(a_3\)개씩” 붙는 격자를 한 번 더 그리면 된다. 이 “반복”을 엄밀한 증명으로 만드는 도구가 수학적 귀납법이고 31주차에서 배운다. 이번 주에는 두 단계는 증명된 것으로, 일반형은 지금은 인정하고 쓴다(31주차에서 증명).

5 빚 회수 ① — \(|A \times B| = |A| \cdot |B|\) (6주차)#

6주차 §1.4에서 “지금은 인정하고 쓴다(12주차에서 증명)”라고 미뤄 둔 크기 사실이 정확히 방금의 격자 논증이다. 빚을 회수하자.

사실. 유한집합 \(A, B\)에 대해 \(|A \times B| = |A| \cdot |B|\)이다.

증명. \(A \times B\)의 원소는 \(a \in A\), \(b \in B\)인 순서쌍 \((a, b)\) — 곧 1번째 항목을 \(A\)에서, 2번째 항목을 \(B\)에서 고른 길이 2 목록이다. 1번째 항목의 선택지는 \(|A|\)가지이고, 1번째로 무엇을 골랐든 2번째 항목의 선택지는 \(|B|\)가지로 일정하다. 격자로 나열하면 행이 \(|A|\)줄, 각 행에 칸이 \(|B|\)개씩 — 총수는 \(|B|\)를 \(|A|\)번 더한 것, 곧 \(|A| \cdot |B|\)이다. \(\blacksquare\)

이 증명에서 2번째 선택지의 집합은 매번 같은 \(B\)였지만, 행마다 들어 있는 내용이 달라도 각 행의 칸 수가 같기만 하면 같은 행-합 논증이 그대로 작동한다 — 이것이 두 단계 곱셈 원리다(확인 6의 회장\(\cdot\)부회장이 바로 그 경우다).

확인 7. \(|A| = 3\), \(|B| = 4\), \(|C| = 2\)라 하자. (가) \(|A \times B|\)는

얼마인가. (나) 1번째는 \(A\)에서, 2번째는 \(B\)에서, 3번째는 \(C\)에서 고른 길이 3

목록의 총수는 얼마인가.

답

(가) \(3 \times 4 = 12\). (나) 길이 2 목록 12개 각각에 3번째 항목이 2가지씩

붙으므로 \(12 \times 2 = 24\) — 곱셈 원리로 한 번에 쓰면 \(3 \times 4 \times 2 = 24\).

(나)가 바로 “격자를 한 번 더 그리는” 반복이다. 문제 11에서 같은 계산을

\(B \times B \times B\)로 다시 만난다.

6 반복 허용과 반복 금지#

기호 \(n\)종으로 길이 \(k\) 목록을 만드는 두 가지 기본형을 정리한다.

조건

개수

이유

반복 허용

\(n^k\)

매 단계 선택지가 \(n\)가지 그대로

반복 금지

\(n(n-1)(n-2)\cdots(n-k+1)\)

단계마다 이미 쓴 기호가 빠져 1가지씩 감소

반복 허용은 곱셈 원리에 \(a_1 = \cdots = a_k = n\)을 넣은 것이다. 반복 금지에서 마지막 항이 \(n - k + 1\)인 것은 자주 틀리는 자리이므로 직접 세어 확정해 두자.

확인 8. 반복 금지에서 \(k\)번째 항목을 고르는 순간, 이미 배치되어 쓸 수

없는 기호는 \(\underline{\quad}\)개다. 따라서 \(k\)번째의 선택지는

\(n - \underline{\quad} = n - k + 1\)가지다. 두 빈칸을 채워 보자.

답

둘 다 \(k - 1\). \(k\)번째 직전까지 채운 자리가 1번째부터 \(k-1\)번째까지의

\(k - 1\)개이기 때문이다. 마지막 항을 \(n - k\)로 적는 경우가 많다 — “\(k\)번째

자리”라는 번호를 그대로 빼기 때문인데, 빼야 할 것은 자리 번호가 아니라

이미 쓴 기호의 개수 \(k - 1\)이다. 검산 한 줄: \(k = 1\)을 넣으면

\(n - 1 + 1 = n\) — 첫 항목은 제약 없이 \(n\)가지, 맞는 값이다.

7 전부 세우기 — 팩토리얼#

반복 금지에서 \(k = n\)인 경우 — \(n\)개의 기호를 전부 써서 일렬로 세우는 경우 — 의 개수는 \(n(n-1)\cdots(n-n+1) = n(n-1)\cdots 2 \cdot 1\)이다. 이 곱은 앞으로 쉬지 않고 등장하므로 이름과 기호를 받는다.

정의 12.2 — 팩토리얼 (factorial) [백지 암기 대상]#

\[ n! = n \times (n-1) \times \cdots \times 2 \times 1, \qquad 0! = 1 \]

기호 \(n!\)은 “엔 팩토리얼”로 읽는다. 뜻은 방금의 유도 그대로 — \(n\)개를 전부 사용해 반복 없이 일렬로 세우는(길이 \(n\) 목록의) 가짓수다.

확인 9. \(5!\)을 계산해 보자. 그리고 그 값이 세고 있는 것이 무엇인지

한 문장으로 적어 보자.

답

\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\). 서로 다른 5개를 전부 써서

일렬로 세우는 방법의 수 — 예컨대 학생 5명을 한 줄로 세우는 가짓수다

(문제 7에서 그대로 쓴다).

\(0! = 1\)인 이유. 0개의 기호로 만들 수 있는 길이 0의 목록은 빈 목록 \(()\) 한 개다 — 만들 방법이 없는 것(0개)이 아니라, 아무것도 나열하지 않는 방법이 정확히 하나 있는 것이다. 공집합의 멱집합이 원소 1개(\(\emptyset\) 자신)를 가졌던 것(4주차 \(\mathcal{P}(\emptyset) = \{\emptyset\}\))과 같은 이치다. \(0! = 0\)으로 정하면 공식 \(\frac{n!}{(n-k)!}\)은 \(k = n\)에서 분모 \((n-k)! = 0!\)이 0이 되어 나눗셈 자체가 정의되지 않는다(0으로 나누기). \(0! = 1\) 덕분에 공식이 \(k = n\)까지 작동함을 문제 12의 검산에서 확인한다.

8 빚 회수 ② — \(|\mathcal{P}(A)| = 2^n\) (4주차)#

4주차 §1.7에서 인정하고 쓰기 시작한 사실 — \(|A| = n\)이면 \(|\mathcal{P}(A)| = 2^n\) — 에 이번 주의 언어로 논증을 붙인다. 발상은 하나다: 부분집합은 세기 어렵지만 목록은 세기 쉽다. 그러니 부분집합 하나하나를 목록 하나하나에 대응시킨다.

확인 10. \(A = \{x_1, x_2, x_3\}\)이라 하자. 부분집합 \(\{x_1, x_3\}\)을 “각

원소를 넣었는가/뺐는가”의 길이 3 목록으로 적으면

(넣음, \(\underline{\quad}\), \(\underline{\quad}\))이다. 빈칸을 채우고, 거꾸로

목록 (뺌, 뺌, 뺌)에 대응하는 부분집합이 무엇인지도 적어 보자.

답

(넣음, 뺌, 넣음) — \(x_2\)는 안 들어갔고 \(x_3\)은 들어갔다. 목록

(뺌, 뺌, 뺌)에 대응하는 부분집합은 아무 원소도 넣지 않은 \(\emptyset\)이다.

부분집합마다 목록이 하나씩, 목록마다 부분집합이 하나씩 — 빠짐도 겹침도

없는 1:1 대응이다. 남은 일은 목록 쪽을 세는 것뿐이다.

논증. \(A\)의 원소를 \(x_1, \dots, x_n\)으로 나열하자. 부분집합 \(X \subseteq A\)마다 길이 \(n\) 목록 \((d_1, \dots, d_n)\) (\(x_i \in X\)이면 \(d_i\) = 넣음, 아니면 뺌)이 하나 정해지고, 거꾸로 그런 목록 하나마다 부분집합 \(\{x_i : d_i = \text{넣음}\}\)이 정확히 하나 만들어진다 — 부분집합과 목록이 1:1로 대응한다. 넣음/뺌 두 기호로 된 길이 \(n\)의 반복 허용 목록은 곱셈 원리에 의해 \(2^n\)개다. 따라서 부분집합도 \(2^n\)개다. \(\blacksquare\)

이 논증이 기대는 곱셈 원리의 일반형은 §1.4 끝에서 말한 대로 31주차 귀납법에서 증명된다 — 4주차가 예고한 “31주차에서 증명”은 그 최종 완결을 가리키고, 이번 주의 몫은 “왜 하필 \(2^n\)인가”를 목록의 언어로 정확히 논증하는 것이다. 이 논증 전체를 문제 13에서 백지에 재현한다.

확인 11. 7주차 §1.6에서 명제 변수 \(n\)개짜리 진리표는 \(2^n\)행이라고 했다.

이 사실을 목록의 언어로 다시 설명해 보자 — 진리표의 행 하나는 어떤 목록인가?

답

행 하나는 (\(P_1\)의 값, …, \(P_n\)의 값)이라는 길이 \(n\) 목록이고, 각 자리의

기호는 T/F 두 종류에 반복 허용이다 — 곱셈 원리에 의해 \(2^n\)행. 부분집합

세기(넣음/뺌)와 진리표 행 세기(T/F)는 기호의 이름만 다른 같은 세기다.

9 세기 답안의 서술 규범, 그리고 근거 목록 갱신#

이번 주부터 세기 문제의 답안은 숫자가 아니라 짧은 논증이다. 형식을 규범으로 못 박는다.

세기 답안의 서술 규범

① 무엇을 세는지 — 어떤 대상의, 길이 몇의 목록인지, 반복이 허용되는지 —

를 먼저 선언한다.

② 단계별 선택지의 개수를 세고, 그 개수가 앞 단계의 결과와 무관함을

확인한다.

③ 곱셈 원리를 인용해 계산한다.

§1.1의 코드 문제로 시연하면 —

“코드는 (문자, 숫자, 숫자)의 길이 3 목록이다(반복 허용). 1번째는 26가지, 2\(\cdot\)3번째는 각 10가지이고, 각 단계의 선택지 개수는 앞 선택과 무관하다. 곱셈 원리에 의해 \(26 \times 10 \times 10 = 2600\)가지다.”

나열로는 실행 불가능하던 세기가 세 문장으로 끝났고, 세 문장 각각이 검사 가능한 근거다 — 이것이 세기를 증명 훈련으로 만드는 장치다.

근거 목록도 갱신한다. 칸은 그대로 네 개다 — ① 칸에 정의 두 개가 추가되고, ④ 칸에 이번 주의 원리와 회수된 사실들이 들어갈 뿐이다.

근거

내용

이번 주에는 이렇게 쓴다

① 정의

정의 12.1(목록), 12.2(팩토리얼) 추가

“다섯 자리 수” \(\leftrightarrow\) “길이 5 목록” 사이를 번역한다

② 닫힘성

정수의 합\(\cdot\)차\(\cdot\)곱은 정수

이번 주에는 등장이 적다

③ 등식의 성질

대입 / 전개 / 묶기

\(\frac{(n-k)!}{(n-k)!}\)을 곱해 팩토리얼 꼴로 정리한다(문제 12)

④ 이미 증명한 명제

곱셈 원리(두 단계는 §1.4~1.5의 격자 논증으로 증명, 일반형은 31주차까지 인정), \(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert\), \(\lvert \mathcal{P}(A) \rvert = 2^n\)(논증은 이번 주, 최종 완결은 31주차)

세기 답안의 인용 근거 — “곱셈 원리에 의해”가 이번 주의 표준 문구다

확인 12. 어떤 답안에 다음 세 근거가 나왔다. 각각 서술 규범과 근거 목록을

통과하는가?

(가) “답: 48” (나) “코드는 길이 3 목록이고 자리별로 4, 3, 4가지이므로 곱셈

원리에 의해 48가지” (다) “순열 공식 \({}_5\mathrm{P}_2\)에 의해 20가지”

답

(가) 불통과 — 규범 ①②③이 전부 없다. 답이 옳아도 검사할 근거가 없다.

(나) 통과 — ①(구조 선언) ②(단계별 개수) ③(원리 인용)이 다 있다.

(다) 불통과 — 공식의 이름은 근거 목록에 없다. 같은 내용을 “(1번째, 2번째)의

길이 2 반복 없는 목록, \(5 \times 4\)”로 다시 적으면 근거 ④(곱셈 원리)가 되어

통과한다. 공식을 쓰고 싶으면 먼저 유도해 근거 ④에 등록해야 한다 — 그

등록 절차가 문제 12다.