生成函数乱编

· · 个人记录

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

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

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

二项式定理

一点瞎扯

考虑二项式定理 (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} 那么可以发现这样的恒等的关系： $$ \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} $$ \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$ 直接写出来，然后直接多项式求逆就可以了？ 但显然这个方法被线性插值给爆锤了。