積の和典型を形式的べき級数(FPS)で考える - クリプトHFTとか競プロとか

積の和典型の問題設定
FPS(形式的べき級数)で考える方法

積の和典型の問題設定

問題設定は
積の和典型 - ei1333の日記がわかりやすいです。
長さが $N$ 、総和が $M$ の非負整数からなる数列の総積の和を求める問題です。

数え上げと対応させて考える方法が他のサイトで紹介されています。
参考:積の和典型 - Shirotsume の日記,
積の和典型 - ei1333の日記

FPS(形式的べき級数)で考える方法

$f =0 \cdot x^0 + x + 2x^2 + 3x^3 + 4x^4 \dots$
とします。
$f^N$ の各項の次数が選ばれた項の和、係数が選ばれた項の積(の和)*1を表します。
$[x^M] f^N$ が求める答えです。
$f = x(1 + 2x + 3x^2 + \dots) = \frac{x}{(1-x)^2}$ *2
ですから、 $[x^M] f^N =[x^M] \frac{x^N}{(1-x)^{2N}} = [x^{M-N}] (1-x)^{-2N}$ となります。

負の二項定理から
$\frac{1}{(1-x)^A} = \sum_{k=0}^\infty {}_{A+k-1} \mathrm{C}_{A-1} \cdot x^k$
なので、求める答えは
$[x^{M-N}] \frac{1}{(1-x)^{2N}} = {}_{2N + M-N - 1}\mathrm{C}_{2N - 1} \\ = {}_{N+M - 1}\mathrm{C}_{2N - 1}$
となります(おわり)

*1:N個選ぶ選び方は色々ありますが、そのすべての選び方について「選んだ項の総積」を求めて、それらをすべて足し合わせたもの

*2: $\frac{1}{1-x}$ をかけることが累積和を取ることに対応するのを考えるとわかりやすいですね。 $1, 2, 3, \dots$ という数列が、 $1, 1, 1, \dots$ という数列の累積和であることと、 $1,1, 1, \dots$ という数列の母関数が $\frac{1}{1-x}$ だからです。