안내
읽기 경로
논리 → 집합 → 셈 → 그래프로 가는 길
읽음 0/0
갱신 2026-08-09
16개 장을 어떤 순서로, 무엇을 기대하며 읽을지 안내한다. 큰 그림은 전체 조망에, 각 재료의 출처와 수준은 원전 소개에 있다. 기본 원칙은 하나 — 모든 정리는 작은 예에서 직접 세어 보고 시작한다. $n=3$, $n=4$에서 손으로 세어 본 다음 일반 증명을 읽으면, 증명은 낯선 기호가 아니라 이미 관찰한 패턴의 설명이 된다.
경로
I. 논리 — 증명의 문법
- 명제논리 — 명제, 논리 연산, 진리표, 동치. 이후 모든 장의 문장을 읽는 규칙이 여기서 정해진다.
- 술어와 한정기호 — $\forall$와 $\exists$, 부정 규칙, 다중 한정. "모든 $\varepsilon$에 대해 어떤 $\delta$가 존재한다" 류의 문장을 기계적으로 부정할 수 있게 된다.
II. 증명법 — 수학이 말하는 방식
III. 집합과 관계 — 이산 구조의 재료
- 집합과 함수 — 집합 연산, 함수, 단사·전사·역함수. "세기"의 기초 언어: 전단사가 곧 개수의 일치다.
- 관계와 동치관계 — 관계의 성질, 동치류와 분할, 부분순서. 동치관계 = 분할이라는 대응이 핵심 수확이다.
- 집합의 크기 — 가산과 비가산, 대각선 논법. 무한집합에도 크기의 등급이 있음을 처음 만나는 장으로, 코스에서 가장 추상적인 지점이다.
IV. 조합론 — 세는 기술
- 셈의 기본 원리 — 곱·합의 법칙, 비둘기집 원리. 단순하지만 이후 모든 세기 논증의 뼈대다.
- 순열과 조합 — 이항계수, 이항정리, 조합적 증명. 같은 항등식을 대수로도, "양쪽에서 같은 것을 센다"로도 증명하는 이중 관점을 익힌다.
- 포함–배제의 원리 — 합집합 세기, 교란순열. "적어도 하나"를 셀 때의 표준 도구.
- 점화식 — 선형 점화식의 해법, 하노이 탑, 피보나치. 직접 세기 어려운 대상을 자기 자신으로 환원하는 기술.
V. 생성함수 — 수열을 함수로 압축한다
- 생성함수 — 형식적 멱급수로 세기, 분할과 카탈란 수. IV부의 도구들이 하나의 통일된 계산법으로 합쳐진다. 수열 $(a_n)$을 $\sum a_n x^n$으로 바꾸면 점화식이 대수 방정식이 된다.
VI. 그래프 이론 — 점과 선의 수학
- 그래프와 트리 — 그래프의 기초, 트리의 특성화. "$n$개 꼭짓점 트리는 간선이 $n-1$개"의 여러 얼굴을 배운다.
- 평면그래프 — 오일러 공식 $V-E+F=2$, $K_5$와 $K_{3,3}$. 세기 논증(간선 개수 상한)으로 기하적 결론(그릴 수 없음)을 얻는 전형.
- 그래프 채색 — 채색수, 그리디 채색, 4색 정리. 탐욕적 알고리즘과 구조적 하계 사이의 긴장을 본다.
- 매칭과 홀의 정리 — 이분 매칭, 홀의 결혼 정리. "언제 완전 매칭이 존재하는가"에 대한 깔끔한 필요충분조건.
VII. 확률적 방법 — 무작위로 존재를 증명한다
- 확률적 방법 — 기대값 논법, 램지 수 하계. 코스 전체의 종합: 세기(기대값 계산)로 구조(좋은 그래프의 존재)를 증명한다.
관통하는 주제 — 세기와 구조
코스를 관통하는 축은 두 개다. 하나는 세기(counting) — "몇 개인가"를 정확히 답하는 기술이고, 다른 하나는 구조(structure) — "어떤 모양이 가능한가"를 판정하는 기술이다. 두 축은 번갈아 주도권을 잡는다.
| 구간 | 세기 | 구조 |
|---|---|---|
| I–II부 | — | 증명이라는 구조 자체를 세운다 |
| III부 | 전단사 = 개수 일치, 가산성 | 동치류, 분할, 부분순서 |
| IV–V부 | 이항계수, 포함–배제, 생성함수 | 점화식이 드러내는 재귀 구조 |
| VI부 | 이중 세기, $V-E+F=2$ | 트리·평면성·채색·매칭의 특성화 |
| VII부 | 기대값 계산 | 존재성 증명 — 두 축의 합류 |
같은 정리를 두 축에서 다시 읽는 습관을 권한다. 예컨대 홀의 정리(매칭과 홀의 정리)는 구조 정리지만 증명은 세기 논증이고, 교란순열(포함–배제의 원리)은 세기 문제지만 답 $n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$은 구조(고정점 없음)의 반영이다.
학습 팁
- 손으로 센다. 정리를 읽기 전에 $n=3,4$에서 표를 만들어 직접 센다. 이항계수·교란순열·트리 개수 모두 작은 경우가 전부를 가르쳐 준다.
- 비중이 큰 장에 시간을 배분한다. 증명 기법, 관계와 동치관계, 순열과 조합, 포함–배제의 원리, 점화식, 그래프와 트리, 평면그래프, 매칭과 홀의 정리은 분량과 난도가 크다 — 하루에 끝내려 하지 말 것.
- 복습 지점을 지킨다. 집합의 크기를 마친 뒤(III부 끝)와 생성함수를 마친 뒤(V부 끝)에 멈춰서 앞을 정리하는 것이 좋다. 두 장은 각각 그 파트의 추상도가 정점에 이르는 곳이다.
- 조합적 증명을 우선한다. 대수적 유도로 항등식을 확인했더라도, "양변이 같은 집합을 센다"는 이야기로 다시 증명해 본다. 조합적 증명이 되는 순간 그 항등식은 잊히지 않는다.
- 그래프는 그린다. VI부에서는 모든 정의·정리마다 꼭짓점 5–6개짜리 예를 직접 그려 확인한다. 반례 후보를 그려 보는 것이 정리의 가정을 이해하는 가장 빠른 길이다.