Advanced Counting Techniques

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 7

Intuition

복잡한 계수 문제는 한 번에 해결하려 하기보다, 문제를 더 작은 단위로 쪼개어 관계를 설정하거나(점화식), 수열을 함수에 담아 조작하거나(생성함수), 중복된 부분을 체계적으로 가감하여(포함-배제) 해결할 수 있다.

One-liner

다양한 제약 조건이 있는 계수 문제를 해결하기 위해 점화식의 모델링 및 풀이, 분할 정복 알고리즘 분석, 생성함수의 활용, 포함-배제의 원리를 체계적으로 학습한다.

Prerequisites

이 챕터를 이해하기 위해 다음의 배경지식이 필요하다.

• 조합론 기초 (Ch. 5): 순열, 조합, 중복 조합에 대한 명확한 이해.
• 수열과 급수: 등비수열의 합 공식 및 기본적인 무한급수의 성질 (Ch. 2).
• 수학적 귀납법 (Ch. 4): 점화식의 해가 유효함을 증명하기 위한 도구.

Goals

• 실생활 문제를 점화식으로 모델링하고 특성 방정식을 이용해 일반항을 도출할 수 있다.
• 분할 정복 알고리즘의 수행 시간을 마스터 정리를 사용하여 추정할 수 있다.
• 수열의 정보를 담은 생성함수를 구축하고 이를 이용해 계수 문제를 해결할 수 있다.
• 여러 집합의 합집합의 크기를 포함-배제의 원리를 통해 계산할 수 있다.

Core Concepts

1. 점화식과 모델링 (7.1)

Definition

Recurrence Relation (점화식): 수열 $\{a_n\}$에 대한 점화식은 $a_n$을 하나 이상의 앞선 항들($a_0, a_1, \dots, a_{n-1}$)을 이용해 표현하는 방정식이다. (p.450)

• Initial Conditions (초기 조건): 점화식이 적용되기 시작하는 시점 이전의 항들을 명시한 것이며, 점화식과 함께 수열을 유일하게 결정한다. (p.450)
• Fibonacci Numbers (피보나치 수): 토끼 번식 모델 등을 통해 도출되며, $f_n = f_{n-1} + f_{n-2}$ 관계를 갖는다. (p.451)
• Tower of Hanoi (하노이의 탑): $n$개의 원판을 옮기는 최소 이동 횟수 $H_n = 2H_{n-1} + 1$로 모델링된다. (p.453)

2. 선형 점화식의 해법 (7.2)

Definition

Linear Homogeneous Recurrence Relation (선형 동차 점화식): 상수 계수 $c_i$를 가지며 $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ 형태인 점화식이다. (p.460)

• Characteristic Equation (특성 방정식): 점화식의 해를 $a_n = r^n$으로 가정하여 유도한 다항 방정식이다. (p.461)
• Nonhomogeneous Relation (비동차 점화식): $a_n = (\text{동차항}) + F(n)$ 형태이며, 일반해는 '동차 점화식의 해'와 '비동차의 특수해'의 합으로 구성된다. (p.467)

3. 분할 정복 알고리즘 (7.3)

Definition

Divide-and-Conquer Recurrence (분할 정복 점화식): 문제를 크기가 $n/b$인 $a$개의 하위 문제로 나누고 이를 결합하는 데 $g(n)$의 연산이 필요한 경우, $f(n) = a f(n/b) + g(n)$으로 표현한다. (p.474)

• Binary Search (이진 탐색): $f(n) = f(n/2) + 2$의 관계를 가지며 시간 복잡도는 $O(\log n)$이다. (p.478)

4. 생성함수 (7.4)

Definition

Generating Function (생성함수): 수열 $a_0, a_1, \dots$에 대하여, 각 항을 $x^k$의 계수로 사용하는 무한 급수 $G(x) = \sum_{k=0}^{\infty} a_k x^k$이다. (p.484)

• 생성함수는 수열의 정보를 '함수'의 형태로 압축하여, 다항식의 곱셈을 통해 조합론적 문제를 해결할 수 있게 한다. (p.488)

5. 포함-배제의 원리 (7.5 & 7.6)

Definition

Principle of Inclusion-Exclusion (포함-배제의 원리): 유한 집합 $A_1, A_2, \dots, A_n$의 합집합의 크기는 각 집합의 크기 합에서 교집합의 크기를 교대로 빼고 더하여 구한다. (p.503)

$$|A_1 \cup \dots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \dots + (-1)^{n+1} |A_1 \cap \dots \cap A_n|$$

• Derangement (교란순열): 어떤 원소도 원래 자기 자리에 있지 않은 순열을 의미하며, 포함-배제의 원리로 개수를 구할 수 있다. (p.510)

Notation

기호	의미
$f_n$	$n$번째 피보나치 수
$H_n$	$n$개의 원판에 대한 하노이의 탑 이동 횟수
$C(n, k)$	$n$개 중 $k$개를 택하는 조합의 수
$D_n$	$n$개 원소의 교란순열 개수
$G(x)$	수열 $\{a_n\}$의 생성함수

Key Theorems & Formulas

Theorem (Linear Homogeneous Recurrence of Degree 2)

조건: 점화식 $a_n = c_1 a_{n-1} + c_2 a_{n-2}$의 특성 방정식 $r^2 - c_1 r - c_2 = 0$이 서로 다른 두 실근 $r_1, r_2$를 가질 때.

결론: 일반해는 $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$이다. ($\alpha_i$는 초기 조건으로 결정) (p.462)

Theorem (The Master Theorem)

조건: 증가함수 $f$가 $f(n) = a f(n/b) + c n^d$를 만족할 때. ($a \ge 1, b > 1, c > 0, d \ge 0$)

결론:

1. $a < b^d \implies f(n) = O(n^d)$
2. $a = b^d \implies f(n) = O(n^d \log n)$
3. $a > b^d \implies f(n) = O(n^{\log_b a})$ (p.479)

Theorem (Number of Derangements)

조건: $n$개 원소의 집합에 대하여.

결론:

$$D_n = n! \left[ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!} \right]$$

(p.510)

Intuitions

• 점화식의 직관: "미래의 상태($a_n$)는 과거의 상태($a_{n-1}, \dots$)들의 규칙적인 조합으로 결정된다." 이는 동적 계획법(Dynamic Programming)의 핵심 원리와 같다.
• 생성함수의 직관: "수열은 내용물이고, 함수는 가방이다." 가방(함수)을 조작(곱셈, 미분 등)하면 가방 안의 내용물(수열의 항)이 우리가 원하는 계수 규칙에 맞춰 자동으로 재배열된다.
• 포함-배제의 직관: "중복 계산된 부분을 한 번 걷어내면 너무 많이 걷어내게 되므로, 다시 그 안의 중복을 더해주는 과정을 반복하여 정확한 경계를 찾는 과정이다."

Worked Examples

Example 1: 특성 방정식을 이용한 점화식 풀이

문제: $a_n = a_{n-1} + 2a_{n-2}$ 이고 $a_0 = 2, a_1 = 7$인 수열의 일반항을 구하라.

핵심 단계:

1. 특성 방정식 $r^2 - r - 2 = 0$을 세운다.
2. 근을 구하면 $(r-2)(r+1)=0$ 이므로 $r_1=2, r_2=-1$이다.
3. 일반해 $a_n = \alpha_1 2^n + \alpha_2 (-1)^n$에 초기 조건을 대입한다.
   • $n=0: \alpha_1 + \alpha_2 = 2$
   • $n=1: 2\alpha_1 - \alpha_2 = 7$
4. 연립 방정식을 풀면 $\alpha_1=3, \alpha_2=-1$이다.

요점: 일반항은 $a_n = 3 \cdot 2^n - (-1)^n$ 이다. (p.463)

Example 2: 생성함수를 이용한 조합 문제

문제: $e_1 + e_2 + e_3 = 17$을 만족하는 정수해의 개수를 구하라. (단, $2 \le e_1 \le 5, 3 \le e_2 \le 6, 4 \le e_3 \le 7$)

핵심 단계:

1. 각 변수의 제약 조건을 생성함수의 다항식으로 변환한다.
   • $G(x) = (x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)$
2. $G(x)$를 전개하여 $x^{17}$의 계수를 찾는다.

요점: 다항식의 곱셈에서 지수의 합이 17이 되는 경우의 수가 곧 방정식의 해의 개수이다. (p.489)

Common Pitfalls

Pitfall

중근을 갖는 점화식: 특성 방정식이 중근 $r_0$를 가질 때, 일반해를 단순히 $a_n = \alpha r_0^n$으로 생각하면 안 된다. 이 경우 항이 부족하여 초기 조건을 모두 만족시킬 수 없으므로, 두 번째 해로 $n r_0^n$을 도입하여 $a_n = \alpha_1 r_0^n + \alpha_2 n r_0^n$으로 풀어야 한다. (p.464)

Pitfall

비동차 점화식의 특수해 선택: 비동차항 $F(n) = s^n$일 때, $s$가 이미 동차 점화식의 근이라면 특수해를 $C s^n$으로 설정하면 안 된다. $s$가 중복되는 횟수 $m$만큼 $n^m$을 곱한 형태($C n^m s^n$)를 특수해로 잡아야 한다. (p.469)

Connections

• 선행 개념: Ch. 5 조합론 기초 (조합의 수 계산), Ch. 3 행렬 (점화식의 행렬 표현과 고윳값), Ch. 4 수학적 귀납법 (재귀적 정의).
• 후속 개념: Ch. 3 알고리즘 분석 (분할 정복의 복잡도 계산), Ch. 6 확률론 (확률 생성 함수).
• 동일 개념의 다른 표현: 점화식은 컴퓨터 과학에서 Recursive Relation 또는 Difference Equation으로도 불린다.

Critical Notes

교재가 강조하는 것

• 다양한 실생활 문제(금융 이자, 생물학적 인구 증가, 퍼즐)를 수학적 점화식으로 추상화하는 능력.
• 생성함수를 '공식적인 멱급수(formal power series)'로 취급하여 수렴 여부에 구애받지 않고 조합론적 도구로 사용하는 유연성.

실제로 중요한 것

• 마스터 정리 (Theorem 2 in 7.3): 실무적인 알고리즘 효율성 분석에서 가장 빈번하게 사용되는 도구다.
• 포함-배제의 일반화: 단순히 집합의 크기를 구하는 것을 넘어, '정확히 $k$개의 성질을 가진 원소의 개수'를 구하는 등의 확장이 중요하다.

교재가 생략하거나 얼버무리는 것

• 일반적인 차수($k \ge 3$) 점화식의 근이 복소수일 경우의 처리 방식은 구체적으로 다루지 않고 연습문제로 넘긴다. (p.462)
• 생성함수의 해석적 성질(수렴 반경 등)은 조합론적 관점에서 중요하지 않다고 간주하여 설명을 생략한다. (p.485)

Open Questions

• 이해하지 못한 것: 생성함수에서 미분을 이용해 새로운 수열의 합 공식을 유도하는 과정이 미적분학적 엄밀성 없이 어떻게 정당화되는지 더 공부할 필요가 있음.
• 더 알고 싶은 것: 지수 생성함수(Exponential Generating Function)가 순열 문제에서 어떻게 일반 생성함수보다 효율적으로 작동하는지에 대한 구체적인 메커니즘.