조합론 in PS

일단 이 글은 생성함수함(이하 젠펑), 기댓값 등에 대한 기초 이해를 필요로 합니다.

1. 더블카운팅과 기댓값의 선형성

사실 둘은 같은 말인데, 기댓값의 선형성에서 전체 경우의 수를 곱하면 더블카운팅이 된다.

 

25441 디지털 회로

문제를 요약하긴 귀찮으니 문제 요약은 하지 않도록(? 하겠다.

 

사실 식을 정리하면서 얻은 관찰 등이 있지만, 이를 생략하고 가자면

결론은 이 문제는 기댓값으로 접근하면 쉽다는 것이다.

 

당연히 다음과 같은 DP 느낌으로 접근한다.

- $DP[i]$ : $i$번째 노드가 1이 되는 경우의 수

 

이렇게 되면, $DP[i]$는

$($자식 중 1개 이상이 1이 되는 경우의 수$) + ($ 2개 이상이 1이 되는 경우의 수$) \dots$

가 된다. 이를 다시 정리하면,

$ 1 \times ( $ 자식 중 1개가 1이 되는 경우의 수 $) + 2 \times ($ 2개가 1이 되는 경우의 수 $) \dots$

이 된다. 이는, 기댓값과 관련이 있음을 시사한다.

전체 경우의 수로 나누면, 이 값은 "자식 중 1의 개수의 기댓값"으로 생각할 수 있다.

이를 이용하면 바로 식이 나오는데, 각 자식마다

$X[i] = DP[i] / ($자기 서브트리를 정하는 경우의 수$)$

로 두면, $X[i]$는 i의 값이 1이 될 기댓값을 나타낸다. $($그냥 확률이랑 같다$)$

그러면, 기댓값의 선형성에 의해 자신의 자식의 $X[i]$값을 더한게 나의 $X[i]$값이 된다.

 

이후는 여러분의 몫에 맡긴다.

2. 생성함수（이하 생함/젠펑）

CF round 1008 1C

https://codeforces.com/contest/2077/problem/C

결론부터 말하자면, 

$\sum_{x=0}^{a}\sum_{y=0}^{b}(x-y)^2 \binom{a}{x} \binom{b}{y}$

의 값을 빠르게 구해야 한다.

 

일반적으로 $f(x) = \sum a_i x^i$에 대해, $\sum a_i i^2$은, $f^{\prime\prime}(1) + f^\prime(2)$이 된다.

결정적인 것은, 이는 음수 지수에 대해서도 성립한다는 것이다. 이를 이용하면

$f(x) = (x+1)^a (x^{-1}+1)^b$

에 대해, $\sum a_i i^2$의 값을 계산하는 문제가 된다.

간단한 식정리로 $O(1)$에 계산할 수 있는 식을 만들 수 있다. 사실 $O(logN)$이다. pow때문에

 

IOI2025 中国国家集训队集中培训 乘积的期望（expectation）

https://qoj.ac/contest/1876/problem/9906

이 문제에서 변형된, 특수 경우인 다음 문제를 살펴봅시다.

$N$개의 수 $a_1, a_2 \dots a_N$이 있고, 초깃값은 모두 $0$이다.

$M$번 다음과 같은 시행을 한다.

- $N$개의 수 중 하나를 골라, 1을 더한다. 단, 각 수가 골라질 확률은 $p_i$이다. 합은 당연히 1이다.

 

최종적으로, $a_1 * a_2 \dots a_N$의 기댓값을 구하라.

 

1. 기댓값의 선형성을 이용한 풀이

$X_{ij}$를, $j$번째에서 $i$번 수를 뽑으면 $1$, 아니면 $0$인 확률변수라고 하자. 그러면,

$ (X_{11} + X_{12} \dots)(X_{21} + X_{22} \dots) \dots $

의 기댓값을 구하는 것이 된다. 전개 후 각 항마다 따로 계산하면, $\frac{M!}{N!}\prod p_i$이 된다.

 

2. 젠펑을 이용한 풀이

$f_i(x) = \sum \frac{i (px)^i}{i!}$로 두면,

$f_1 * f_2 * f_3 \dots$

에서 $M$번째 계수 $*M!$이 답이 된다.

식정리를 통해 

$f_i(x) = x p_i e^x$

임을 알 수 있고, 최종적으로 답은 위와 동일하게 나온다.

 

Lagrange–Bürmann formula

$G(x)$가 다음과 같이 암묵적으로 정의된 멱급수라고 하자:

$G(z) = z \phi(G(z))$

$\phi(y)$는 $y$에 대한 해석함수, 즉 다항함수이다. 뭐 정확히는 조금 다르지만.

이때, $H(x)$를 어떤 다항함수라 했을 때

$[z^n](H(G(z))) = \frac{1}{n}[t^{n-1}](H^{\prime}(t) \phi(t)^n)$

이 성립한다.

 

이를 어떻게 쓰는가? 다음은 한 예시이다.

 

카탈란 수 변형

길이 $2N$의 딕 경로$($Dyck Path$)$ 중, 처음 시작지점을 제외하고 $y=0$과 $k$번 만나는 경로의 수를 생각해보자.

 

그러면, 이는 닿는 지점마다 하나의 "블럭"으로 생각하면 다음과 같은 식을 세울 수 있다. 각 블럭마다 맨 앞과 맨 뒤의 괄호를 제거하면 딕 경로가 되기 때문이다. $f(n, k)$를 위에서 구하려는 수라고 하면

$f(n, k) = [z^n](zD(z))^k = [z^{n-k}]D(z)^k$

이때, $D(z)$는 카탈란 수의 생성함수이다. $D(z) = 1 + zD(z)^2$이  성립하므로

$G(z) = D(z) - 1, \phi(y) = (1+y)^2$

로 두고 위 공식을 적용하면

$[z^m](D(z))^k = [z^m](1 + G(z))^k = \frac{k}{m+k}\binom{2n-k}{n}$

이 된다. 적당한 대입을 통해

$f(n, k) = \frac{k}{2n-k}\binom{2n-k}{n}$

임을 일 수 있다.

 

이를 이용하는 건 이후 후술한다. 암튼 이런게 있다.

3. 번사이드