0. 개요
경우의 수를 셀 때, 합의 법칙과 곱의 법칙을 매번 손으로 따지는 대신 생성함수라는 도구를 이용하면 다항식(혹은 급수)의 곱셈과 덧셈만으로 문제를 훨씬 체계적으로 풀어낼 수 있다.
이 글에서는 먼저 생성함수의 정의와 활용 예제를 살펴본 뒤, 생성함수의 대표적인 응용 사례인 카탈란 수를 기하학적 증명과 생성함수적 증명 두 가지 방법으로 유도하고, 마지막으로 카탈란 수와 일대일 대응되는 다섯 가지 조합론적 상황을 정리한다.
1. 생성함수 (Generating function)
- 정의
수열 $a_n$의 생성함수 $f(x)$를 다음과 같이 정의한다.
$$ f(x)=\sum_{n=0}^{\infty}a_nx^n =a_0+a_1x+a_2x^2+\cdots $$
- $a_n$ : 특정 조건을 만족하는 경우의 수
- $x^n$ : 특정 조건(예: 개수, 점수 등)을 나타내는 형식적 기호
경우의 수를 셀 때 쓰는 합의 법칙과 곱의 법칙은 각각 생성함수의 덧셈과 곱셈으로 표현할 수 있다. 즉 문제의 조건과 생성함수의 항 사이에 1:1 대응 관계를 만들어 놓으면, 이후로는 다항식 계산만으로 경우의 수를 구할 수 있다.
예제 1. 양궁판을 두 번 쏘는 경우
1점짜리 칸이 3개, 2점짜리 칸이 5개, 3점짜리 칸이 2개인 양궁판에 화살을 연달아 두 번 쏘았을 때 4점을 획득하는 경우의 수를 구해보자. (단, 칸은 전부 다른 것으로 취급)
한 번 쏘았을 때의 생성함수를 $f(x)=3x+5x^2+2x^3$라 하면, 두 번 쏘는 것은 곱의 법칙에 대응되므로
$$ f(x)^2 = (3x+5x^2+2x^3)(3x+5x^2+2x^3) $$
$$ = 9x^2+30x^3+37x^4+20x^5+4x^6 $$
$x^4$의 계수가 4점을 얻는 경우의 수이므로 답 : 37
예제 2. 과일을 20개 뽑는 경우
사과의 개수는 짝수, 바나나의 개수는 5의 배수, 오렌지의 개수는 최대 4개, 배의 개수는 0 또는 1개라는 조건 아래 과일을 총 20개 뽑는 경우의 수를 구해보자. (같은 종류의 과일은 같은 것으로 취급)
각 과일별 생성함수를 곱의 법칙으로 결합하면
$$ (1+x^2+x^4+\cdots) (1+x^5+x^{10}+\cdots) (1+x+x^2+x^3+x^4) (1+x) $$
무한등비급수 합 공식을 이용해 각 항을 정리하면
$$ \frac{1}{1-x^2} \times \frac{1}{1-x^5} \times \frac{1-x^5}{1-x} \times (1+x) $$
$$ = \frac{1}{(1-x)^2} $$
이를 미분하면
$$ \frac{1}{(1-x)^2} = \frac{d}{dx} \left( \frac{1}{1-x} \right) $$
$$ = \frac{d}{dx} (1+x+x^2+\cdots) $$
$$ = 1+2x+3x^2+\cdots = \sum_{n=0}^{\infty}(n+1)x^n $$
따라서 $a_{20}=21$, 답 : 21
- 무한등비급수 합 공식
$$ \sum_{n=0}^{\infty}r^n = \frac{1}{1-r} $$
2. 카탈란 수 (Catalan number)
- 정의
$C_n$ : $(0,0)$에서 $(n,n)$까지 이동할 때, 이동 경로 위의 모든 점에서 x좌표가 y좌표보다 항상 크거나 같도록 이동하는 경우의 수
- 일반 공식
$$ C_n = \frac{1}{n+1} \binom{2n}{n} $$
- 순환(점화) 공식
$$ C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k} $$
$$ = C_0C_{n-1} + C_1C_{n-2} + \cdots + C_{n-1}C_0 $$
이는 경로가 하나의 기준점을 지나면서 두 부분으로 나누어지고, 각각의 부분을 만드는 경우의 수가 $C_k$와 $C_{n-1-k}$가 된다는 사실에서 나온다.
2-1. 카탈란 수의 기하학적 증명
$(0,0)$에서 $(n,n)$까지 가는 전체 경로 중, $x\ge y$ 조건을 만족하지 않는(즉 한 번이라도 $y>x$가 되는) 경로를 세는 것이 핵심이다.
오른쪽으로 $n$번, 위쪽으로 $n$번 이동해야 하므로 전체 경로의 수는
$$ \binom{2n}{n} $$
이다.
조건을 위배하는 경로는 최초로 $y=x+1$ 직선에 닿는 순간, 그 지점을 기준으로 이후 경로를 $y=x$ 직선에 대해 반사시키면 $(-1,1)$에서 $(n,n)$까지 가는 경로와 정확히 1:1 대응된다. 이를 반사법(Reflection Principle)이라고 한다.
따라서 조건을 위배하는 경로의 수는
$$ \binom{2n}{n+1} $$
이다.
그러므로 조건을 만족하는 경로의 수는
$$ C_n = \binom{2n}{n} - \binom{2n}{n+1} $$
이다.
이를 정리하면
$$ C_n = \frac{1}{n+1} \binom{2n}{n} $$
이 성립하여 카탈란 수의 일반 공식이 증명된다.
2-2. 카탈란 수의 생성함수적 증명
$C_n$의 생성함수를 다음과 같이 두자.
$$ f(x) = \sum_{n=0}^{\infty}C_nx^n $$
순환 공식
$$ C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k} $$
의 양변에 $x^n$을 곱하고 $n=1$부터 무한히 더하면
$$ \sum_{n=1}^{\infty}C_nx^n = \sum_{n=1}^{\infty} \left( \sum_{k=0}^{n-1} C_kC_{n-1-k} \right)x^n $$
왼쪽은 생성함수에서 $C_0$을 제외한 부분이다. $C_0=1$이므로
$$ \sum_{n=1}^{\infty}C_nx^n = f(x)-1 $$
오른쪽에 $x$를 하나 묶어내면
$$ x \sum_{n=1}^{\infty} \left( \sum_{k=0}^{n-1} C_kC_{n-1-k} \right)x^{n-1} $$
$m=n-1$이라고 치환하면
$$ x \sum_{m=0}^{\infty} \left( \sum_{k=0}^{m} C_kC_{m-k} \right)x^m $$
한편 생성함수의 제곱은
$$ f(x)^2 = \left( \sum_{k=0}^{\infty}C_kx^k \right) \left( \sum_{j=0}^{\infty}C_jx^j \right) $$
$x^m$의 계수를 모으면
$$ f(x)^2 = \sum_{m=0}^{\infty} \left( \sum_{k=0}^{m} C_kC_{m-k} \right)x^m $$
따라서
$$ f(x)-1 = xf(x)^2 $$
즉
$$ xf(x)^2-f(x)+1=0 $$
이라는 이차방정식을 얻는다.
근의 공식을 이용하면
$$ f(x) = \frac{1\pm\sqrt{1-4x}}{2x} $$
이다.
생성함수는 $x=0$에서 $C_0=1$이어야 한다. $+$를 선택하면 $x\rightarrow0$일 때 발산하므로 생성함수가 될 수 없다.
반면 $-$를 선택하면
$$ \lim_{x\rightarrow0} \frac{1-\sqrt{1-4x}}{2x} = 1 $$
이므로 조건을 만족한다.
따라서 카탈란 수의 생성함수는
$$ \boxed{ f(x) = \frac{1-\sqrt{1-4x}}{2x} } $$
이다.
이 식을 급수로 전개하면
$$ f(x) = 1+x+2x^2+5x^3+14x^4+\cdots $$
이므로
$$ C_n = \frac{1}{n+1} \binom{2n}{n} $$
임을 다시 확인할 수 있다.
3. $C_n$과 일대일 대응되는 5가지 상황
카탈란 수 $C_n$은 위의 격자 경로 문제 외에도 다음 두가지 조합론적 상황과 정확히 일대일 대응된다.
3-1 이진트리
특정 노드로부터 최대 두 개의 가지가 뻗어나갈 수 있는 그래프를 이진트리라 할 때, $n$개의 내부 노드를 가지는 이진트리의 구조는 카탈란 수와 대응된다.
하나의 이진트리를 루트 노드를 기준으로 나누어 보면 왼쪽 부분과 오른쪽 부분이라는 두 개의 작은 이진트리가 만들어진다.
왼쪽 부분에 $k$개의 내부 노드가 있다면 오른쪽 부분에는 $n-1-k$개의 내부 노드가 남는다. 따라서 왼쪽 이진트리를 만드는 경우의 수는 $C_k$, 오른쪽 이진트리를 만드는 경우의 수는 $C_{n-1-k}$이다.
두 부분은 독립적으로 구성되므로 경우의 수를 곱하면
$$ C_kC_{n-1-k} $$
가 된다.
가능한 모든 $k$에 대해 더하면
$$ C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k} $$
가 된다.
이는 앞에서 살펴본 카탈란 수의 순환 공식과 정확히 일치한다. 따라서 $n$개의 내부 노드를 가지는 이진트리의 구조 개수는 $C_n$이다.
3-2 다각형의 삼각분할
$n+2$각형을 서로 교차하지 않는 대각선들로 쪼개어 모든 조각이 삼각형이 되도록 만드는 경우의 수이다.
다각형에서 하나의 꼭짓점을 고정하고, 그 꼭짓점에서 다른 꼭짓점으로 연결되는 대각선 하나를 생각해보자. 이 대각선은 다각형을 두 개의 작은 다각형으로 나눈다.
한쪽 부분이 $k+2$각형이라면 다른 쪽 부분은 $(n-k)+2$각형이 된다.
따라서 두 부분을 각각 삼각분할하는 경우의 수는
$$ C_kC_{n-1-k} $$
이다.
가능한 모든 $k$에 대해 더하면
$$ C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k} $$
라는 카탈란 수의 순환 공식이 그대로 나타난다.
따라서 $n+2$각형의 삼각분할 역시 $C_n$개의 경우의 수를 가지며, 카탈란 수와 일대일 대응된다.
4. 생성함수의 심화 이론
생성함수는 단순히 경우의 수를 계산하는 도구에 그치지 않는다. 수열의 점화식을 하나의 함수 방정식으로 바꾸고, 그 함수의 성질을 분석함으로써 수열의 일반항이나 증가 속도까지 알아낼 수 있다.
4-1. 점화식과 생성함수의 관계
예를 들어 수열이
$$ a_n=a_{n-1}+a_{n-2} $$
라는 점화식을 만족한다고 하자.
생성함수
$$ A(x) = a_0+a_1x+a_2x^2+\cdots $$
를 정의하자.
점화식은 $n\ge2$에서 성립하므로 양변에 $x^n$을 곱하고 $n=2$부터 무한히 더하면
$$ \sum_{n=2}^{\infty}a_nx^n = \sum_{n=2}^{\infty}a_{n-1}x^n + \sum_{n=2}^{\infty}a_{n-2}x^n $$
왼쪽은
$$ \sum_{n=2}^{\infty}a_nx^n = A(x)-a_0-a_1x $$
첫 번째 오른쪽 항은
$$ \sum_{n=2}^{\infty}a_{n-1}x^n = x\sum_{n=2}^{\infty}a_{n-1}x^{n-1} $$
지수를 바꾸면
$$ = x\sum_{m=1}^{\infty}a_mx^m $$
따라서
$$ = x(A(x)-a_0) $$
두 번째 오른쪽 항은
$$ \sum_{n=2}^{\infty}a_{n-2}x^n = x^2\sum_{n=2}^{\infty}a_{n-2}x^{n-2} $$
이므로
$$ = x^2A(x) $$
따라서
$$ A(x)-a_0-a_1x = x(A(x)-a_0)+x^2A(x) $$
이를 정리하면
$$ A(x)-xA(x)-x^2A(x) = a_0+(a_1-a_0)x $$
따라서
$$ \boxed{ A(x) = \frac{a_0+(a_1-a_0)x} {1-x-x^2} } $$
특히 피보나치 수열처럼
$$ a_0=0,\qquad a_1=1 $$
이라면
$$ \boxed{ A(x)=\frac{x}{1-x-x^2} } $$
가 된다.
이처럼 생성함수를 이용하면 수열의 재귀적인 점화식을 하나의 대수적인 함수식으로 변환할 수 있다. 이러한 특징 때문에 생성함수는 조합론뿐만 아니라 점화식, 확률론, 알고리즘 분석 등에서도 사용된다.
4-2. 카탈란 수의 점화식과 대수적 생성함수
카탈란 수의 중요한 특징은 점화식이 곱셈 형태로 나타난다는 것이다.
$$ C_n = \sum_{k=0}^{n-1} C_kC_{n-1-k} $$
카탈란 수의 생성함수를
$$ f(x) = \sum_{n=0}^{\infty}C_nx^n $$
이라고 하자.
점화식의 양변에 $x^n$을 곱하고 $n=1$부터 무한히 더하면
$$ \sum_{n=1}^{\infty}C_nx^n = \sum_{n=1}^{\infty} \left( \sum_{k=0}^{n-1} C_kC_{n-1-k} \right)x^n $$
왼쪽은
$$ f(x)-1 $$
이다.
오른쪽에 $x$를 하나 묶어내면
$$ x \sum_{n=1}^{\infty} \left( \sum_{k=0}^{n-1} C_kC_{n-1-k} \right)x^{n-1} $$
$m=n-1$로 치환하면
$$ x \sum_{m=0}^{\infty} \left( \sum_{k=0}^{m} C_kC_{m-k} \right)x^m $$
그런데
$$ f(x)^2 = \left( \sum_{k=0}^{\infty}C_kx^k \right) \left( \sum_{j=0}^{\infty}C_jx^j \right) $$
이므로 $x^m$의 계수는
$$ \sum_{k=0}^{m}C_kC_{m-k} $$
이다. 따라서
$$ f(x)-1=xf(x)^2 $$
이고, 정리하면
$$ xf(x)^2-f(x)+1=0 $$
이라는 이차방정식을 얻는다.
근의 공식을 이용하면
$$ f(x) = \frac{1\pm\sqrt{1-4x}}{2x} $$
이다.
생성함수는 $x=0$에서 $C_0=1$이어야 한다. $+$를 선택하면 $x\rightarrow0$에서 발산하므로 적절하지 않다.
반면 $-$를 선택하면
$$ \lim_{x\rightarrow0} \frac{1-\sqrt{1-4x}}{2x} = 1 $$
이므로 $C_0=1$을 만족한다.
따라서 카탈란 수의 생성함수는
$$ \boxed{ f(x) = \frac{1-\sqrt{1-4x}}{2x} } $$
이다.
이처럼 카탈란 수의 복잡한 조합론적 구조는 생성함수를 통해 하나의 간단한 이차방정식으로 압축된다.
21기 Exponential 전무겸
댓글