Generating Function과 조합론적 응용
생성함수의 성질을 알아봅시다.
생성함수
덧셈에 대한 식에 대해 조합론적 값을 구할 때 생성함수가 도움이 되는 경우가 많다. 생성함수가 무엇인지 살펴보고, 어떻게 사용되는지를 살펴보자.
생성함수의 정의
간단하게 말해서, 무한수열이 계수인 formal power series이다. 기존의 power series와의 차이는 수렴반경을 전혀 안 고려해도 된다는 점인데 이게 무슨 말인지 간단하게 살펴본다면, 물론 기존의 power series function은 수렴반경을 가져야 하는 것이 맞다. 그런데 formal power series는 계수를 알아내는 게 목적이라 수렴성은 무시하고, 단순히 계수만 보는 것이다.
생성함수의 성질
그런데 수렴반경만 문제였다면, 이를 지운 상황에서 여전히 다른 다항식의 성질들은 모조리 적용할 수 있을 것이다. 어떤 의미인지, 왜 가능한지 알기 위해서는 이 formal power series가 ring을 구성한다는 점을 확인하면 된다.
Ring, Field의 정의
우선 Ring(환)은 임의의 집합 $R$와 두 개의 이항 연산 (이름을 붙이자면, $+$(덧셈)와 $\cdot$(곱셈)) 여기서 ring axiom으로 보는 3가지 공리를 만족시켜야 한다.
우선 $R$은 덧셈에 대해서 abelian group이여야 한다. 이가 의미하는 바는, 기존 group의 정의에 교환법칙이 추가된다.
$R$은 곱셈에 대해서 monoid여야 한다. 이는 group보단 약한 정의인데, 단순히 결합법칙과 곱셈의 항등원만 존재하면 된다.
곱셈과 덧셈은 분배법칙을 만족해야 한다.
가장 대표적인 Ring으로는 $\mathbb{Z},\mathbb{Q}, \mathbb{R}$ 등이 있으며, $\mathbb{Z} / n \mathbb{Z}$ (나머지가 같은 congruence class들의 집합)도 참조할 만하다.
Field의 정의는 Ring의 정의에서, 곱셈 또한 abelian group인 것이다!($0$으로 나누는 것을 방지하기 위해서 그건 역원을 정의하지 않는다)
그럼 여기서 다항식의 정의를 조금 확장해보자. $A$가 ring일때, 무한 수열 $(f_{0},f_{1},\cdots)$이 있고, 어떤 $n$이 존재해서 $f_{n+1}=f_{n+2}=\cdots=0$인 것이다. 이걸 다항식으로 정의하면 덧셈, 뺄셈, 곱셈 등이 자연스레 정의된다. 물론 여기서 자연스레 $f(x)$라는 함수를 떠올리기 쉬운데, 이는 두 다항식이 동치인 게 모든 정의역의 함숫값이 같은 것과 동치이기 때문이다. (증명은 인수정리로 간편히 할 수 있다) 물론 이는 무한환에서만 가능한 행위고, 유한환인 경우 서로 다른 다항식이여도 같은 다항함수를 정의할 수 있다.
Formal Power Series의 사용 방법
$A$가 ring일때, 무한 수열 $(f_{0},f_{1},\cdots)$이 있으면 이를 이제 formal power series의 계수 수열($A[[x]]$이라고 하자)로 보면 될 것이다. 물론 이를 함수로 보기 시작하면 수렴반경 이야기가 튀어나오기에, 이런 식으로 보지 말고, 단순히 다항식이라는 관점에서 보는 것이다. 결론부터 말하자면, 굳이 해석적 의미를 생각할 필요없이 대수적 관점에서만 처리해도 충분하다는 것이다.
이후의 전개를 편하게 하기 위해서, $x^{n}$으로 나눈 나머지를 그냥 $x^{0}$부터 $x^{n-1}$까지의 개수만 본다고 하자. 이제 $A[[x]]$가 ring이 됨을 증명해보자.
간단하게 결합법칙만 생각하자면, $\bmod x^{n}$으로 잘라낸 다항식에 대해 실제로 곱이 같은지가 생각하면 되고, 그 이후는 알아서 진행하면 될 것이다.
이번에는 이러한 formal power series의 역원(ring이라 존재할 필요없는데 존재한다!)에 대해서 생각해보자. 즉 곱이 1이 되는 상황인데, $fg=1$에서 $g$가 역원이 된다고 생각하고 개수를 맞춰보면 된다. 다항식 곱을 실제로 생각해보면 $f_{0}g_{0}=1$, $\sum\limits_{i+j=k}f_{i}g_{j}=0$이면 되니, 우린는 $f_{0}g_{k}$를 $g_{0}$부터 $g_{k-1}$에 대해서 표현할 수 있으니까, 역원에 존재하고 실제로 construct까지 할 수 있다. (그래봤자 테일러함수로 나타내진 꼴과 차이가 없다)
Ex. Catalan Numbers
카탈란 수는 $C_{0}=1$, $C_{n}=\sum\limits_{i+j=n}C_{i}C_{j}$인 수열을 의미한다. 이의 점화식을 생성함수를 통해 쉽게 구해보자. 우선 생성함수를 $c(x)=\sum\limits_{n=0}^{\infty}C_{n}x^{n}$으로 두게 되면 정의에 의해 $c(x)=1+xc(x)^{2}$가 되며, 이를 근의 공식으로 전개하면 $c(x)=\frac{1-\sqrt{1-4x}}{2x}$가 된다. (다른 한 근은 $C_{0}$의 초깃값 문제로 실패) 이제 테일러 전개(즉, 유리수 지수의 이항정리)을 바탕으로 정리를 하자. 그렇게 하여 정리할 시 우리가 아는 카탈란 수인 $\frac{1}{n+1}\binom{2n}{n}$이 나오게 된다.
Ex. $\frac{1}{(1-x)^{n}}$의 generating function
우선 생성함수의 역원을 바탕으로 $\frac{1}{1-x}$의 생성함수를 생각해보면 $\sum\limits_{n=0}^{\infty}x^{n}$이 됨을 알 수 있다. (점화관계가 등차수열이 되므로) 해당 식을 미분하면(혹은 제곱을 하여) $\frac{1}{(1-x)^{2}}=\sum\limits_{n=0}^{\infty}(n+1)x^{n}$이 된다. 계속 미분을 하게 되면 $\frac{1}{(1-x)^{3}}=\sum\limits_{n=0}^{\infty}\binom{n+2}{2}x^{n}$이 된다. (두 번 미분하면서 2가 나오게 되니). 이제 귀납적으로 $\frac{1}{(1-x)^{k}}=\sum\limits_{n=0}^{\infty}\binom{n+k-1}{k-1}x^{n}$으로 두게 되면 양변을 미분할 시(혹은 $\frac{1}{1-x}$을 곱한다면 생각하면: 이 경우는 하키스틱 공식으로 유도하면 된다) $\frac{1}{(1-x)^{k+1}}=\sum\limits_{n=0}^{\infty}\binom{n+k}{k}x^{n}$임을 보일 수 있다. 즉 귀납법에 의해,
$\frac{1}{(1-x)^{k}}=\sum\limits_{n=0}^{\infty}\binom{n+k-1}{n}x^{n}$
(마지막 부분은 $\binom{n}{r}=\binom{n}{n-r}$ 이용)
예제
BOJ 13542 (우표 구매하기(Hard))
중복조합적 관점으로 생각하면 편하다. 만일 1원을 $t$ 종류 사용한다면, 2원은 $\frac{k-t}{2}$(물론, 정수로 정의되는 경우만)개를 써야 한다. 이걸 곱하기 쉬운 방법을 찾기 위해서, 생성함수를 사용하면 된다.
1원을 처리하기 위해서 $\frac{1}{(1-x)^{n}}$를, 2원을 처리하기 위해서 $\frac{1}{(1-x^{2})^{m}}을 사용하여 둘을 곱해준 결과가 될 것이다. 그런데..
$\frac{1}{(1-x)^{n}(1-x^{2})^{m}}=\frac{(1+x)^{n}}{(1-x^{2})^{n+m}}$!
즉, 분모를 $\frac{1}{1-x}$의 생성함수 처리하는 느낌으로 처리하고, 분자는 단순히 이항정리를 하여 곱하였을 때, $x^{k}$의 개수를 찾는 문제가 된다.
$K$가 많이 크기에, 소수에 대한 나머지를 구하기 위해서 Luca’s Theorem을 같이 사용해주면 된다.
다음은 해당 파이썬 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import sys
input = sys.stdin.readline
N,M,K,P = map(int,input().split())
L = [1]*(999992)
for i in range(2,999992):
L[i]=(L[i-1]*i)%(P)
def comb(N,K):
global L
M = P
def p_base(N,M):
res = []
while N>0:
res.append(N%M)
N//=M
return res
def exponent(a,n):
if n == 0:
return 1
if n == 1:
return (a%(M))
else:
x = exponent(a,n//2)
if n%2 == 0:
return ((x%(M))**2)%(M)
else:
return ((x%(M))**2*a)%(M)
L1,L2 = p_base(N,M),p_base(K,M)
if len(L2)>=len(L1):
for i in range(len(L2)-len(L1)):
L1.append(0)
else:
for i in range(len(L1)-len(L2)):
L2.append(0)
ans = 1
for i in range(len(L2)):
N,K = L1[i],L2[i]
ans=(ans*(L[N]*exponent((L[K]*L[N-K])%(M),M-2))%(M))%M
return ans
ANS = 0
for i in range(N+1):
if (K-i)%2==0:
ANS+=comb(N,i)*comb(N+M+(K-i)//2-1,N+M-1)
ANS%=P
print(ANS)
BOJ 23824 (서버 증축)
식 변환을 잘 하면 되는 재밌는 문제. 우선 차수를 $n$로 맞추면 된다는 관점에 주목하여 다항식으로 현재 상황을 나타내자면,
$\prod\limits_{i=0}^{k-1}(1+x^{2^{i}})^{a}$가 된다. 이거의 $x^{n}$의 개수를 찾으면 끝나는 문제인데, 분모와 분자에 $(1-x)^{a}$을 곱하게 되면 분자가 합차공식에 의해 순식간에 정리되면서 $\frac{(1-x^{2^{k}})^{a}}{(1-x)^{a}}$이 된다. 분자는 첫 문제와 비슷하게 이항정리는, 분모는 생성함수로 정리해서 $x^{n}$의 개수를 가져오면 된다. ($1048573$은 소수이니, 마찬가리로 뤼카정리 사용)
다음은 해당 파이썬 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import sys
input = sys.stdin.readline
MOD = 1048573
P = MOD
L = [1]*(10000001)
for i in range(2,10000001):
L[i]=(L[i-1]*i)%(P)
def comb(N,K):
global L
M = P
def p_base(N,M):
res = []
while N>0:
res.append(N%M)
N//=M
return res
def exponent(a,n):
if n == 0:
return 1
if n == 1:
return (a%(M))
else:
x = exponent(a,n//2)
if n%2 == 0:
return ((x%(M))**2)%(M)
else:
return ((x%(M))**2*a)%(M)
L1,L2 = p_base(N,M),p_base(K,M)
if len(L2)>=len(L1):
for i in range(len(L2)-len(L1)):
L1.append(0)
else:
for i in range(len(L1)-len(L2)):
L2.append(0)
ans = 1
for i in range(len(L2)):
N,K = L1[i],L2[i]
ans=(ans*(L[N]*exponent((L[K]*L[N-K])%(M),M-2))%(M))%M
return ans
k,a,n=map(int,input().split())
ans=0
if (2**k-1)*a<n:
print(0)
exit()
for i in range(n//(2**k)+1):
if i%2 == 0:
ans+=comb(a,i)*comb(n-(2**k*i)+a-1,a-1)
else:
ans-=comb(a,i)*comb(n-(2**k*i)+a-1,a-1)
ans%=MOD
print(ans%MOD)
BOJ 7048 (Sweets)
(사실 정해는 생성함수는 아니지만, 생성함수로 풀 수 있어 들고 왔다.) 앞 두 문제와 비슷하게, 다항식으로 formulate을 시도해보면 $\prod\limits_{i=1}^{n}\sum\limits_{j=0}^{m_{i}}x^{j}$을 구해주면 된다. 여기서 등비수열의 합 공식을 사용해주면
식이 $\prod\limits_{i=1}^{n}\frac{1-x^{m_{i}+1}}{1-x}$이 된다. (물론 분모를 한 번에 묶어서 처리하는 방법도 존재하는 방법도 있긴 한데, 2004로 나눈 나머지 때문에 (링크) 문제 처럼 전처리에 중국의 나머지 정리를 섞어야 해서 구현 난이도가 급상승한다. 에라토스테네스의 체를 쓰기엔 마찬가지로 $a,b$가 너무 크다..)
이제 하나씩 기본 다항식인 $[1,0,0,\cdots]$($x^{a}$부터 $x^{b}$까지 구해야 하니, $b+1$개의 원소만 있어도 충분하다)에다가 저 식을 하나씩 곱해줄 것을 생각할 것이다. 어차피 $x^{b}$ 이후의 차수들은 볼 이유가 없기에, $(1-x^{i})$꼴을 곱할 때는 기존 것에다 $i$만큼 평행이동된 항에 계수를 뺴준다를, $1-x$를 나눈다는 건 조립제법으로 생각하여 처리해 주면 된다.
다음은 $a,b$의 범위 때문에 C++으로 해결한 풀이이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
void solve() {
int n, a, b; cin >> n >> a >> b;
vector<int> f(b+1);
const int MOD = 2004;
f[0] = 1;
for(int i=0;i<n;i++) {
int jar; cin >> jar;
jar++;
for (int i=0;i<b;i++){
f[i+1]+=f[i];
if (f[i+1]>=MOD) f[i+1]%=MOD;
}
for (int i=b-jar;i>=0;--i){
f[i+jar]-=f[i];
if (f[i+jar]>=MOD) f[i+jar]%=MOD;
if (f[i+jar]<0) f[i+jar]=MOD+f[i+jar]%MOD;
}
}
int ans = 0;
for(int i=a;i<=b;i++) {
ans += f[i];
if(ans>=MOD) ans%=MOD;
if (ans<0) ans=ans%MOD+MOD;
}
if (ans<0) ans=ans%MOD+MOD;
if (ans>=0) ans=ans%MOD;
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC = 1;// cin >> TC;
for(int tc=0;tc<TC;tc++) {
solve();
}
}
BOJ 13429 (동전 교환)
작성 예정입니다. ($\Leftrightarrow$ 푸는 중)
BOJ 31419 (배열 제작의 달인)
우선 현재 리스트를 바탕으로 사용가능한 각 숫자의 개수를 리스트에 담아준다. 앞서 문제들과의 차이점이라면 $A[1]+\cdots+A[N]=M$($M$: $0$의 개수)에서 $A[i]$가 bounded되어 있을 때 단순히 만족하는 개수가 아니라 배열하는 개수, 즉 $\frac{M!}{\prod\limits_{i=1}^{N}A[i]!}$의 모든 개수를 전부 구해줘야 한다. 즉, 이걸 단순히 전부 구하기에는 숫자가 너무 크기에 다른 방안을 모색해야 한다.
그런데 DP Table을 DP[$i$ 현재까지 고려한 수(즉, $1$ 부터 $i$까지만 보기)] [$j$ (0에서 변화시킨 개수))]으로 생각해보자. 우리의 목표는 DP[$N$][$M$]을 구하는 것임을 파악할 수 있으며, 이제 점화관계를 조사해보자.
DP[$i$][$j$]에서 마지막 원소가 $k$개($k$는 개수에 대해 bounded)인 경우를 조사해보자. 앞에 변화시킨 건 $j-k$개이니 그것만 세면 DP[$i-1$][$j-k$]가 되며, 이제 $k$개로 새로 배정되는 자리는 우리가 배치한 후 순서가 바뀌어도 상관없이 $k!$으로 나누면 된다.
BOJ 13178 (목공)
작성 예정입니다. ($\Leftrightarrow$ 푸는 중)