常见的生成函数封闭形式

· · 个人记录

OGF

\sum\limits_{i=0}x^{ik}\xrightarrow{\bf OGF}\dfrac{1}{1-x^k} \sum\limits_{i=0}c^ix^{ik}\xrightarrow{\bf OGF}\dfrac{1}{1-cx^k} \{1,1,1,1,1,1,\dotsb\}\xrightarrow{\bf OGF}\dfrac{1}{1-x} \{1,a,a^2,a^3,a^4,\dotsb\}\xrightarrow{\bf OGF}\dfrac{1}{1-ax} \{1,1,\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\dotsb\}\xrightarrow{\bf OGF}e^x \{0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\dotsb\}\xrightarrow{\bf OGF}\ln {\dfrac{1}{1-x}}=-\ln{(1-x)} \{\binom{n}{0},-\binom{n}{1},\binom{n}{2},-\binom{n}{3},\dotsb,(-1)^n\binom{n}{n}\}\xrightarrow{\bf OGF}(1-x)^n \{\binom{n}{0},\binom{n+1}{1},\binom{n+2}{2},\dotsb,\binom{n+k}{k},\dotsb\}\xrightarrow{\bf OGF}\dfrac{1}{(1-x)^{n+1}}

EGF

\{1,1,1,1,1,1,\dotsb\}\xrightarrow{\bf EGF}e^x \{1,-1,1,-1,1,-1,\dotsb\}\xrightarrow{\bf EGF}e^{-x} \{1,c,c^2,c^3,\dotsb\}\xrightarrow{\bf EGF}e^{cx} \{1,0,1,0,1,0,\dotsb\}\xrightarrow{\bf EGF}\dfrac{e^x+e^{-x}}{2} e^{cx}&=\sum\limits_{i\ge 0}c^i\dfrac{x^i}{i!}\\ e^{cx}-1&=\sum\limits_{i\ge 1}c^i\dfrac{x^i}{i!}\\ \dfrac{e^{cx}-1}{x}&=\sum\limits_{i\ge 1}c^i\dfrac{x^{i-1}}{i!}\\ &=\sum\limits_{i\ge 0}c^{i+1}\dfrac{x^i}{(i+1)!} \end{aligned}

必要的时候可以去掉常数项，或者化柿子。

比如求自然数幂和。

&\quad\; \sum\limits_{i=1}^ni^k\\ &=\sum\limits_{i=0}^n e^{ix}[\dfrac{z^k}{k!}]-[k=0]\\ &=\dfrac{e^{(n+1)x}-1}{e^x-1}-[k=0]\\ &=\dfrac{e^{(n+1)x}-1}{x}\times \dfrac{x}{e^x-1}-[k=0] \end{aligned}

第三行来自等比数列。

由于 e^x-1 不能求逆，所以上下同乘 x，然后就发现特别好做了。

最后别忘了这是个 \rm EGF，最后要乘 k!。

所以 $\dfrac{F(x)}{1-p^{n+1}x}=\dfrac{F(px)}{1-p^nx}$。 把下面展开，然后拆一个 $p^i$ 塞进生成函数里可以得到。