初学多项式与生成函数笔记 Part II

生成函数初步 Ⅱ

1. 形式幂级数扩展

鉴于本人完全没学过微积分，这里简单记一下几个重要的结论。应该全是错的。

导数与积分

记 \(f(x)\) 的导数为 \(f'(x)\)。

对于形式幂级数 \(f(x)=a_0+a_1x+a_2x^2+\cdots\)，定义其形式导数为 \(f'(x)=a_1+2a_2x+\cdots+na_nx^{n-1}+\cdots\)。

定义 \(f(x)+C\) 为 \(f'(x)\) 的不定积分，对于 \(f(x)\) 的不定积分，记作 \(\int f(x)\text d x\)。

对于形式幂级数 \(f(x)=a_0+a_1x+a_2x^2+\cdots\)，定义其形式不定积分为 \(\int f(x)\text d x=a_0x+\dfrac {a_1} 2 x^2+\cdots+\dfrac{a_{n-1}}nx^n\)。

一些初等函数的导数。

• \((C)'=0\)，\(C\) 为常数。
• \((x^n)'=nx^{n-1}\)。
• \((\text e^x)'=(\exp x)'=\exp x\)，即求导为其自身。
• \((\ln x)'=\dfrac 1 x\)。
• \((\sin x)'=\cos x\)。
• \((\cos x)'=-\sin x\)。

一些求导的性质：

• 线性性

\((f(x)+g(x))'=f'(x)+g'(x)\)，且有 \((c\cdot f(x))'=c\cdot f'(x)\)。

• 乘法法则

\((f(x)g(x))'=f'(x)g(x)+f(x)g'(x)\)。

这个结构是不是有点熟悉，\(\sin\) 的合角公式跟它相通。

• 链式法则（复合函数求导）

有 \((g\circ f)'(x)=g'(f(x))\cdot f'(x)\)。

2. \(\exp\) 与 \(\ln\)

先介绍一个叫泰勒展开的东西，这里记 \(f^{(n)}(x)\) 为 \(f(x)\) 的 \(n\) 阶导，则有。

\[\boxed{f(x)=\sum_{i=0}\frac{f^{(i)}(a)}{i!}(x-a)^i} \]

比方说，你把 \(f(x)\) 换成 \(\exp(x)\)，再代个 \(a=0\) 进去，你惊喜的发现它就变成

\[\exp(x)=\sum_{i=0}\frac{x^i}{i!} =1+x+\frac{x^2}{2!}+\cdots+\frac{x^n}{n!}+\cdots \]

这下看懂了。

假如说我们要泰勒展开 \(\ln(x)\)，你发现这下不能代 \(a=0\) 了，因为真数大于 \(0\)，那我们代个 \(1\) 吧。

注意这里 \(\ln^{(n)}(x)=(-1)^{n-1}(n-1)!x^{-n}\)，自己推一下就能出来，则 \(\ln^{(n)}(1)=(-1)^{n-1}(n-1)!\)。

代入有

\[\begin{align} \ln(x)&=\sum_{i=1}\frac{(-1)^{i-1}(i-1)!}{i!}(x-1)^i\\ &=\sum_{i=1}\frac{(-1)^{i-1}}{i}(x-1)^i\\ &=(x-1)-\frac{(x-1)^2}{2}+\frac{(x-1)^3}{3}-\cdots \end{align} \]

当然这个不常用，我们常用的是这个：

\[\ln(1+x)=\sum_{n=1} \frac{(-1)^{n-1}}{n}\cdot x^n=x-\frac{x^2}2+\frac{x^3}{3}-\cdots \]

设有形式幂级数 \(f(x)\)，可以定义 \(\exp(f(x))\)。

若形式幂级数 \(f(x)\) 常数项 \([x^0]f(x)=0\)，才可以定义与 \(\ln(1+f(x))\)。

当然若 \([x^0]f(x)=1\)，可以定义 \(\ln(f(x))\)。

小学知识告诉我们 \(\ln\) 和 \(\exp\) 互为反函数，因此

\[g(x)=\exp(f(x))\Leftrightarrow f(x)=\ln(g(x)) \]

---

怎么求 \(\ln(f(x))\)？

我们先求导，你会发现有

\[(\ln(f(x)))'=f'(x)\cdot \frac 1 {f(x)} \]

左边这个求导，右边这个求个逆，乘起来再积分即可。

怎么求 \(\exp(f(x))\)，我们这里用牛迭，假设 \(g(x)=\exp(f(x))\)，则能构造出来 \(\ln(g(x))-f(x)=0\)。于是我们设 \(h(x)=\ln(x)-f\)，则有

\[0\equiv h(g)\equiv h(g_0)+h'(g_0)(g-g_0)\pmod{x^{2n}} \]

变形：

\[g\equiv g_0-\frac{h(g_0)}{h'(g_0)}\equiv g_0-\frac{\ln(g_0)-f}{\frac 1 {g_0}}\equiv g_0(1-\ln(g_0)+f) \]

在求 \(\exp(f(x))\) 时，我们一般保证 \([x^0]f(x)=0\)，因此初值为 \([x^0]g(x)=1\)，倍增即可。

来个例题。

例 1x42.1

有 \(n\) 种体积为 \(v_i\) 的物品，每种物品有无穷多个，求出凑成 \(1\sim m\) 的体积的总方案数，对 \(19260817\) 取模。

\(1\le n,m,V\le 5\times 10^4\)

容易对每种物品构造出生成函数，即

\[f_i(x)=1+x^{v_i}+x^{2v_i}+\cdots=\frac 1{1-x^{v_i}} \]

那么最终答案的生成函数就是

\[f(x)=\prod_{i=1}^n f_i(x)=\prod_{i=1}^n \frac{1}{1-x^{v_i}} \]

这个式子非常难拆，因此我们考虑通过 \(\ln\) 把乘法转化成加法。可以知道 \(\ln f(x)\) 就是

\[\ln f(x)=\sum_{i=1}^n\ln \frac1{1-x^{v_i}}=-\sum_{i=1}^n\ln(1-x^{v_i})=\sum_{i=1}^n\sum_{j\ge 1}\frac{x^{v_ij}}{j} \]

即

\[\ln f(x)=\sum_{k=1}^m\sum_{j\ge1,kj\le m}\frac{x^{kj}}{j}\cdot \#[v_i=k] \]

\(\#[v_i=k]\) 表示等于 \(k\) 的 \(v_i\) 的数量，这玩意直接枚举，是调和级数，时间复杂度 \(O(m\log m)\)，最后对其求 \(\exp\) 即可。

这题很呃呃的点在于模数，懒的写。

3. 第二类斯特林数

这个学过很多遍了，不妨整理一下。

首先第二类斯特林数表示的是，将 \(n\) 个有标号球分配到 \(k\) 个无标号盒子，且盒子不能为空的方案数，记作 \(S_2(n,k)\) 或 \(\begin{Bmatrix}n\\ k\end{Bmatrix}\)。

公式 1：递推关系

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix} \]

dp 意义，第 \(n\) 个球既可以新开一个盒子，还可以从原来就有的 \(k\) 个盒子中选择一个放进去。

公式 2：通项公式

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n \]

容斥！先考虑盒子有标号，然后考虑钦定 \(i\) 个盒子为空盒的方案，那就为 \(\dbinom k i(k-i)^n\)。容斥一下除以 \(k!\) 即可。

公式 3：普通幂转下降幂

方便和组合数联动，推式子。

\[x^n=\sum_{k=0}^n \begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}} \]

直接考虑组合意义，左边代表 \(n\) 个元素，在 \(x\) 个盒子中随便选一个放，右边就是在枚举有几个盒子要放球，然后再乘上 \(x\) 个盒子里选 \(k\) 个盒子出来排列的方案数。

公式 4：关于 \(n\) 的指数生成函数

\[\sum_{n\ge 0}\begin{Bmatrix}n\\k\end{Bmatrix}\frac{x^n}{n!}=\frac 1{k!}(\exp(x)-1)^k \]

依旧考虑组合意义，我们给每个盒子一个标号，这样就有了盒子 \(1\) 到盒子 \(k\)，然后此时又有球 \(1\) 到球 \(n\)。这就相当于我们用 \(k\) 种颜色给这 \(n\) 个球染色，且每个颜色至少出现一次的方案数。

显然对于每个颜色的 EGF 为

\[\hat{f_i}=\sum_{n\ge 1}\frac{x^n}{n!}=\exp(x)-1 \]

则最后盒子有标号的答案的 EGF 为

\[F=(\exp(x)-1)^k \]

最后转成无标号的，乘个 \(\frac{1}{k!}\) 即可。

---

第二类斯特林数·行

拆开通项公式的组合数。

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n=\sum_{i=0}^k \frac{(-1)^i}{i!}\cdot \frac{(k-i)^n}{(k-i)!} \]

和一定，卷起来即可。

第二类斯特林数·列

设 \(F=\exp(x)-1\)，则答案为

\[\begin{Bmatrix}n\\k \end{Bmatrix}=\frac{n!}{k!}[x^n]F^k(x) \]