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

:::{admonition} 이 주의 길잡이
:class: keybox

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

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

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

## 이번 주 목표

1. 목록(list)의 **정의**를 백지에 쓰고, 상등 기준으로 집합과 구분할 수 있다.
1. 곱셈 원리로 세기 문제를 풀되, **답이 나오는 이유를 문장으로 서술**할 수 있다.
1. 팩토리얼 $n!$과 반복 없는 목록의 개수 $n(n-1)\cdots(n-k+1)$을 유도할 수 있다.
1. $|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$"의 부정을 만드시오.
1. modus tollens의 전제와 결론을 쓰시오.
1. 지난주 모의시험 오답 1개를 백지에서 다시 푸시오.
1. (진단) 학생 5명 중 회장 1명과 부회장 1명을 뽑는 방법의 수를 구하고, 그 답이

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

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

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

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

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

- **유형 2 — 공식 인용.** "순열이므로 $5 \times 4 = 20$" 또는 "${}_5\mathrm{P}_2 = 20$"이라고

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

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

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

## 개념 — 목록과 곱셈 원리

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

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

:::{admonition} 시도 — 전부 나열로 밀어붙이기
:class: quotebox

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

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

다음은 C00, … "
:::

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

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

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

:::{admonition} 답
:class: quotebox dropdown

다른 코드다 — 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}$ |

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

한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

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

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

:::{container} quotebox
**목록**은 순서가 있고 중복이 허용되는 대상들의 나열이다. $(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이 나온다.

:::{container} quotebox
**확인 3.** 이번에는 둘째 조각의 "중복 허용"을 지워 보자. 참/거짓 5문항

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

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

:::{container} quotebox
**확인 4.** 상등 기준으로 판정해 보자. (가) $(1, 2, 2)$와 $(2, 1, 2)$는 같은가?

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

:::{admonition} 답
:class: quotebox dropdown

(가) 다르다 — 길이는 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}$ |

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

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

:::{admonition} 답
:class: quotebox dropdown

(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) [백지 암기 대상]

:::{container} quotebox
길이 $k$의 목록을 만들 때, 1번째 항목의 선택지가 $a_1$가지, (1번째 선택과

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

$$
a_1 \times a_2 \times \cdots \times a_k
$$
:::

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

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

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

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

무엇인가?
:::

:::{admonition} 답
:class: quotebox dropdown

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

회장이 누구든 부회장 후보는 정확히 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$부회장이 바로 그 경우다).

:::{container} quotebox
**확인 7.** $|A| = 3$, $|B| = 4$, $|C| = 2$라 하자. (가) $|A \times B|$는

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

목록의 총수는 얼마인가.
:::

:::{admonition} 답
:class: quotebox dropdown

(가) $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$인 것은 자주 틀리는 자리이므로 직접 세어 확정해 두자.

:::{container} quotebox
**확인 8.** 반복 금지에서 $k$번째 항목을 고르는 순간, 이미 배치되어 쓸 수

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

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

:::{admonition} 답
:class: quotebox dropdown

둘 다 $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) [백지 암기 대상]

:::{container} quotebox
$$
n! = n \times (n-1) \times \cdots \times 2 \times 1, \qquad 0! = 1
$$
:::

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

:::{container} quotebox
**확인 9.** $5!$을 계산해 보자. 그리고 그 값이 세고 있는 것이 무엇인지

한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$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$ — 에 이번 주의 언어로 논증을 붙인다. 발상은 하나다: **부분집합은 세기 어렵지만 목록은 세기 쉽다. 그러니 부분집합 하나하나를 목록 하나하나에 대응시킨다.**

:::{container} quotebox
**확인 10.** $A = \{x_1, x_2, x_3\}$이라 하자. 부분집합 $\{x_1, x_3\}$을 "각

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

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

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

:::{admonition} 답
:class: quotebox dropdown

(넣음, **뺌**, **넣음**) — $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에서 백지에 재현한다.

:::{container} quotebox
**확인 11.** 7주차 §1.6에서 명제 변수 $n$개짜리 진리표는 $2^n$행이라고 했다.

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

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

:::{admonition} 세기 답안의 서술 규범
:class: quotebox

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

를 먼저 선언한다.

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

확인한다.

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

§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주차) | 세기 답안의 인용 근거 — "곱셈 원리에 의해"가 이번 주의 표준 문구다 |

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

통과하는가?

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

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

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

등록 절차가 문제 12다.
:::