이산수학은 연속적인 양이 아니라 하나, 둘, 셋처럼 떨어져 있는 대상을 다룬다. 경우의 수를 세는 조합론, 점과 선의 연결을 다루는 그래프 이론, 컴퓨터 알고리즘의 바탕이 되는 논리와 점화식이 여기에 속한다. 컴퓨터 과학과 가장 가까운 수학 분야이다.
무엇을 배우나요
세는 방법
합의 법칙과 곱의 법칙, 순열과 조합, 중복조합 ${}_nH_r=\binom{n+r-1}{r}$을 익힌다. 겹치는 경우를 빼고 더하는 포함-배제의 원리도 중요하다.
$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|$$
이항정리와 파스칼 삼각형
$$(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k, \qquad \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$$
점화식과 생성함수
피보나치 수열 $F_{n+2}=F_{n+1}+F_n$처럼 앞의 항으로 다음 항을 정하는 식을 풀고, 수열을 다항식(멱급수)의 계수로 담아 다루는 생성함수를 배운다.
그래프 이론
꼭짓점과 변으로 이루어진 그래프에서 경로, 연결성, 트리, 오일러 회로, 해밀턴 회로, 색칠 문제를 다룬다. 모든 그래프에서 차수의 합은 변 개수의 두 배이다.
$$\sum_{v\in V}\deg(v)=2|E|$$
대표 정리
- 비둘기집 원리: $n+1$개의 물건을 $n$개의 상자에 넣으면 적어도 한 상자에는 두 개 이상이 들어간다.
- 오일러의 한붓그리기 정리: 연결 그래프가 모든 변을 한 번씩 지나 제자리로 돌아오는 회로를 가질 필요충분조건은 모든 꼭짓점의 차수가 짝수인 것이다.
- 평면 그래프의 오일러 공식: $V-E+F=2$
선수 지식
중등 경우의 수. 수학기초론의 논리와 수학적 귀납법을 함께 익히면 좋다.
학습 로드맵
- 경우의 수 → 순열과 조합 → 중복조합과 분할
- 이항정리 → 포함-배제 원리 → 비둘기집 원리
- 점화식 → 생성함수
- 그래프의 기초 → 트리 → 회로와 경로 → 그래프 색칠
