이 책에서의 이산수학( Discrete Mathematics )은 연속적이지 않은 수학적 구조를 뜻한다.
조합론
1. 부분집합의 개수 세기 (Counting subsets)
- 원소가 $ n $개인 집합의 모든 부분집합의 개수:
$$ 2^n $$
- 예제: $n = 3$
$$ 2^3 = 8 $$
→ 공집합부터 모든 원소를 포함하는 집합까지 총 $ 8 $개 존재
2. 이항 계수 (Binomial coefficient)와 조합 (Combination)
- 이항 계수:
$$ \binom{n}{k}=\frac{n!}{k!(n-k)!} $$
→ $ n $개의 원소 중에서 $ k $개를 선택하는 경우의 수
- 예제:
$$ \binom{5}{3}=\frac{5!}{3!(5-3)!}=10 $$
→ $ 5 $개의 원소 중에서 $ 3 $개를 선택하는 방법은 $ 10 $가지
3. 파스칼의 삼각형 (Pascal’s triangle)과 이항 정리 (Binomial theorem)
파스칼의 삼각형은 이항 계수의 재귀적 성질 을 이용해 생성
- 공식:
$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$
- 이항 정리:
$$ (x+y)^n=\sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k $$
→ 다항식 전개에서 중요한 역할
4. 중복을 허용한 경우의 수 (Counting with repetition)
- 원소를 중복 선택할 수 있는 경우:
$$ \binom{n+k-1}{k} $$
→ 중복 조합의 공식
- 예제: $3$ 종류의 동전에서 $ 4 $개 선택
$$ \binom{3+4-1}{4}=\binom{6}{4}=15 $$
→ $ 15 $가지 선택 가능