14주차 — 포함–배제의 원리 + 3부 총정리

14주차 — 포함–배제의 원리 + 3부 총정리#

이 주의 길잡이

핵심 문장: 두 번 센 것은 한 번 빼면 된다.

이 주의 위치: 50주 과정의 14주차. 3부(세기)의 마지막 주 — 덧셈 원리\(\cdot\)포함–배제\(\cdot\)여사건 세기를 더하고, 총정리 모의시험으로 12~14주차를 닫는다.

원서 대응: BoP(Book of Proof) 3.3, 3.7 — 병행자 참고용. 원서 없이 읽을 수 있다.

이번 주 목표#

  1. 덧셈 원리(서로소 분할이면 개수를 더한다)를 조건까지 포함해 진술하고 사용한다.

  2. \(|A \cup B| = |A| + |B| - |A \cap B|\)를 증명한다 — 고1 때 외운 \(n(A \cup B)\) 공식이자, 5주차 문제 13에서 수치로만 확인한 등식의 빚 회수다.

  3. 3집합 포함–배제와 여사건 세기(“적어도 하나”)를 사용한다.

  4. 3부(세기) 총정리 모의시험으로 12~14주차를 자가 평가한다.

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

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

  1. \(\binom{n}{k}\)의 정의와 공식을 쓰시오.

  2. 파스칼 공식을 쓰고, 세기 증명의 핵심(기준 인물 분할)을 한 문장으로 말하시오.

  3. \((x+y)^5\)의 \(x^2y^3\) 계수는?

답은 §6 해설 맨 앞에 있다. 채점까지 마친 뒤 본문으로 들어간다.

자주 나오는 세 가지 답#

채점 결과는 대개 다음 세 유형 중 하나로 갈린다. 셋 다 13주차 내용을 절반 이상 소화한 상태이고, 셋 다 이번 주 모의시험 전에 메워야 할 정확한 간격이 있다.

  • 유형 1 — 공식은 정확한데 세기 증명의 핵심이 안 나온다. \(1 \le k \le n-1\)이면

\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)까지는 적는다 — 조건까지 붙였으면 13주차 예제 2.2의 명제 그대로이고, 조건을 빠뜨렸으면 그 한 줄부터 보충한다. 공식 암기는 완료된 상태다. 간격은 우변의 두 항이 무엇을 세는지다 — 기준 인물(갑)의 포함/미포함으로 부분집합 전체를 겹침 없이 둘로 나눈 뒤 각각 세어 더한다는 논증. 그 “겹침 없이 나눠 더하기”를 정당화하는 원리가 이번 주의 덧셈 원리이고, 모의시험 문제 16이 이 증명의 백지 재현이다.

  • 유형 2 — 첨자가 어긋난다. \(\binom{n}{k} = \binom{n-1}{k} + \binom{n}{k-1}\)처럼

적는 경우가 많다. 파스칼 삼각형의 그림 기억에만 의존한 것이 원인이다 — 각 항이 세는 대상(갑 포함이면 남은 \(n-1\)명 중 \(k-1\)명, 갑 미포함이면 \(n-1\)명 중 \(k\)명)을 항 옆에 붙이면 첨자는 스스로 복원된다. 공식은 그림이 아니라 분할에서 나온다.

  • 유형 3 — 3번의 값은 맞는데 이유가 없다. 계수 10을 적고 끝낸다. 값은 옳다.

간격은 서술이다 — 12주차 서술 규범대로 “다섯 괄호에서 \(y\)를 고를 3곳을 선택하는 가짓수 \(\binom{5}{3}\)”이라는 한 줄이 있어야 채점 가능한 답이 된다. 이번 주 모의시험은 이 서술을 전 문항에서 요구한다.

개념 — 덧셈 원리, 포함–배제, 여사건#

1 곱셈 원리만으로 밀어붙이면 어디서 막히는가#

12주차 이후 세기의 도구는 곱셈 원리 하나였다. 이 도구로 다음 문제를 밀어붙여 보자.

시도 — 곱셈 원리로 밀어붙이기

문제: 미술반 12명, 음악반 15명(두 반에 겹치는 학생은 없다) 가운데 축제 대표

1명을 뽑는 가짓수는?

서술 규범대로 적어 보자: “대표 선출은 (1단계: \(\underline{\qquad}\), 2단계:

\(\underline{\qquad}\))의 길이 2 목록이고 …” — 여기서 멈춘다.

1단계와 2단계가 없다. 뽑는 사람은 한 명이고, 선택은 한 번뿐이다.

확인 1. 곱셈 원리의 적용 조건(12주차)은 무엇이었는가. 이 문제는 왜 그

조건에 들어맞지 않는가. 억지로 \(12 \times 15\)를 계산하면, 그 수는 실제로

무엇을 세는가?

답

곱셈 원리는 세기가 단계의 연속(길이 \(k\) 목록)으로 분해될 때 쓴다. 이

선택은 단계가 아니라 갈래다 — “미술반에서 뽑는 경우” 아니면 “음악반에서 뽑는

경우”. \(12 \times 15\)는 (미술반원, 음악반원) 쌍의 개수, 즉 **각 반에서

한 명씩** 두 명을 뽑는 다른 문제의 답이다(27명 중 아무 두 명을 뽑는 문제의 답

\(\binom{27}{2} = 351\)과도 다르다). 필요한 것은 단계를 잇는 원리가 아니라

경우끼리 개수를 결합하는 새 원리다.

2 경우로 쪼개 더하기 — 원리를 만들어 보기#

두 경우에 걸친 후보 전체는 집합의 언어로 \(A \cup B\)다 (\(A\) = 미술반, \(B\) = 음악반). 작은 사례부터 — 겹치지 않는 두 집합의 합집합을 직접 나열해 크기를 재 보자.

\(A\)

\(B\)

\(\lvert A \rvert\)

\(\lvert B \rvert\)

\(A \cup B\)의 나열

\(\lvert A \cup B \rvert\)

\(\{1, 2\}\)

\(\{5, 7, 9\}\)

2

3

\(1, 2, 5, 7, 9\)

5

\(\{a, b\}\)

\(\{c\}\)

2

1

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

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

미술반

음악반

12

15

두 명단을 이어 붙인 것

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

확인 2. 표의 빈칸 (1)(2)(3)을 채우고, 세 줄에 공통인 규칙을 등식 하나로

적어 보자.

답

(1) \(a, b, c\) (2) \(3\) (3) \(27\). 공통 규칙: \(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert\).

이유도 나열 안에 이미 있다 — 겹침이 없으므로 \(A\)의 나열 뒤에 \(B\)의 나열을

이어 붙인 것이 곧 \(A \cup B\)의 나열이고, 같은 원소가 두 번 등장하지도,

빠지지도 않는다. 개수는 그대로 합이다.

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 겹치지 않는 두 명단을 이어 붙이면 개수가 합이 된다는, 방금 표에서 한 관찰을 문장으로 굳혔을 뿐이다.

덧셈 원리 (Addition Principle) [백지 암기 대상]#

유한집합 \(A, B\)가 서로소(\(A \cap B = \emptyset\))이면 \(|A \cup B| = |A| + |B|\)이다.

일반화: \(A_1, \dots, A_k\)가 쌍마다 서로소이면 \(|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_k|\)이다.

두 집합 꼴의 근거는 확인 2의 이어 붙이기 논증으로 충분하다. \(k\)개 일반형은 이 논증을 반복해서 얻는데, 그 반복의 정당화는 31주차 귀납법에서 완결한다 — 지금은 인정하고 쓴다.

실은 이미 써 본 원리다. 13주차 파스칼 공식의 세기 증명에서 부분집합 전체를 “갑 포함/갑 미포함”으로 나눠 더할 때 “14주차에서 공식화한다”고 예고했던 바로 그것이고, 12주차 문제 20에서 설계한 “경우 나누기” 상황의 해답이다. 곱셈 원리는 “단계”로 쪼갤 때, 덧셈 원리는 “경우”로 쪼갤 때 쓴다.

확인 3. 다음 세 세기는 각각 단계로 쪼개는가(곱셈), 경우로 쪼개는가(덧셈).

(가) 대문자 1개 뒤에 숫자 1개를 붙인 코드의 가짓수

(나) 대문자 1개 또는 숫자 1개로 된 기호 하나의 가짓수

(다) \(\{1, \dots, 30\}\)에서 2의 배수 또는 3의 배수인 수의 개수

답

(가) 단계 — (문자, 숫자)의 길이 2 목록, 곱셈 원리로 \(26 \times 10 = 260\).

(나) 경우 — 대문자인 경우와 숫자인 경우. 대문자이면서 숫자인 기호는 없으므로

서로소이고, 덧셈 원리로 \(26 + 10 = 36\).

(다) 경우이긴 한데 — 2의 배수이면서 3의 배수인 수(6, 12, …)가 있어 두 경우가

서로소가 아니다. 덧셈 원리의 조건이 무너지는 이 상황이 §1.4의 주제다.

3 원리 해부 — 조각마다 하는 일#

조각

하는 일

세기(증명)에서의 역할

“유한집합 \(A, B\)”

대상의 제한

크기 \(\lvert \cdot \rvert\)가 개수로 확정되는 무대다 — 무한집합의 크기 비교는 48~49주차의 주제다

“서로소 (\(A \cap B = \emptyset\))”

적용 조건

이 조각이 무너지면 이중 세기가 생긴다 (아래 실험)

“\(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert\)”

결론 등식

큰 세기 하나를 작은 세기 두 개로 분해한다 — 파스칼 증명이 이 분해였다

“쌍마다 서로소”

일반화의 조건

셋 이상일 때는 모든 쌍이 겹치지 않아야 이어 붙이기가 반복된다

조각 삭제 실험. 둘째 조각 “서로소”를 지우고 원리를 확인 3의 (다)에 적용해 보자. \(U = \{1, \dots, 30\}\)에서 \(A\) = 2의 배수 집합(15개), \(B\) = 3의 배수 집합(10개)이므로 \(15 + 10 = 25\)개 — 라고 주장하게 된다.

확인 4. \(A \cup B\)를 실제로 나열해 개수를 세어 보자. 25개가 맞는가?

답

\(2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 26, 27, 28, 30\) —

20개다. \(25 \neq 20\) — “서로소” 조각을 지우는 순간 등식이 실제 개수보다

5만큼 크게 어긋난다. 조건은 장식이 아니라 등식을 지키는 조각이다.

어긋난 5가 정확히 어디서 왔는지는 다음 절에서 원소 단위로 추적한다.

4 겹치면 그냥 더할 수 없다 — 초과분의 정체#

\(15 + 10 = 25\)가 실제 20보다 커진 이유를 원소의 입장에서 본다. \(15 + 10\)이라는 계산은 \(A\)의 명단과 \(B\)의 명단을 그대로 이어 붙여 센 것이다 — 원소 하나하나가 이 계산에서 몇 번 세어지는지 표로 추적해 보자.

원소

\(A\)의 명단에서

\(B\)의 명단에서

\(15 + 10\)에서 세어진 횟수

\(4\) (2의 배수만)

1번

0번

1번

\(9\) (3의 배수만)

0번

1번

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

\(6\) (2와 3의 배수)

1번

1번

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

\(7\) (어느 쪽도 아님)

0번

0번

0번

확인 5. 표의 빈칸 (1)(2)를 채우고, “초과분 5”의 정체를 집합의 언어로

지목해 보자.

답

(1) \(1\) (2) \(2\). 두 번 세어지는 원소는 정확히 양쪽 명단에 다 있는 원소,

곧 \(A \cap B\)의 원소들이다. 여기서는 6의 배수 \(6, 12, 18, 24, 30\)의 5개 —

초과분 5는 바로 \(\lvert A \cap B \rvert\)다. 그러므로 각 원소를 정확히 한 번씩만

세려면 두 번 센 만큼을 한 번 빼면 된다: \(25 - 5 = 20\) ✓.

이 조정에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 두 번 센 만큼(\(|A \cap B|\))을 한 번 뺐을 뿐이다.

포함–배제 원리 (Inclusion–Exclusion) [백지 암기 대상]#

유한집합 \(A, B\)에 대해

\[ |A \cup B| = |A| + |B| - |A \cap B| \]

유한집합 \(A, B, C\)에 대해

\[ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C| \]

고1 때 외운 \(n(A \cup B)\) 공식이 이것이다. 이번 주에는 외우는 대신 증명한다 — 예제 2.1에서 덧셈 원리 두 번으로 만들고, 문제 11에서 백지에 재현한다.

3집합 버전의 리듬: 홀수 개짜리 교집합은 더하고(\(+\)), 짝수 개짜리 교집합은 뺀다(\(-\)). 목적은 하나다 — 각 원소가 정확히 한 번씩 세어지도록 조정하는 것. (3집합 식은 예제 2.1을 두 번 적용하고 분배법칙 \(C \cap (A \cup B) = (C \cap A) \cup (C \cap B)\) (7주차 예제에서 진리표로 확정)을 쓰면 이번 주 도구만으로도 유도된다 — 여기서는 원소 세기 관찰(확인 6)로 납득하고 넘어가고, 임의의 \(n\)집합 일반형은 31주차 귀납법 이후에 완결한다.)

확인 6. 3집합 식의 우변에서, 다음 두 원소가 각각 몇 번 세어지는지 항별로

추적해 보자.

(가) 세 집합 모두에 속하는 원소 (나) \(A\)와 \(B\)에만 속하고 \(C\)에는 없는 원소

답

(가) \(|A| + |B| + |C|\)에서 \(3\)번, 쌍 교집합 세 개를 빼며 \(-3\)번, 삼중 교집합에서

\(+1\)번 — 합계 \(3 - 3 + 1 = 1\)번.

(나) 단일 항에서 \(2\)번(\(A\), \(B\)), 쌍 교집합에서는 \(A \cap B\) 하나에만 속하므로

\(-1\)번, 삼중 교집합에는 없으므로 \(0\)번 — 합계 \(2 - 1 = 1\)번.

어느 부류의 원소든 정확히 한 번 — 부호의 리듬은 이 “정확히 한 번”을 맞추기

위한 조정이다.

5 배수는 몇 개인가 — 바닥 기호#

포함–배제를 배수 세기에 쓰려면 “\(1\)부터 \(N\)까지 중 \(d\)의 배수의 개수”가 재료다. 새 기호 하나를 들인다 — \(\lfloor x \rfloor\)는 “\(x\)의 바닥”으로 읽고, \(x\)를 넘지 않는 가장 큰 정수를 뜻한다. 예: \(\lfloor 3.7 \rfloor = 3\), \(\lfloor 5 \rfloor = 5\).

사실. \(1\)부터 \(N\)까지의 자연수 중 \(d\)의 배수는 \(\lfloor N/d \rfloor\)개다. 이유 — 그 배수들은 \(d \cdot 1, d \cdot 2, \dots, d \cdot k\) (\(d \cdot k \le N\)인 가장 큰 \(k\))로 나열되고, 그 \(k\)가 바로 \(N\)을 \(d\)로 나눈 몫 \(\lfloor N/d \rfloor\)다.

확인 7. \(1\)부터 \(100\)까지 중 \(7\)의 배수는 몇 개인가. 바닥 기호로 적고,

마지막 배수가 무엇인지로 검산해 보자.

답

\(\lfloor 100/7 \rfloor = 14\)개. 검산 — 마지막 배수는 \(7 \times 14 = 98 \le 100\)이고

다음 배수 \(7 \times 15 = 105\)는 100을 넘는다 ✓. §1.3의 삭제 실험에서 쓴

“2의 배수 15개”도 같은 계산 \(\lfloor 30/2 \rfloor = 15\)였다.

6 “적어도 하나”는 뒤집어 센다#

포함–배제가 “또는”의 세기라면, 이번에는 “적어도 하나”의 세기다. 정면으로 밀어붙이면 비용이 어떻게 되는지부터 본다.

시도 — 정면 돌파

문제: 3자리 비밀번호(각 자리 0~9) 중 숫자 0을 적어도 하나 포함하는 것은 몇 개인가?

“적어도 하나”이므로 0의 개수로 경우를 나눈다 — 0이 정확히 1개:

자리 선택 \(\binom{3}{1} = 3\), 나머지 두 자리 \(9^2\)가지로 \(3 \times 81 = 243\)개.

정확히 2개: \(\binom{3}{2} \times 9 = 27\)개. 정확히 3개: \(1\)개.

세 경우는 서로소이고 전체를 덮으므로 덧셈 원리로 \(243 + 27 + 1 = 271\)개.

답은 나왔다 — 그러나 경우 세 개마다 곱셈 원리 계산이 하나씩 필요했고, 자리가 5개, 10개로 늘면 경우도 그만큼 늘어난다. 방향을 바꿔 보자. 11주차 부정 규칙 — “적어도 하나(\(\exists\))”의 부정은 “전부 아님(\(\forall\neg\))” — 이 세기 전략이 되는 지점이다(12주차 문제 15에서 먼저 맛본 전환이다).

확인 8. “0을 적어도 하나 포함한다”의 부정을 11주차 규칙으로 문장으로 적고,

그 부정에 해당하는 비밀번호의 개수를 곱셈 원리로 계산해 보자.

답

부정: “어느 자리에도 0이 없다” — 모든 자리가 0이 아니다. 각 자리의 후보가

1~9의 9가지인 길이 3 목록이므로 곱셈 원리로 \(9^3 = 729\)개. 전체 \(10^3 = 1000\)개에서

빼면 \(1000 - 729 = 271\)개 — 정면 돌파의 결과와 일치한다. 경우 세 개가 뺄셈

한 번으로 줄었다.

여사건 세기 (complementary counting) [백지 암기 대상]#

유한집합 \(U\)와 \(A \subseteq U\)에 대해 \(|A| = |U| - |A^c|\)이다.

‘빼기 원리’라고도 부른다. “적어도 하나 ~”는 정면 돌파가 번거롭고, 그 부정(“하나도 ~ 아님”)은 곱셈 원리 한 번으로 끝날 때가 많다. 부정을 세서 전체에서 빼는 이 전략이 여사건 세기다.

확인 9. 이 공식은 외울 것이 아니라 유도할 것이다 — 덧셈 원리에서 두 줄로

나온다. \(U\)를 어떤 서로소 조각으로 나누면 되는지부터 시작해 유도 전체를 적어 보자.

답

\(U\)의 임의의 원소는 \(A\)에 속하거나 속하지 않거나 — 정확히 한쪽이다. 따라서

\(U = A \cup A^c\)이고 \(A \cap A^c = \emptyset\) (5주차 여집합의 정의). \(U\)가

유한집합이므로 조각 \(A\), \(A^c\)도 유한집합이고, 서로소인 두 유한집합에 덧셈

원리를 적용하면 \(|U| = |A| + |A^c|\)이고, 이항하면(근거 ③) \(|A| = |U| - |A^c|\)이다. \(\blacksquare\)

여사건 공식은 덧셈 원리의 두 줄짜리 따름 명제다 — 유도했으므로 오늘부터

근거 ④로 인용해 쓴다.

7 근거 목록 갱신 — 칸은 그대로 네 개#

칸은 그대로 네 개다. 이번 주에 새 정의는 바닥 기호 하나뿐이고(§1.5), 세 원리는 전부 “이미 증명했거나 논증한 명제”로서 ④ 칸에 들어간다.

근거

내용

이번 주에는 이렇게 쓴다

① 정의

바닥 기호 \(\lfloor x \rfloor\)(§1.5) 추가 (목록\(\cdot\)팩토리얼 12주차, 조합 13주차)

“적어도 하나 포함하는 비밀번호”를 집합 \(A \subseteq U\)로 번역하고, \(\lfloor N/d \rfloor\)를 배수의 개수로 번역한다

② 닫힘성

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

이번 주에는 등장이 적다

③ 등식의 성질

대입 / 이항 / 묶기

\(\lvert A - B \rvert\)를 이항으로 표현하고(예제 2.1의 (ii)), (ii)를 (i)에 대입한다

④ 이미 증명한 명제

덧셈 원리(두 집합은 §1.2의 이어 붙이기 논증, 일반형은 31주차까지 인정), 포함–배제 2집합(예제 2.1에서 증명), 3집합(원소 세기 관찰로 납득 — 예제 2.1을 두 번 적용하고 분배법칙을 쓰면 유도된다), 여사건 공식(확인 9에서 유도), 배수 세기 \(\lfloor N/d \rfloor\)(§1.5), 공배수 = 최소공배수의 배수(5주차 문제 9의 관찰 — 20주차에서 증명, 지금은 인정하고 쓴다), 곱셈 원리\(\cdot\)조합\(\cdot\)이항정리(12~13주차)

세기 답안의 인용 근거 — “덧셈 원리에 의해”, “포함–배제에 의해”가 이번 주의 표준 문구다

확인 10. 어떤 답안에 다음 세 근거 문장이 나왔다. 각각 근거 목록을 통과하는가?

(가) “2와 5의 공배수는 10의 배수이므로 \(\lfloor 100/10 \rfloor = 10\)개”

(나) “\(n(A \cup B)\) 공식은 고등학교에서 배웠으므로”

(다) “포함–배제(예제 2.1에서 증명)에 의해”

답

(가) 통과 — “2와 5의 공배수 = 10의 배수”(근거 ④의 공배수 관찰 — 20주차에서

증명, 지금은 인정)와 배수 세기 사실(근거 ④)의 결합 적용이다.

(나) 불통과 — “학교에서 배웠다”는 목록 밖의 권위다. 식 자체는 옳지만, 이

교재 안에서는 예제 2.1의 증명이 그 식의 근거이고 그렇게 인용해야 한다.

(다) 통과 — 같은 식을 근거 ④의 형식으로 바르게 인용한 것이다. (나)와 (다)의

차이가 곧 “외운 공식”과 “증명한 명제”의 차이다.