다양한 생성함수와 그 응용 (1)
개요
어떤 주어진 성질을 만족하는 것의 가짓수를 세는 문제를 연구하는 학문을 조합론이라 하며, PS 분야 뿐만 아니라 통계학, 수리물리학 등 다양한 분야에서 중요하게 다루어진다.
일반적으로, PS 분야에서 조합론 문제는 Dynamic Programming 테크닉을 이용하여 효율적으로 해결할 수 있다.
하지만, DP 수열을 정의하는 점화식을 알아내는 작업은 조합론의 영역이지만, 그렇게 정의된 DP 수열을 빠르고 효율적으로 계산하는 작업은 알고리즘의 영역에 속한다.
본 글은, 후자의 알고리즘 문제를 해결하는 좋은 방법에 대하여 수학적으로 기술한다. 점화식 형태로 정의된 수열이 주어질 때, 이를 생성함수라는 강력한 수학 테크닉을 이용하여 계산에 필요한 시간 복잡도를 낮추는 방법을 자세하게 알아보고자 한다.
다루어야 할 내용이 상당히 많기 때문에, 지면의 문제 상 다음과 같이 세 개로 나누고자 한다.
- 생성함수 OGF, EGF와 그 정의 및 간단한 응용 (= 현재 글)
- 분할, 간단한 미적분 등을 사용한 생성함수
- 미분 방정식을 이용한 생성함수
본문에서는 다음의 내용을 부가적인 설명 없이 서술한다. 각 항목에 대하여, 자세하게 서술한 좋은 글을 링크해두었다.
생성함수
Motivation
어떠한 분야의 학문이던지, 이미 가지고 있는 개념을 더욱 확장하는 작업은 학술적으로 아주 중요하다.
수학에서도 18세기부터 이산적인 개념을 연속적인 개념으로 확장하고자 하는 학문적 노력이 있었다.
대표적으로, 자연수와 0에서만 정의되는 팩토리얼 함수를 복소수 범위로 확장한 결과가 감마 함수 $\Gamma (z)$이며, 이로부터 스털링 근사 등을 비롯한 다양한 유용한 공식이 새롭게 유도되었다.
비슷하게, 이산적으로 정의된 ‘수열’을, 실수 혹은 복소수 범위에서 정의되는 ‘함수’로 확장한 결과가 바로 생성함수이다. 따라서, 생성함수를 이용하면 수열에서 관찰하기 어려웠던 새로운 성질을, 해석적인 도구를 이용하여 쉽게 유도할 수 있으리라 기대할 수 있다.
정의
어떤 수열 $\{ a _i \}$의 생성함수 $f(x)$를 만든다는 것은, 그 수열을 특정한 방법으로 변형하여, 실수 $\mathbb{R}$에서 정의된 실함수 $f : \mathbb{R} \rightarrow \mathbb{R}$를 생성한다는 것을 의미한다.
수열을 함수로 변형하는 방법은 아주 다양하지만, PS에서 주로 사용되는 OGF와 EGF에 대해서 다루어보고자 한다.
먼저, 각각의 정의에 대하여 알아보자.
Ordinary Generating Functions (OGFs)
실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$의 OGF $f(x)$는 다음과 같이 정의된다:
$ f(x) = \sum _{ i = 0 }^{ \infty } a _i x^i = a _0 + a _1 x + a _2 x^2 + a _3 x^3 + \cdots $
OGF는 수열을 함수로 변환하는 가장 대중적인 방법이다.
예를 들어, 항등 수열 $1, 1, 1, \cdots$의 OGF는 다음과 같이 나타낼 수 있다:
$ f(x) = 1 + 1 \cdot x + 1 \cdot x^2 + 1 \cdot x^3 + \cdots = 1 + x + x^2 + x^3 + \cdots $
그리고, $x$가 적당히 작다면, 등비수열의 합공식을 이용하여 다음과 같이 표현할 수 있다:
$ f(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x} $
이 등식은 $-1 < x < 1$의 범위에서만 성립한다(그림 1). 그럼에도 문제는 없다. 생성함수를 만드는 목적은, 이 함수가 어떤 $x$ 값에서 수렴하는지 관찰하는 것이 아니다. 이 함수가 $0$을 포함하는 적당히 작은 open interval에서 좋은 성질(연속성, 미분가능성, etc.)을 가지고 있다고 믿고, 이를 이용하여 수열에 관한 새로운 성질을 만들어내기 위하여, 생성함수를 사용할 것이기 때문이다.
그림 1: $\displaystyle \frac{1}{1-x}$의 매클로린 급수 그래프
$(-1, 1)$의 범위에 $x$가 속할 때, $1 + x + x^2 + x^3 + \cdots$의 식에서 항을 더해갈 수록 $\displaystyle \frac{1}{1-x}$에 근사함을 관찰할 수 있다.
이제, 조금은 특이하게 정의된 EGF에 대하여 알아보자.
Exponential Generating Functions (EGFs)
실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$의 EGF $g(x)$는 다음과 같이 정의된다:
$ g(x) = \sum _{ i = 0 }^{ \infty } \frac{ a _i }{ i! } x^i = a _0 + a _1 x + \frac{ a _2 }{ 2! } x^2 + \frac{ a _3 }{ 3! } x^3 + \cdots $
EGF는 지수함수 $e^x$의 매클로린 급수에서 착안되었다. $e^x$의 매클로린 급수는 아래와 같으며, EGF의 정의와 아주 유사함을 쉽게 알 수 있다:
$ e^x = \sum _{ i = 0 }^{ \infty } \frac{ 1 }{ i! } x^i = 1 + x + \frac{ 1 }{ 2! } x^2 + \frac{ 1 }{ 3! } x^3 + \cdots $
즉, 다시 말하면, 앞에서 살펴본 항등 수열 $1, 1, 1, \cdots$의 EGF는 $e^x$이다.
그러면, 어떤 실함수가 주어졌을 때, 이 함수는 어떤 수열로부터 생성되었는지는 어떻게 알 수 있을까? 다음 정리는 우리의 궁금증에 대한 간단한 답을 알려준다.
알려진 정리 (매클로린 급수의 성질)
무한히 미분 가능한 실해석함수 $f(x)$가 주어졌다고 하자.
함수 $f(x)$를 이용하여, 다음과 같이 두 실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$, $\{ b _i \} _{ i = 0, 1, \cdots }$을 정의하자.
수열 $\{ a _i \} _{ i = 0, 1, \cdots }$의 OGF와 수열 $\{ b _i \} _{ i = 0, 1, \cdots }$의 EGF는 모두 $f(x)$와 일치한다.
$ a _n = \frac{ f^{(n)} (0) }{ n! } \qquad ( n = 0, 1, 2, \cdots ) $
$ b _n = f^{(n)} (0) \qquad ( n = 0, 1, 2, \cdots ) $
수열 $\{ a _i \} _{ i = 0, 1, \cdots }$의 OGF의 $n$계 도함수의 상수항이 $\displaystyle n! a _n$라는 점과, 이 값은 $\displaystyle \frac{ f^{(n)} }{ n! }$라는 것을 생각하면 쉽게 받아드릴 수 있다.
EGF의 경우에도 유사하게 증명할 수 있다.
이제, 생성함수의 아주 중요한 대수적 성질을 알아보자. 이 성질 때문에 PS에서 생성함수를 사용한다고 강하게 말할 수 있을 정도로, 이는 아주 유의미하고 강력한 성질이다.
OGF와 EGF의 대수적 성질
두 실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$와 $\{ b _i \} _{ i = 0, 1, \cdots }$의 생성함수가 각각 $A(x)$, $B(x)$라고 하자.
1. 상수배
OGF와 EGF 모두에 대하여, 함수 $C(x) = k \cdot A(x)$는 실수열 $c_i = k \cdot a_i$의 생성함수와 같다. (단, $k$는 상수)
즉, 생성함수를 상수 $k$배하는 것은 해당하는 수열을 $k$배하는 것과 동일한 효과를 가진다.
2. 선형 결합
OGF와 EGF 모두에 대하여, 함수 $C(x) = k_a \cdot A(x) + k_b \cdot B(x)$는 실수열 $c_i = k_a \cdot a_i + k_b \cdot b_i$의 생성함수와 같다. (단, $k_a$와 $k_b$는 상수)
생성함수끼리 선형 결합을 하는 작업은, 해당 수열의 선형 결합을 의미한다.
이를 어려운 말로, 수열을 생성함수로 변환하는 작업은 선형 결합 연산을 보존한다고 말한다.
3. 각 항에 Index $i$를 곱하기
OGF와 EGF 모두에 대하여, 함수 $C(x) = x A’(x) = x \cdot \frac{ \mathrm{d} }{ \mathrm{d} x } A(x)$는 실수열 $c_i = i \cdot a_i$의 생성함수와 같다.
이 성질은 조합론 문제를 DP 수열로 해결할 때 많은 도움을 줄 것이다.
또한, 도함수에 관한 항이 등장하기 때문에, 복잡한 DP 점화식을 알려진 미분 방정식으로 변환하여 해결하는 테크닉을 사용할 수 있을 것이라는 암시를 한다.
4. 평행이동 (오른쪽)
자연수 $k$에 대하여, 실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$를 오른쪽으로 $k$만큼 평행이동한 실수열 $c _i = a _{i-k}$을 생각하자.
즉, $\displaystyle \left( c _0, c _1, \cdots, c _{k-1}, c _k, c _{k+1}, c _{k+2}, \cdots \right) = \left( 0, 0, \cdots, 0, a _0, a _1, a _2, \cdots \right)$임에 유의하라.
함수 $C_O (x) = x^k A(x)$는 실수열 $\{ c _i \} _{ i = 0, 1, \cdots }$의 OGF와 같다.
함수 $A(x)$를 $k$번 적분한 함수 $\displaystyle C_E (x) = \idotsint A(x) \mathrm{d}^k x$는 실수열 $\{ c _i \} _{ i = 0, 1, \cdots }$의 EGF와 같다.
OGF와 EGF의 정의의 사소한 차이 때문에, 평행이동한 수열의 생성함수 또한 다르다는 점을 인지하여야 한다.
5. 평행이동 (왼쪽)
자연수 $k$에 대하여, 실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$를 왼쪽으로 $k$만큼 평행이동한 실수열 $c _i = a _{i+k}$을 생각하자.
즉, $\displaystyle \left( c _0, c _1, c _2, \cdots \right) = \left( a _k, a _{k+1}, a _{k+2}, \cdots \right)$임에 유의하라.
함수 $\displaystyle C _O (x) = \frac{1}{x^k} \left( A(x) - a _0 - a _1 x - a _2 x^2 - \cdots - a _{k-1} x^{k-1} \right)$는 실수열 $\{ c _i \} _{ i = 0, 1, \cdots }$의 OGF와 같다.
함수 $A(x)$를 $k$번 미분한 함수 $\displaystyle C _E (x) = \frac{ \mathrm{d}^k }{ \mathrm{d}^k x } A(x) = A^{(k)} (x)$는 실수열 $\{ c _i \} _{ i = 0, 1, \cdots }$의 EGF와 같다.
평행이동을 왼쪽으로 할 때와 상반됨을 관찰하라.
OGF의 경우 $x^k$를 곱하거나 나누는 것이 평행이동이라면, EGF의 경우에는 $k$번 적분하거나 미분하는 것이 평행이동이다.
이제, 제일 강력한 성질 세 가지를 소개한다. 이는 꼭 암기하여야 한다고 자신있게 말할 수 있다.
6. 합성곱 (Convolution)
먼저, 합성곱이라는 개념이 생소한 독자를 위하여, 먼저 그 정의를 소개한다.
두 함수의 합성곱
두 실함수 $f(x)$, $g(x)$의 합성곱은 $(f*g)(x)$과 같이 나타내며, 다음과 같이 정의한다:
$ (f*g)(x) = \int _{ - \infty }^{ \infty } f(u) g(x-u) \mathrm{d} u $
두 수열의 합성곱
두 실수열 $\{ a _i \} _{ i = 0, 1, \cdots }$, $\{ b _i \} _{ i = 0, 1, \cdots }$의 합성곱은 $\{ (a*b) _i \} _{ i = 0, 1, \cdots }$로 나타내며, 다음과 같의 정의한다:
$ (a*b)(n) = \sum _{i = 0}^{n} a _i b _{n-i} $
합성곱에 대한 더 자세한 내용은 다음 글을 참고하라.
그러면, 두 수열의 합성곱의 생성함수은 어떻게 표현할 수 있을까? 아래의 강력한 정리는 이에 대한 답을 알려준다.
정리 (두 수열의 합성곱의 생성함수)
두 함수 $A(x)$와 $B(x)$의 곱 $C(x) = A(x) B(x)$는 다음과 같이 정의된 수열 $\{ c _i \} _{ i = 0, 1, \cdots }$의 OGF와 같다:
$ c _n = \sum _{i = 0}^{n} a _i b _{n-i} = (a*b) _n $
또한, 동일한 함수 $C(x) = A(x) B(x)$는 아래와 같이 정의된 수열 $\{ d _i \} _{ i = 0, 1, \cdots }$의 EGF와 같다:
$ d _n = \sum _{i = 0}^{n} \binom{n}{i} a _i b _{n-i} $
EGF에서 등장하는 조합 기호 $\binom{n}{i}$ 때문에, OGF로는 해결할 수 없지만 EGF로는 가능한 경우가 존재한다.
7. 분할 (Partition)
자연수 $k$에 대하여, 다음이 성립한다.
- 수열 $\displaystyle c _n = \sum _{ i _1 + i _2 + \cdots i _k = n } a _{ i _1 } a _{ i _2} \cdots a _{ i _k }$의 OGF는 $C(x) = A(x)^k$와 같다.
- 수열 $\displaystyle d _n = \sum _{ i _1 + i _2 + \cdots i _k = n } \frac{ n! }{ i _1 ! i _2 ! \cdots i _k ! } a _{ i _1 } a _{ i _2} \cdots a _{ i _k }$의 EGF는 $C(x) = A(x)^k$와 같다.
즉, 생성함수를 $k$번 곱한 함수는, 수열의 index $n$을 $k$개의 정수의 합으로 표현한 분할에 대하여 곱연산을 취한 것과 같은 효과이다.
$k = 2$일 때, 위의 분할과 합성곱이 밀접한 연관성을 가진다는 사실을 눈여겨 보아야 한다.
8. 구간 합 (Prefix Sum Technique)
실수열 $c _n = a _0 + a _1 + a _2 + \cdots + a _n$의 OGF는 $\displaystyle C(x) = \frac{1}{1-x} A(x)$와 같다.
DP 문제를 해결할 때, Prefix sum에 관한 식으로 표현해야 할 필요가 종종 생긴다.
위 정리는 수열의 Prefix sum과 OGF 생성함수 간의 연관성을 알려준다.
증명은 “2. 선형결합” 및 “4. 평행이동 (오른쪽)” 성질과 아래의 수식을 이용하여 쉽게 알아낼 수 있다.
$ \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots $
이제, 위에서 살펴본 8가지의 성질을 이용하여, 몇 가지 유명한 수열을 생성함수로 표현해보자.
생성함수의 예시
피보나치 수열
피보나치 수열 $f _n$의 OGF 생성함수 $F(x)$를 계산해보자.
먼저, 피보나치 수열을 다음과 같이 정의하자:
- $f _0 = f _1 = 0$
- $f _n = $f _{n-1} + f _{n-2} \qquad n = 2, 3, 4, \cdots$
정의의 점화식을 다음과 같이 변형해보자. 점화식의 양변에 $x^n$을 곱해준 결과이다.
$ f _n x^n = f _{n-1} x^n + f _{n-2} x^n = x \left( f _{n-1} x^{n-1} \right) + x^2 \left( f _{n-2} x^{n-2} \right) $
이제, 위 식을 모든 $n = 2, 3, \cdots$에 대하여 더하자.
$ \sum _{n=2}^{\infty} f _n x^n = x \sum _{n=2}^{\infty} f _{n-1} x^{n-1} + x^2 \sum _{n=2}^{\infty} f _{n-2} x^{n-2} $
피보나치 수열 $f _n$의 OGF $F(x)$의 정의에 따르면,
$ F(x) = \sum _{n=0}^{\infty} f _n x^n $
이므로, 위의 식은 다음과 같이 표현할 수 있을 것이다:
$ F(x) - f _0 - f _1 x = x \left( F(x) - f _0 \right) + x^2 F(x) $
$ F(x) \left( 1 - x - x^2 \right) = x $
$ F(x) = \frac{ x }{ 1 - x - x^2 } $
따라서, 피보나치 수열의 OGF는 $\displaystyle \frac{x}{1 - x - x^2}$이다.
카탈랑 수열
카탈랑 수 $c _n$는 $(n+1)$개의 단말 노드(Leaves)를 가지는 이진 순서 트리의 가짓수를 의미한다.
따라서, 다음과 같이 카탈랑 수열을 정의할 수 있다:
- $c _0 = 1$
- $\displaystyle c _{n+1} = \sum _{k = 0}^{n} c _k c _{n-k} \qquad n = 0, 1, 2, \cdots$
마지막 점화식은, 루트 노드의 왼쪽 부트리의 크기를 $k$로, 오른쪽 부트리의 크기를 $n-k$로 설정하였을 때의 가능한 이진 트리의 가짓수가 $c _k c _{n-k}$라는 사실로부터 유도할 수 있다.
피보나치 수열과 유사하게, 점화식의 양변에 $x^{n+1}$을 곱한 후, 모든 $n = 0, 1, 2, \cdots$에 대하여 더하자.
$ \sum _{n=0}^{\infty} c _{n+1} x^{n+1} = \sum _{n = 0}^{\infty} \sum _{k = 0}^{n} c _k c _{n-k} x^{n+1} = x \sum _{n=0}^{\infty} \sum _{i = 0}^{\infty} \left( c _k x^k \right) \left( c _{n-k} x^{n-k} \right) $
카탈랑 수열 $c _n$의 OGF를 $C(x)$라고 하자. 좌변은 자명하게 $C(x) - 1$이다. 또한, 우변은 “6. 합성곱” 성질에 따르면, $x C(x)^2$와 같다. 카탈랑 수열과 자기 자신의 합성곱의 OGF 생성함수에 $x$를 한 번 곱한 형태이기 때문이다.
따라서, 다음과 같은 등식을 얻는다: $\displaystyle C(x) - 1 = x C(x)^2 $
이 등식을 $C(x)$에 대한 이차 방정식으로 해석하면, $C(x)$를 $x$에 대한 식으로 표현할 수 있다:
$ C(x) = \frac{ 1 \pm \sqrt{ 1 - 4x } }{ 2x } $
여기서, $\pm$ 중 어떤 부호가 맞을까? 함수 $C(x)$가 연속이라고 믿으면, $\displaystyle \lim_{x \to 0} C(x) = C(0) = c _0 = 1$라야 한다.
$ \lim_{x \to 0} \frac{ 1 + \sqrt{ 1 - 4x } }{ 2x } = \infty $
이므로, $\pm$ 중 빼기 기호를 선택하여야 옳음을 알 수 있다. 정리하면, 카탈랑 수의 OGF는
$ C(x) = \frac{ 1 - \sqrt{ 1 - 4x } }{ 2x } $
이다.
생성함수의 이점에 관한 간략한 설명
카탈랑 수의 점화식 정의만을 이용하면, $c _n$을 알아내기 위해서는 $c _0, c _1, \cdots c _{n-1}$의 값이 모두 필요하고, 또한, 그 $n$개의 값으로부터 계산하는데 $O(n)$의 시간이 걸린다.
즉, $c _n$을 계산하기 위해서 $O \left( n^2 \right)$ 번의 연산을 수행하여야 한다.
하지만, 생성함수 $\displaystyle C(x) = \frac{ 1 - \sqrt{ 1 - 4x } }{ 2x } $는 다항식으로 표현할 수 있으며, 이 작업은 $O \left( n \lg n \right)$ 번의 연산만으로 완료할 수 있다. 다항식의 제곱근을 구하는 작업을 $O \left( n \lg n \right)$의 시간 복잡도로 해결할 수 있기 때문이다.
따라서, 생성함수를 이용하면, 카탈랑 수 $c _0, c _1, \cdots, c _n$ 모두를 $O \left( n \lg n \right)$만에 계산할 수 있다. 이것은 생성함수가 주는 수많은 이점 중 하나이다!
벨 수열
벨 수 $b _n$는 $n$개의 원소로 이루어진 집합을 분할하는 경우의 수를 의미한다. 정의로부터 아래 두 개의 등식을 쉽게 유도할 수 있다:
- $ b _0 = 1 $
- $\displaystyle b _n = \sum _{k = 0}^{n-1} \binom{n-1}{k} b _k \qquad n = 1, 2, 3, \cdots $
마지막 등식은, $n$개의 원소 중 특정한 한 원소와 같은 분할에 들어갈 원소 $k$개를 $(n-1)$개의 남은 원소 중에서 골라낸다고 생각하면 쉽게 이해할 수 있다.
점화식에 $\displaystyle \binom{n}{k}$가 등장하기 때문에, OGF보다는 EGF가 더 적합하다. 벨 수열 $b _n$의 EGF를 $B(x)$라고 하자.
점화식을 조금 변형하여 다음 등식을 만들자:
$ n \cdot \frac{ b _n }{ n! } = \sum _{ k = 0 }^{ n - 1 } \frac{ b _k }{ k! } \frac{ 1 }{ (n - k - 1)! } $
이제, 양변에 $x^n$을 곱한 후, 모든 $n = 1, 2, 3, \cdots$에 대하여 더하자.
$ \sum _{n=1}^{\infty} n \cdot \frac{ b _n }{ n! } x^n = x \sum _{n=1}^{\infty} \left( \sum _{k=0}^{n-1} \frac{ b _k x^k }{ k! } \frac{ x^{n-k-1} }{ (n-k-1)! } \right) $
좌변은 “3. 각 항에 Index $i$ 곱하기” 및 “4. 평행이동 (오른쪽)” 성질에 의하여, $x B’(x)$과 같다.
우변은 $B(x)$의 수열과 $e^x$의 수열의 합성곱과 연관되어 있음을 관찰하여야 한다. 즉, “6. 합성곱 (Convolution)” 성질에 따르면 $x B(x) e^x$와 같다.
따라서, 다음 미분 방정식을 얻는다:
$ x B’(x) = x B(x) e^x $
이는 상당히 쉬운 일계 선형 미분 방정식이므로, 그 해 또한 쉽게 구할 수 있다:
$ B(x) = e^{ e^x - 1 } $
카탈랑 수열과 마찬가지로, 위에서 구한 EGF 생성함수를 이용하면, $b _0, b _1, \cdots, b _n$의 모든 값을 $O \left( n \lg n \right)$만에 계산할 수 있다.
결론
거의 대부분의 PS 문제를 풀 때 사용되는 동적 계획법 테크닉은, 어떤 값을 구하기 위하여 수열을 정의하고, 이 수열의 점화식으로부터 답을 계산해낸다.
하지만, 종종 수열의 점화식만을 이용해서 답을 구하는 과정은 상당히 비효율적이다. 앞에서 살펴본 카탈랑 수와 벨 수가 그러한 경우의 대표적인 예시이다.
수열을 연속적으로 확장한 생성함수는 상당히 강력한 8가지 성질을 가지며, 이는 수열의 점화식에 적용하기에 아주 적합하다.
생성함수의 대표적인 예인 OGF와 EGF에 대하여 깊게 알아보았고, 이를 적절히 응용하면 기존에 수열을 계산하는데 필요한 시간 복잡도를 더욱 개선할 수 있었다. 카탈랑 수와 벨 수 모두 기존의 알고리즘은 $O \left( n^2 \right)$의 시간 복잡도를 가진 반면에, 새롭게 알아낸 생성함수를 이용하면 $O \left( n \lg n \right)$이라는 빠른 시간 복잡도로 계산할 수 있었다.
다음 포스트에서는, 더 복잡하고 흥미로운 조합론 문제에 생성함수 테크닉을 적용하여 효율적으로 해결할 것이다.