ARC110D_FPS
$F_{i}(x) = \sum_{k=0}^{\infty} \binom{k}{A_{i}} x^{k}$ $ G(x) = \prod_{i=1}^{N} F_{i}(x)$
- 下固定の二項係数→負の二項定理:
- $\binom{A+i}{A} = [x^i] \sum_n \binom{A+n}{A}x^n = [x^i]\frac{1}{(1-x)^{A+1}} $
- $i < 0$の時 $\binom{A+i}{A} = 0$ であることから $F_{i}(x) = \sum_{k=0}^{\infty} \binom{k}{A_{i}} x^{k} = \frac{x^{A_i}}{(1-x)^{A_i+1}}$
$S := \sum A_i$
$ G(x) = \prod_{i=1}^{N} F_{i}(x) = \frac{x^S}{(1-x)^{S+N}}$
- 形式的べき級数の係数の部分和:
- $\displaystyle \sum_{i=0}^{k} [x^{i}]F = [x^{k}] \frac{1}{1-x}F$
$X = \sum_{i=}^{M} [x^{i}]G = [x^{M}] \frac{1}{1-x}G = [x^{M}]\frac{x^S}{(1-x)^{S+N+1}}$ $= [x^{M-S}]\frac{1}{(1-x)^{S+N+1}}$
- べき級数→二項係数:
- $[x^B]\frac{1}{(1-x)^{A}} = \binom{A+B-1}{A-1}$
$[x^{M-S}]\frac{1}{(1-x)^{S+N+1}} = \binom{S+N+1+M-S-1}{S+N} = \binom{N+M}{S+N}$
参考