笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

生成函数乱编

posted on 2020-02-16 23:47:27 | under GF |

好久好久之前的笔记,最近整理了一下又放了上来,企图骗访问量- 我的博客

个人感觉应该是全网最详细的生成函数教程(雾

但是由于当时是分着写的,所以有些记号可能用法不同,最直接的就是下标问题了,但是似乎问题不大?


二项式定理

一点瞎扯

考虑二项式定理 $(x+y)^n=\sum\binom{n}{i}x^iy^{n-i}$,由于展开成了二元多项式的形式,所以存在卷积性质。利用此或可证明一些东西。

一点有趣的证明题

A

证明:$$ \sum_{x=1}^n x\cdot\binom{n}{x}=n\cdot 2^{n-1} $$

考虑一个式子:$\binom{n}{k}=\dfrac{n}{k}\binom{n-1}{k-1}$。那么对于原式的右边就可以化成$$ \begin{aligned} &\sum_{x=1}^n x\cdot\binom{n}{x}\\ =&\sum_{x=1}^n n\cdot \binom{n-1}{x-1}\\ =&n\cdot 2^{n-1} \end{aligned} $$

B

证明$$ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} $$

考虑 $(1+x)^{n+1}$ 的两种展开方式:$$ \begin{aligned} (1+x)^{n+1}=&\sum \binom{n+1}{i+1}x^{i+1}\\ (1+x)^{n+1} =&(1+x)\sum \binom{n}{i}x^{i}\\ =&\sum \binom{n}{i}\left(x^{i}+x^{i+1}\right)\\ =&\sum \left(\binom{n}{i}+\binom{n}{i+1}\right)x^{i+1} \end{aligned} $$ 比较两个多项式中 $i+1$ 项的系数,可知证毕。

形式幂级数

关于 $\dfrac{1}{1-x}$

设该商为 $\sum c_nx^n$。那么有$$ \begin{aligned} 1=(1-x)\sum c_ix^i\\ 1=c_0+\sum(c_i-c_{i-1})x^i\\ \end{aligned} $$ 可知 $c_0=1,c_i=c_{i-1}$ 。所以每一项的系数都为 $1$ 。故有形式幂级数基本定理:$$ 1+x+x^2+x^3\cdots=\dfrac{1}{1-x} $$

一系列求母函数例子

$$ \begin{aligned} \{C_n^{n},C_{n+1}^n,C_{n+2}^{n}\cdots\}&\to\sum \binom{n+i}{n}x^i=\dfrac{1}{(1-x)^{n+1}}\\ \{1,5,25,125\cdots\}&\to\sum 5^ix^i=\sum{5x^i}=\dfrac{1}{(1-5x)}\\ \{0,1\times 2,2\times 3,3\times 4\cdots\}&\to\sum (i+1)\cdot i\cdot x^i=\sum x^i\cdot 2\sum_{j=1}^ij=(\sum i\cdot x^i)*(\sum 2x^i)=\dfrac{2}{1-x}\cdot\dfrac{x}{(1-x)^2}\\ \{0,0,0,-1,1,-1,1\cdots\} & \to \sum_{i=3}^{\infty}(-1)^ix^i=x^3\sum(-x)^i=\dfrac{x^3}{1+x}\\ \end{aligned} $$

部分分式

这一章的作用在于把一个复杂的计数问题转化为许多个简单的 $\rm OGF$ 的形式。

预备定理

设 $\dfrac{P(x)}{Q(x)}$ 是一个真分式,$a$ 是 $Q(x)$ 的一个 $k$ 重根,那么存在一个数列 $A_{1\sim k}$ 使得$$ \dfrac{P(x)}{Q(x)}=\sum_{i=1}^k\dfrac{A_i}{(x-a)^i}+\dfrac{P'(x)}{Q'(x)} $$ 其中 $\dfrac{P'(x)}{Q'(x)}$ 依旧是真分式。

懒得证了。感性理解。

部分分式定理

设 $\dfrac{P(x)}{Q(x)}$ 是一个真分式,如果 $a_1,a_2,\cdots a_m$ 分别是多项式 $Q(x)$ 的 $k_1,k_2,\cdots k_m$ 重根。那么存在一张数表 $\mathbf A$ ,使得$$ \dfrac{P(x)}{Q(x)}=\sum_{i=1}^m\sum_{j=1}^{k_i}\dfrac{\mathbf A_{i,j}}{(x-a_i)} $$

由预备定理可知显然。

例题

(1)

分解 $\dfrac{1}{x^3-x^2-x+1}$ 为部分分式。

首先因式分解可以知道 $1$ 是他的二重根,$-1$ 是他的一重根。那么可以根据部分分式定理得到$$ \dfrac{1}{x^3-x^2-x+1}=\dfrac{a}{(x-1)^2}+\dfrac{b}{x-1}+\dfrac{c}{x-1} $$ 两边通分后发现是个恒等式,于是就可以对 $x$ 用特殊值法得到

$$ a=\dfrac{1}{2},b=-\dfrac{1}{4},c=\dfrac{1}{4} $$

然后就没有然后了。

(2)

将分解 $\dfrac{6x^2+22x+18}{x^3+6x^2+11x+6}$ 为部分分式

继续考虑将分母因式分解。即$$ x^3+6x^2+11x+6=(x+1)\cdot (x+2)\cdot (x+3) $$ 那么之后就变成sb题了,分解为 $\dfrac{1}{x+1}+\dfrac{2}{x+2}+\dfrac{3}{x+3}$。

简单组合问题

一般组合问题

设有 $n$ 种不同的物体,分别只能取 $a_1,a_2,a_3\cdots a_n$ 个,如果要取 $r$ 个,有多少种方案。

形式幂级数大概就是$$ \prod _{i=1}^n(1+x+x^2+\cdots+x^{a_i}) $$ 这样。或者考虑一个更特殊的问题,从 $n$ 个不同物品里可以重复地取出 $r$ 个的方案数:$$ \prod_{i=1}^n(1+x+x^2+\cdots)=\dfrac{1}{(1-x)^n} $$ 由上面的形式幂级数展开可以知道,这个东西的第 $r$ 项是 $\binom{n-1+r}{n-1}=\binom{n+r-1}{r}$,是个常见的结论。

砝码模型

设有 $n$ 种砝码,质量分别为 $c_1,c_2\cdots c_n$,分别有 $b_1,b_2\cdots b_n$ 枚,求一共可以称出多少种不同质量的物品。

这个东西的形式幂级数大概是$$ \prod_{i=1}^n (1+x^{c_i}+x^{2\cdot c_i}+x^{3\cdot c_i}+\cdots+x^{b_i\cdot c_i}) $$

不定方程相关

$$ p_1x_1+p_2x_2+\cdots+p_nx_n=r $$ 的非负整数解个数。

很显然是$$ \prod_{i=1}^n (1+x^{p_i}+x^{2\cdot p_i}+\cdots) $$ 这里继续把 $1$ 当作一个物品,每个变量只能拿 $p_i$ 的倍数个就很好理解了。

那么这东西的母函数显然是$$ \dfrac{1}{(1-x^{p_1})(1-x^{p_2})(1-x^{p_3})\cdots(1-x^{p_n})} $$

有关分拆数的拓展

在正整数 $r$ 的所有分拆中, 不超过 $n$ 的有几种?

发现本质上是在求这样一个不定方程$$ 1\cdot x_1+2\cdot x_2+3\cdot x_3+\cdots+n\cdot x_n=r $$ 的非负整数解个数。

那么显然就是 $\dfrac{1}{(1-x)(1-x^2)\cdots(1-x)^n}$

又一个拓展(OI中的应用)

给定 $n$ 和 $c_i(1\leq c_i\leq \rm m)$,求 $0\leq x_i\leq c_i$ 时,$\sum x_i=s$ 的解的数量。

对于前 $30\%$ 的数据,有 $n\leq 16,0\leq m,s\leq 10^9$ 。

对于前 $70\%$ 的数据,有 $n\leq 35,0\leq m,s\leq 10^9$ 。

对于另外 $30\%$ 的数据,有 $1\leq n\leq 5\cdot 10^5,0\leq m,s\leq 100$。

发现大概 $30\%$ 的可以直接大力容斥,最后 $30\%$ 的可以生成函数,中间 $40\%$ 的就需要神秘的 $\rm Meet~in~Middle$ 了。想了想大概就是分成两部分,枚举第二部分的时候顺便乘法原理一下第一部分的结果就完了。

线性循环数列

斐波那契数列通项

考虑斐波那契数列 $\{a_n\}$ 的母函数可以这么得到:$$ \begin{aligned} f(x)=a_0+a_1x+\cdots+a_nx^n+\cdots\\ -xf(x)=-a_0x-a_1x^2-\cdots-a_nx^{n+1}\cdots\\ -x^2f(x)=-a_0x^2-a_1x^3-\cdots-a_nx^{n+2}\cdots\\ \end{aligned} $$ 考虑 ① + ② + ③ 得到:

$$ (1-x-x^2)f(x)=a_0+(a_1-a_0)x+(a_2-a_1-a_0)x^2\cdots $$ 可知$$ f(x)=\dfrac{1}{1-x-x^2} $$ 那么考虑如何展开这个东西。令 $r_1,r_2$ 为方程 $1-x-x^2$ 的两个根。那么有$$ \dfrac{1}{1-x-x^2}=\dfrac{1}{r_2-r_1}\left(\dfrac{1}{x-r_1}-\dfrac{1}{x-r_2}\right) $$ 变一下形:$$ \dfrac{1}{1-x-x^2}=\dfrac{1}{r_2-r_1}\left(\dfrac{1}{r_2\left(1-\dfrac{1}{r_2}x\right)}-\dfrac{1}{r_1\left(1-\dfrac{1}{r_1}x\right)}\right) $$ 然后有一步很神仙的转化。由$$ \begin{aligned} \dfrac{1}{1-\dfrac{1}{r_1}x}=\sum\left(\dfrac{1}{r_1}\right)^ix^i\\ \dfrac{1}{1-\dfrac{1}{r_2}x}=\sum\left(\dfrac{1}{r_2}\right)^ix^i \end{aligned} $$ 得到$$ \dfrac{1}{1-x-x^2}=\sum\left[\dfrac{1}{r_2-r_1}\left(\dfrac{1}{r_2^{i+1}}-\dfrac{1}{r_1^{i+1}}\right)\right]x^i $$ 可知$$ a_n=\dfrac{1}{\left(r_1r_2\right)^n}\cdot\dfrac{r_2^{n+1}-r_1^{n+1}}{r_1-r_2} $$ 继而可以得到$$ a_n=\dfrac{1}{\sqrt 5}\left[\left(\dfrac{1+\sqrt 5}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt 5}{2}\right)^{n+1}\right] $$

一般线性循环数列

由上例可知,对于一个给定的 $k$ 阶线性循环数列,求母函数只需要构造出除了前 $k$ 项之外系数都为 $0$ 的幂级数即可。

比如给定数列 $\{a_n\}$ 满足:

$$ \begin{aligned} &a_0=0,a_1=1,a_2=-1\\ &a_n=-a_{n-1}+16a_{n-2}-20a_{n-3}\quad(n=3,4,5\cdots)\\ \end{aligned} $$

那么考虑构造如下四个:$$ \begin{aligned} f(x)&=a_0+a_1x+\cdots+a_nx^n+\cdots\\ xf(x)&=a_0x+a_1x^2+\cdots + a_nx^{n+1}\cdots\\ -16x^2f(x)&=-16a_0x^2-16a_1x^3-\cdots-16a_nx^{n+2}\cdots\\ 20x^3f(x)&=-20a_0x^3+20a_1x^4+\cdots+20a_nx^{n+3}\cdots\\ \end{aligned} $$ 还是 ① + ② + ③ + ④:$$ \begin{aligned} (1+x-16x^2+20x^3)f(x)=x\\ f(x)=\dfrac{x}{1+x-16x^2+20x^3} \end{aligned} $$ 就完了。

特征多项式

齐次

考虑对于一个以 $\{c_i\}$ 为递推转移的 $k$ 阶线性循环数列 $\{a_i\}$ 的母函数,根据构造似乎可以被写成这样的形式:$$ \dfrac{b_0+b_1x+b_2x^2\cdots b_{m}x^{m}}{1-c_1x-c_2x^2-c_3x^3\cdots -c_kx^k} $$$\{b_i\},m$ 都是根据实际情况会变的参数。

那么可以发现这样的恒等的关系:$$ \begin{aligned} \dfrac{b_0+b_1x+b_2x^2\cdots b_{m}x^{m}}{1-c_1x-c_2x^2-c_3x^3\cdots - c_kx^k}&=a_0+a_1x+a_2x^2\cdots +a_nx^n+\cdots\\ b_0+b_1x+b_2x^2\cdots b_{m}x^{m}&=(a_0+a_1x+a_2x^2\cdots +a_nx^n+\cdots)\times(1-c_1x-c_2x^2-c_3x^3\cdots - c_kx^k)\\ \end{aligned} $$ 即$$ \begin{aligned} &b_0=a_0,\\ &b_1=a_1-c_1a_0,\\ &b_2=a_2-c_1a_1-c_2a_0\\ &\cdots,\\ &b_{k-1}=a_{k-1}-\sum_{i=1}^{k-1}c_ia_{k-1-i},\\ &\cdots,\\ &b_p=a_p-\sum_{i=1}^{k}c_i=0\quad \mathrm{if}~(p\geq k) \end{aligned}": $$ 可以发现分子上的多项式至多有 $k-1$ 次.

像这种根据递推方式快速确定的一个线性循环数列母函数的方法,称为特征法。而多项式$$ 1-c_1x-c_2x^2-\cdots c_kx^k $$ 则称为 $\{a_i\}$ 的特征多项式。

e.g.

$$ a_n=a_{n-1}+9a_{n-2}-9a_{n-3},a_0=1,a_1=1,a_2=2 $$

的通项。


首先分解因式$$ (1-x-9x^2-9x^3)=(1-3x)(1+3x)(1-x) $$ 并且观察到 $b_0=1,b_1=0,b_2=-8$。

那么不妨设$$ \dfrac{a}{1-3x}+\dfrac{b}{1+3x}+\dfrac{c}{1-x}=\dfrac{1-8x^2}{1-x-9x^2-9x^3} $$ 解得$$ a=\dfrac{1}{12},b=\dfrac{1}{24},c=\dfrac{7}{8} $$ 那么就可以知道 $\dfrac{1-8x^2}{1-x-9x^2-9x^3}$ 的展开是:$$ \sum_{n=1}^{\infty}(\dfrac{1}{12}\cdot 3^n+\dfrac{1}{24}(-1)^n3^n+\dfrac{7}{8})x^n $$ 那么通项就是$$ a_n=\dfrac{1}{12}\cdot 3^n+\dfrac{1}{24}(-1)^n3^n+\dfrac{7}{8} $$

非齐次

非齐次的话,可以直接把常数构造在系数里,本质上没什么不同的。

例题

(1)用 $1,2,3$ 三个数来构造一个 $n$ 位数。不允许两个 $1$ 相邻,求方案数。

发现如果第一位放 $2$ 或 $3$ ,那么有 $2\cdot a_{n-1}$ 的方案;如果放 $1$,那么第二维只能放 $2$ 或 $3$ ,那么有 $2\cdot a_{n-2}$ 的方案。所以有 $a_n=2a_{n-1}+2a_{n-2}$ 。

(2)有一行方格,每个格子可以放黑色或者白色,白色不能相邻地放。求方案树。

发现还是讨论第一个位置放的是不是白色。$f_n=f_{n-1}+f_{n-2}$ 。

高阶差分

一点定义

定义 $\{a_i\}$ 的一阶差分 $\Delta^1\{a_i\}$ 是这样的数列 $\{a_1-a_0,a_2-a_1,\cdots,a_n-a_{n-1}\}$ 。

那么 $k$ 阶差分指的是 $\Delta^k\{a_i\}=\Delta\{\Delta^{k-1}\{a_i\}\}$ 。

假设一个数列 $\{a_i\}$ 在 $k$ 阶差分时不是全 $0$ 数列,在 $k+1$ 阶差分时是全 $0$ 数列,那么称这个数列为 $k$ 阶等差数列。

一个定理

如果记 $\Delta^k\{a_i\}:\{a_0^{(k)},a_1^{(k)},a_2^{(k)},\cdots,a_n^{(k)}\cdots \}$,那么有:$$ \begin{aligned} a_n^{(k)}&=a_{n+k}-\binom{k}{1}a_{n+k-1}+\binom{k}{2}a_{n+k-2}-\cdots+(-1)^ka^n\\ &=\sum_{i=0}^k(-1)^i\binom{k}{i}a_{n+k-i} \end{aligned} $$

这个显然可以直接归纳。就懒得证了。

$k$ 阶等差数列 $\{a_n\}$ 的前 $n$ 项和。

考虑对于数列 $\{s_n\}$ ,满足 $s_i=\sum_{j=0}^ia_i$,那么发现可以直接让 $\{a_n\}*(\dfrac{1}{1-x})$ 得到 $\{s_n\}$$$ \left(\sum a_nx^n\right)*\left(\sum x^n\right)=\sum_{n=0}^{\infty}\left(\sum_{j=0}^n a_j\right)x=\sum s_nx^n $$ 所以假设 $\{a_n\}$ 的母函数是 $f(x)$,那么 $\{s_n\}$ 的母函数就是 $\dfrac{f(x)}{1-x}$。

那么考虑如何计算 $f(x)$ 。根据性质可知:$$ a_n^{(k+1)}=a_{n+k+1}-\binom{k+1}{1}a_{n+k}+\binom{k+1}{2}a_{n+k-1}-\cdots+(-1)^{k+1}a^n $$ 那么由于 $a_{n}^{(k+1)}=0$ ,所以可以得到:$$ a_{n+k+1}=\binom{k+1}{1}a_{n+k}-\binom{k+1}{2}a_{n+k-1}+\cdots-(-1)^{k+1}a^n $$ 发现本质上 $\binom{k+1}{x}$ 属于常数项。所以可以知道 $\{a_n\}$ 是一个 $k+1$ 个线性循环数列。所以可以用特征法直接求出。

但其实这种方法有时候比归纳要麻烦很多。这种方法主要用来解决一些比较妙的问题。

一点应用

e.g.

给定 $n$ ,求坐标系中 $|x|+|y|=m,(m=0,1,2,3\cdots n)$ 的 $(x,y)$ 点对数。

考虑设 $\{a_i\}$ 表示 $i=m$ 时的方案数,$\{s_i\}$ 即为所求。那么可以知道 $a_i$ 的母函数为:

$$ f(x)=(1+2x+2x^2+2x^3+\cdots +2x^n+\cdots)^2 $$

看上去十分 $easy$,因为每个坐标有$+-$ 两种取值,所以加一个系数 $2$ 。

那么发现可以这么转化:$$ \begin{aligned} f(x)&=(1+2x+2x^2+2x^3+\cdots +2x^n+\cdots)^2\\ &=(1+2x(1+x+x^2+\cdots+x^n+\cdots))^2\\ &=(1+\dfrac{2x}{1-x})^2\\ &=(\dfrac{1+x}{1-x})^2 \end{aligned} $$ 所以 $\{s_n\}$ 的母函数 $f_s(x)$ 为$$ f_s(x)=\dfrac{f(x)}{1-x}=\dfrac{(x+1)^2}{(1-x)^3} $$ 发现 $(1-x)$ 是它的 $3$ 重根,所以有:

$$ f_s(x)=\dfrac{4}{(1-x)^3}-\dfrac{4}{(1-x)^2}+\dfrac{1}{1-x} $$

那么可以展开得到:$$ f_s(x)=\sum_{i=0}^{\infty}\left[4\binom{n+2}{2}-4(n+1)+1\right]x^n $$ 于是可知 $s_n=2n^2+2n+1$ 。

卡特兰数

首先发现卡特兰数的定义式就是$$ a_n=\sum_{k=1}^{n}a_{n-k}a_{k} $$ 那么这东西的母函数大概可以这么求(默认第 $0$ 为位是 $0$ 而不考虑):$$ \begin{aligned} f^2(x)&=\left(\sum a_ix^i\right)^2\\ &= a_1^2x^2+(a_1a_2+a_2a_1)x^3+(a_1a_3+a_2a_2+a_3a_1)x^4\cdots+\left(\sum_{i=1}^{n}a_{i}a_{n-i}\right) x^n+\cdots\\ &=f(x)-a_1x \end{aligned} $$ 那么解一下方程可以得到俩根:$$ f_1(x)=\dfrac{1-\sqrt{1-4x}}{2},f_2(x)=\dfrac{1+\sqrt{1-4x}}{2} $$ 验一下发现应该取 $f_1$.

在不考虑牛顿迭代的情况下,不加证明地给出一个等式:

$$ \sqrt{1+x}=1+\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}}{n 2^{2 n-1}} \binom{2(n-1)}{n-1} x^{n} $$

那么代换一下可以得到:$$ \begin{aligned} \sqrt{1-4 x} &=1+\sum_{n=1}^{\infty} \dfrac{(-1)^{n-1}}{n 2^{2 n-1}} \binom{2(n-1)}{n-1}(-4 x)^{n} \\ &=1+\sum_{n=1}^{\infty} \dfrac{(-1)^{2 n-1}}{n 2^{2 n-1}} 4^{n} \binom{2(n-1)}{n-1} x^{n} \\ &=1-\sum_{n=1}^{\infty} \dfrac{2}{n} \binom{2(n-1)}{n-1} x^{n} \end{aligned} $$ 再带回去得到:$$ f(x)=\sum_{n=1}^{\infty}\dfrac{\binom{2(n-1)}{n-1}}{n} x^n $$ 那么可知卡特兰数第 $n$ 项 $\mathrm{Cat}_n=\dfrac{\binom{2(n-1)}{n-1}}{n}$。

当然一般情况下 $\rm Cat$ 的定义有从 $0$ 开始的,只是把这种方式向前平移了一项而已。

指数型母函数

基础定义

出于需要,定义另一种生成函数,即指数型母函数 $(\mathbf{EGF})$ 。对于数列 $\{a\}$,他的 $\rm EGF$ 是:$$ \sum_{n=0}^{\infty}\dfrac{a_n}{n!}x^n $$

那么可以得出两个 $\rm EGF$ 卷积的结果是:$$ \begin{aligned} \sum_{n=0}^{\infty}\dfrac{a_n}{n!}x^n &= \left(\sum_{n=0}^{\infty}\dfrac{a_n}{n!}x^n\right)\cdot \left(\sum_{n=0}^{\infty}\dfrac{b_n}{n!}x^n\right)\\ &= \sum_{n=0}^{\infty} x^n\sum_{i+j=n}\dfrac{a_ib_j}{i!j!}\\ &= \sum_{n=0}^{\infty} \dfrac{1}{n!}x^n\sum_{i+j=n}\left(a_ib_j\cdot\dfrac{n!}{i!j!}\right)\\ \end{aligned} $$ 可以发现有$$ c_n=\sum_{k=0}^n\binom{n}{k}a_kb_{n-k} $$ 那么之所称之为指数型母函数,则依赖于下面的性质:

$$ e(x)=1+x+\dfrac{x^2}{2!}+\cdots +\dfrac{x^n}{n!}+\cdots $$

可以发现有$$ e(x)e(y)=e(x+y) $$ 证明大概是可以把 $e(y)$ 改写成$$ e(y)=\sum \dfrac{1}{n!}(\dfrac{y}{x})^nx^n $$ 然后$$ \begin{aligned} e(x)e(y)&=\left(\sum \dfrac{1}{n!}x^n\right)\cdot \left[\sum \dfrac{1}{n!}(\dfrac{y}{x})^nx^n\right]\\ &=\sum \dfrac{\sum_{k=0}^n\binom{n}{k}\cdot (\dfrac{y}{x})^k}{n!}x^n\\ &=\sum \dfrac{(1+\dfrac{y}{x})^n}{n!}x^n\\ &=\sum \dfrac{\dfrac{1}{x^n}(x+y)^n}{n!}x^n\\ &=\sum \dfrac{(x+y)^n}{n!}\\ &= e(x+y) \end{aligned} $$ 发现这种性质类似于指数运算的性质,所以称之为指数型母函数。

同时可知,令 $y=-x$ 则有 $e(x)=\dfrac{1}{e(-x)}$ 。

二项式反演

设 $\{a_n\}$ 给定,且$$ b_n=\sum_{i=0}^n\binom{n}{i}(-1)^ia_i $$ 则必有$$ a_n=\sum_{i=0}^n\binom{n}{i}(-1)^ib_i $$

考虑让数列 $\{(-1)^na_n\}$ 的母函数卷上 $e(x)$ 得到:$$ e(x)*\sum\dfrac{(-1)^na_n}{n!}x^n=\sum\dfrac{\sum_{k=0}^n\binom{n}{k}(-1)^ka_k}{n!}x^n=\sum\dfrac{b_n}{n!}x^n $$ 也就是$$ \sum\dfrac{(-1)^na_n}{n!}x^n=\dfrac{1}{e(x)}*\sum\dfrac{b_n}{n!}x^n $$ 因为 $\dfrac{1}{e(x)}=e(-x)$ ,所以有:$$ \sum\dfrac{(-1)^na_n}{n!}x^n=\sum(-1)^n\dfrac{\sum_{k=0}^n\binom{n}{k}(-1)^kb_k}{n!}x^n $$ 对比第 $n$ 项即可得到$$ a_n=\sum_{k=0}^n\binom{n}{k}(-1)^kb_k $$

一个例子

$$ \sum_{k=1}^n(-1)^k\binom{n}{k}\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{k}\right)=-\dfrac{1}{n} $$

首先有一个比较 general 的结论:$$ \sum_{k=0}^n\dfrac{(-1)^k}{k+1}\binom{n}{k}=\dfrac{1}{n+1}\qquad(1) $$ 这是由于$$ \binom{n+1}{k+1}=\dfrac{n+1}{k+1}\binom{n}{k} $$ 那么稍微变一下形态:$$ \sum_{k=0}^n(-1)^k\dfrac{n+1}{k+1}\binom{n}{k}=\sum_{k=1}^{n+1}(-1)^k\binom{n+1}{k}=1+(1-1)^n=1 $$ 移个项就完了。

那么根据这个可以再证明出一个更强一点的结论:$$ \sum_{k=1}^n\dfrac{(-1)^{k-1}}{k}\binom{n}{k}=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}\qquad (2) $$ 考虑直接归纳。不难验证 $n=1$ 成立。那么考虑 $n\to n+1$ 的过程$$ \begin{aligned} &\sum_{k=1}^{n+1}\dfrac{(-1)^{k-1}}{k}\binom{n+1}{k} \\=&\sum_{k=1}^{n+1}\dfrac{(-1)^{k-1}}{k}\left(\binom{n}{k}+\binom{n}{k-1}\right) \\=&\sum_{k=1}^{n}\dfrac{(-1)^{k-1}}{k}\binom{n}{k}+\sum_{k=0}^{n}\dfrac{(-1)^{k+1}}{k}\binom{n}{k} \\=&\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}\right)+\dfrac{1}{n+1} \end{aligned} $$ 其中最后一步用的就是上面的 $(1)$。

那么回到本题,考虑设 $a_0=0, a_n=-\dfrac{1}{n}\quad (n=1,2,3\cdots )$ 。同时设 $b_0=0$,$$ b_n=\sum_{i=0}^n\binom{n}{i}(-1)^ia_i=\sum_{i=0}^n\dfrac{(-1)^{i+1}}{i}\binom{n}{i} $$ 那么根据 $(2)$ 和二项式反演可以得到$$ \begin{aligned} &b_n=\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}\right)\\ &\sum_{k=1}^n(-1)^k\binom{n}{k}\left(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{k}\right)=\sum_{k=1}^n(-1)^kb_k=a_n=-\dfrac{1}{n} \end{aligned} $$

指数型母函数的应用

有限制的可重排列问题

给定 $n$ 个物品,从中取 $r$ 个进行排列,第 $k~(k=1,2,3\cdots m)$ 种物品有 $n_k$ 个,求排列方案数。

首先给出这东西的母函数:$$ f_e(x)=\left(1+x+\dfrac{x^2}{2!}+\cdots+\dfrac{x^{n_1}}{n_1!}\right)*\left(1+x+\dfrac{x^2}{2!}+\cdots+\dfrac{x^{n_2}}{n_2!}\right)*\cdots*\left(1+x+\dfrac{x^2}{2!}+\cdots+\dfrac{x^{n_m}}{n_m!}\right) $$ 考虑这样表示的意义。对于 $f_e(x)$ 的第 $r+1$ 项,有:

$$ [x^r]f_e(x)=\dfrac{x^{d_1}}{d_1!}\cdot\dfrac{x^{d_2}}{d_2!}\cdot\dfrac{x^{d_3}}{d_3}\cdots\dfrac{x^{d_m}}{d_m!} $$ 其中 $\{d_m\}$ 可以看做是满足 $d_1+d_2+\cdots+d_m=r$ 的一组枚举量。

考虑这样做的可行性。首先变一下形$$ \begin{aligned} &[x^r]f_e(x)\\ &=\dfrac{x^{d_1}}{d_1!}\cdot\dfrac{x^{d_2}}{d_2!}\cdot\dfrac{x^{d_3}}{d_3}\cdots\dfrac{x^{d_m}}{d_m!}\\ &=\dfrac{r!}{\prod d_i!}\cdot\dfrac{x^r}{r!} \end{aligned} $$ 发现第 $r+1$ 项的系数 $\dfrac{r!}{\prod d_i!}$,正好是从 $r$ 个物品中,共 $m$ 中,每种分别有 $d_i$ 个,取满 $r$ 个的方案数。所以正确性显然。

例子

用 $1,2,3,4$ 四个数字能组成多少五位数?要求 $1$ 只能出现 $2$ 或 $3$ 次,$2$ 出现 $0$ 或 $1$ 次,$3$ 没有限制, $4$ 出现偶数次。

这个问题的母函数显然就是这个:$$ f_e(x)=\left(\dfrac{x^2}{2!}+\dfrac{x^3}{3!}\right)\cdot \left(1+x\right)\cdot e(x)\cdot \left[1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots+\dfrac{x^{2n}}{(2n)!}+\cdots\right] $$ 考虑一个性质$$ 1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots+\dfrac{x^{2n}}{(2n)!}+\cdots=\dfrac{e(x)+\dfrac{1}{e(x)}}{2} $$ 那么原式就变成了$$ \begin{aligned}f_e(x)&=\left(\dfrac{x^2}{2!}+\dfrac{x^3}{3!}\right)\cdot\left(1+x\right)\cdot e(x)\cdot \dfrac{1}{2}\left(e(x)+\dfrac{1}{e(x)}\right)\\&=\dfrac{e(2x)}{2}\left(\dfrac{x^2}{2!}+\dfrac{x^3}{3!}\right)\cdot\left(1+x\right)+\dfrac{1}{2}\left(\dfrac{x^2}{2!}+\dfrac{x^3}{3!}\right)\cdot\left(1+x\right)\end{aligned} $$ 发现本质上右边不存在 $x^5$ 这一项,所以忽略。

于是最后通过化简可知答案是 $140$ .

伯努利数

定义

考虑用母函数的方式定义。此处直接定义伯努利数的指数型母函数是:$$ \mathbf B=\dfrac{x}{e(x)-1} $$ 那么考虑如何展开。记伯努利数为 $\{B_n\}$。发现移一下项$$ x=\left(B_0+B_1x+\dfrac{B_2}{2!}x^2\cdots\right) * \left(e(x)-1\right) $$ 如果记右边卷出来的结果是 $\{a_n\}$,那么发现$$ a_n=\sum_{k=0}^{n-1}\binom{n}{k}B_k $$ 此处上界为 $n-1$ 的原因是 $\left(e(x)-1\right)_0=0$ ,其余项均为 $1$ 。

比较同次项系数可知

$$ B_0=1, \sum_{k=0}^{n-1}\binom{n}{k}B_k=0\qquad (n=2,3,4\cdots) $$

考虑用这个方程去递推每一项。大致思路是左右两边同时加上 $B_n$ 。$$ \sum_{k=0}^{n}\binom{n}{k}B_k=B_n $$ 然后就可以发现,比如拿 $n=2$ 举例:$$ B_0+2B_1+B_2=B_2 $$ 就可以消掉 $B_2$ 求出 $B_1$。以此类推,每次用 $n$ 可以消出 $B_{n-1}$ 。

一个小性质

考虑 $B_n$ 的性质,发现推出来的大概长这样:$$ \begin{aligned}&B_0=1\\&B_1=-\dfrac{1}{2}\\&B_2=\dfrac{1}{6}\\&B_3=0\\&B_4=-\dfrac{1}{30}\\&B_5=0\\&B_6=\dfrac{1}{42}\\&B_7=0\\&B_8=-\dfrac{1}{30}\\&B_9=0\\&B_{10}=\dfrac{5}{66}\\&\cdots\end{aligned} $$ 发现似乎,除了 $B_1$ 之外,其余 $n$ 为奇数的时候均为 $0$ 。证明考虑:$$ \dfrac{x}{e(x)-1}=\sum \dfrac{B_n}{n!}x^n=1-\dfrac{x}{2}+\sum_{k=2}^{\infty}\dfrac{B_k}{k!}x^k $$ 那么如果令$$ f(x)=\dfrac{x}{e(x)-1}+\dfrac{x}{2} $$ 那么$$ \begin{aligned}f(-x)&=\dfrac{-x}{e(-x)-1}-\dfrac{x}{2}\\&=\dfrac{-x}{\dfrac{1}{e(x)}-1}-\dfrac{x}{2}\\&=\dfrac{-xe(x)}{1-e(x)}-\dfrac{x}{2}\\&=x-\dfrac{x}{1-e(x)}-\dfrac{x}{2}\\&=\dfrac{x}{e(x)-1}+\dfrac{x}{2}\\&=f(x)\end{aligned} $$ 可知 $f(x)$ 是偶函数,那么也就是$$ 1+\sum_{k=2}^{\infty}\dfrac{B_k}{k!}x^k $$ 是偶函数。考虑他是偶函数的条件,当且仅当所有奇次幂系数都为 $0$ 的时候,才会是偶函数。所以可以证明上面的结论。

伯努利多项式

考虑观察下列两个EGF的卷积:$$ \dfrac{x}{e(x)-1}*e(tx) $$ 其中 $t$ 是任意常数。考虑记卷积结果为 $\beta(t)$ 。那么显然$$ \beta_n(t)=\sum_{k=0}^n\binom{n}{k}B_kt^{n-k} $$ 记这样的多项式为伯努利多项式。这个多项式有个很有用的性质:$$ \beta_{n+1}(t + 1)-\beta_{n+1}(t)=t^n(n+1)\qquad(n=0,1,2,3\cdots) $$ 考虑直接做差法证明。首先设出两个式子:

$$ \begin{aligned} \dfrac{xe(tx)}{e(x)-1}&=\sum\dfrac{\beta_n(t)}{n!}x^n\qquad(1)\\ \dfrac{xe((t+1)x)}{e(x)-1}&=\sum\dfrac{\beta_n(t+1)}{n!}x^n\qquad(2)\\ \end{aligned} $$

$(2)-(1)$ 得到$$ \dfrac{xe(tx)[e(x)-1]}{e(x)-1}=\sum\dfrac{\beta_n(t+1)-\beta_n(t)}{n!}x^n $$ 即$$ xe(tx)=\sum\dfrac{\beta_n(t+1)-\beta_n(t)}{n!}x^n $$ 比较系数可知$$ \dfrac{\beta_n(t+1)-\beta_n(t)}{n!}=\dfrac{t^{n-1}}{(n-1)!} $$ 变一下形就可以得到:$$ \beta_{n+1}(t + 1)-\beta_{n+1}(t)=t^n(n+1) $$

用伯努利多项式求自然数的 $k$ 次方和

考虑决定自然数 $k$ 次方的要素在于下标 $n$ 。于是考虑所有自然数的 $k$ 次方和就是这样:$$ (k+1)\mathbf S^{(k)}=\sum_{i=1}^{\infty}\left(\beta_{k+1}(i+1)-\beta_{k+1}(i)\right) $$ 展开之后$$ \mathbf S_n^{(k)}=\dfrac{\left(\beta_{k+1}(n+1)-\beta_{k+1}(1)\right)}{k+1} $$ 也就是$$ \mathbf S_n^{(k)}=\dfrac{1}{k+1}\sum_{r=1}^{k+1}\binom{k+1}{r}B_{k+1-r}(n+1)^{r} $$ 其中 $r=0$ 时减掉了 $\beta_{k+1}(1)$ 这一项。

发现本质上可以 $k\log k$ 用 $\exp$ 来预处理伯努利数,然后就可以 $O(k)$ 算不限制 $n$ 时的 $k$ 次方和了。

emmm似乎预处理也不用 $\rm exp$ ,$e(x)-1$ 直接写出来,然后直接多项式求逆就可以了?

但显然这个方法被线性插值给爆锤了。