生成函数浅谈

多项式计数杂谈 - command_block 的博客学习总结

二项式

$(1)$ 拆开组合数

$(\binom{n}{m}) = \frac{n!}{m! (n - m)!}$

组合意义就是总共有 $n$ 个物品，我们选择 $m$ 个出来的方案数。

根据组合意义，我们需要有 $0 \leq m \leq n$ 才能保证成立。

一些推论：

对称性 $(\binom{n}{m}) = (\binom{n}{n - m})$
吸收恒等式 $(\binom{n}{m}) = \frac{n}{m} (\binom{n - 1}{m - 1})$

$(2)$ 经典二项式定理

$(x + y)^{k} = \sum_{i = 0}^{k} (\binom{k}{i}) x^{i} y^{k - i}$

注意 $1$ 的幂可能隐藏在求和中。

$(3)$ 递推公式

$(\binom{n}{m}) = (\binom{n - 1}{m}) + (\binom{n - 1}{m - 1})$

证明的话就是考虑新加入一个数到底是放不放的情况。

对于更加复杂的二项式的形式，我们可以考虑通过拆开进行递推得到答案。

一些推论：

平行求和

$\sum_{i = 0}^{n} (\binom{r + i}{i}) = (\binom{r + n + 1}{n})$

上指标求和

$\sum_{i = 0}^{n} (\binom{i}{m}) = (\binom{n + 1}{m + 1})$

下指标求和

$\sum_{i = 0}^{n} (\binom{n}{i}) = 2^{n}$

对称性

奇数项和偶数项分别等于 $2^{n - 1}$ 。

$2^{n - 1} = \sum_{i = 0}^{⌊ \frac{n}{2} ⌋} (\binom{n}{i}) + \frac{1}{2} \times (\binom{n}{\frac{n}{2}}) [n i s e v e n]$

$(4)$ 范德蒙德卷积

$\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i}) = (\binom{n + m}{k})$

本质上就是 $(1 + x)^{n} \times (1 + x)^{m} = (1 + x)^{n + m}$ 。

或者从组合意义上理解也是一样的，就是在两个集合选 $k$ 个数的方案。

$(5)$ 广义二项式系数 + 广义二项式定理

定义广义二项式系数： $(\binom{n}{m}) = \frac{n^{\underset{―}{m}}}{m!}$ 。

这样我们就有：

$(x + y)^{a} = \sum_{i \geq 0} (\binom{a}{i}) x^{i} y^{a - i}$

广义二项式定理衍生技巧：

上指标反转：

$(\binom{n}{m}) = (\binom{m - n - 1}{m}) (- 1)^{m}$

取一半：处理 $(\binom{2 n}{n})$ 形组合数。

我们考虑两个下降幂的乘积：

$x^{\underset{―}{k}} (x - \frac{1}{2})^{\underset{―}{k}} = x (x - \frac{1}{2}) (x - 1) \dots (x - k + 1) (x - k + \frac{1}{2})$

考虑加倍操作得到：

$x^{\underset{―}{k}} (x - \frac{1}{2})^{\underset{―}{k}} \times \frac{1}{2^{2 k}} = \frac{(2 x)^{\underset{―}{2 k}}}{2^{2 k}}$

我们两边同时除以 $(k!)^{2}$ 得到：

$(\binom{x}{k}) (\binom{x - \frac{1}{2}}{k}) = (\binom{2 x}{2 k}) (\binom{2 k}{k}) \times \frac{1}{2^{2 k}}$

说句实话这里 $c o m m a n d - b l o c k$ 写错了。

考虑带入 $x = n, k = x$ 可以得到等式：

$(\binom{n - \frac{1}{2}}{n}) = (\binom{2 n}{n}) \times \frac{1}{2^{2 n}}$

也就是：

$(\binom{- \frac{1}{2}}{n}) \times 2^{2 n} \times (- 1)^{n} = (\binom{2 n}{n})$

最终得到：

$(\binom{- \frac{1}{2}}{n}) \times (- 4)^{n} = (\binom{2 n}{n})$

可以求出 $\sum_{i = 0} (\binom{2 i}{i}) z^{i}$ 的封闭形式：

$\sum_{i = 0}^{\infty} (\binom{- \frac{1}{2}}{i}) \times (- 4 z)^{i} = (1 - 4 z)^{- \frac{1}{2}}$

$(6)$ 下降幂和上升幂的二项式定理

$(x + y)^{\underset{―}{a}} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{\underset{―}{i}} y^{\underset{―}{a - i}} (x + y)^{\overset{―}{a}} = \sum_{i = 0}^{n} (\binom{n}{i}) x^{\overset{―}{i}} y^{\overset{―}{a - i}}$

$(7)$ 二项式反演

见二项式反演。

$(8)$ 差分和前缀和

前缀和：乘以一个全是 $1$ 的多项式，也就是 $\frac{1}{1 - z}$ 。

差分：乘以 $1 - z$ 。

$(9)$ 牛顿级数

暂时不是很会，等会了再说，感觉不是很难。

$(10)$ 生成函数和杨辉三角

考虑二元生成函数的形式：

$\begin{aligned} G [n, m] & = (\binom{n}{m}) \\ G (x, y) & = \sum_{i = 0} \sum_{j = 0} (\binom{i}{j}) x^{i} y^{j} \\ G (x, y) & = \sum_{i = 0} x^{i} (y + 1)^{i} \\ G (x, y) & = \sum_{i = 0} (x y + x)^{i} \\ G (x, y) & = \frac{1}{1 - x - x y} \end{aligned}$

令 $y = x^{k}$ 则

$\begin{aligned} G (x, y) & = [x^{n}] \sum_{i = 0} \sum_{j = 0} (\binom{i}{j}) x^{i} y^{j} \\ = [x^{n}] \sum_{i = 0} \sum_{j = 0} (\binom{i}{j}) x^{i} x^{j k} \\ = \sum_{i + j k = n} (\binom{i}{j}) \end{aligned}$

同理如果 $x = y^{k}$ 同样可以得到 $[x^{n}] G (x, y) = \sum_{k i + j = n} (\binom{i}{j})$ 。

生成函数技巧

$(1)$ 特征方程

如果有递推方程 $f (n) = a f (n - 1) + b f (n - 2)$ 。

设 $x^{2} = a x + b$ 解得两个根 $x_{0}, x_{1}$ 。

我们断言 $f (n) = A x_{0}^{n} + B x_{1}^{n}$ 。

我们带入初始给定的值即可解得方程。

$(2)$ 构造系数的技巧

平移 $[x^{n}] F (x) x^{t} = F [n - t]$ 。
伸缩 $F (x^{k}) \leftarrow< F [0], \overset{k - 1 个 0}{\overset{⏞}{0, 0, \dots, 0, 0}}, F [1], \overset{k - 1 个 0}{\overset{⏞}{0, 0, \dots, 0, 0}} >$ 。

$(3)$ 生成函数系数的获取

考虑通过求导和平移用 $F (x)$ 表示 $F^{'} (x) x$ ，然后得到与 $F (x), F^{'} (x)$ 的递推式。

考虑将其表示成系数的形式显然有 $F^{'} [n] = (n + 1) F [n + 1]$ 。

带入即可得到递推式。

可以考虑例题 [MtOI2018] 情侣？给我烧了！（加强版）

其中求 $D (x)$ 的时候可以使用该方法。

所以我才能切了这题。

当然如果你得到通向了之后可以暴力展开。

或者考虑对于比较复杂的部分 $\frac{C + \sqrt{x}}{x}$ 这样的情况，我们可以考虑分步进行计算。

考虑设 $G (x) = \sqrt{x}$ 我们先求出 $G$ 的递推式，之后可以得到 $F$ 关于 $G$ 的式子，之后就可以直接得出答案了。

例题 1：

$F (x) = \frac{1 - x - \sqrt{1 - 6 x + x^{2}}}{2 x}$

求其递推式。

设 $G (x) = \sqrt{1 - 6 x + x^{2}}$

可以知道 $G^{'} (x) = \frac{1}{2} (1 - 6 x + x^{2})^{- \frac{1}{2}} \times (- 6 + 2 x)$

我们两边同时乘以 $1 - 6 x + x^{2}$ 。

可以得到 $G^{'} (x) (1 - 6 x + x^{2}) = G (x) \times (x - 3)$ 。

也就是 $g^{'} [n] - 6 g^{'} [n - 1] + g^{'} [n - 2] = g [n - 1] - 3 g [n]$ 。

根据我们之前的式子 $g^{'} [n] = g [n + 1] (n + 1)$ 。

可以知道 $g [n + 1] (n + 1) - 6 n g [n] + (n - 1) g [n - 1] = g [n - 1] - 3 g [n]$ 。

整理之后得到：

$\begin{aligned} g [n + 1] & (n + 1) - (6 n - 3) g [n] + (n - 2) g [n - 1] = 0 \\ g [n + 1] & = \frac{1}{n + 1} (6 n - 3) g [n] - (n - 2) g [n - 1] \end{aligned}$

初值什么的就自己看了。

之后考虑 $F (x) = \frac{1 - x - G (x)}{2 x}$ 。

可以得到 $2 x F (x) = 1 - x - G (x)$ 。

发现前面的 $1 - x$ 本质上只和 $f (1)$ 有关。

所以得到 $2 f (n) = g (n + 1)$ 。

$(4)$ 生成函数的组合意义

$e x p$ 表示有标号无交集合 $(E G F)$ 的拼接，注意我们可以通过钦定根的情况直接使用 $e x p$ 来得到一些有根的图或者树。
$l n$ 这个就是 $e x p$ 的逆操作同样也是 $(E G F)$ ，也就是将一个集合分成若干个不相交的集合，常见的应用就是将无向图变成连通的。

这个操作应该是由连通图推到无向图，之后再取对数得到的。

而不是本来 $l n$ 的意义！！

对于 $O G F$ 加法和乘法的意义：

加法：本质就是两个不相交集合的并。
乘法：本质就是两个不相交集合的笛卡尔积。
$(5)$ 多项式复合：

直接举一个例子，设 $F (z) = \sum_{i \geq 0} \frac{z^{i}}{i!}$ 。

那么显然有 $F (G (z)) = \sum_{i \geq 0} \frac{G^{i} (z)}{i!}$ ，也就是将原来的 $z$ 替换成了 $G (x)$ 。

例题：大朋友和多叉树

我们考虑使用生成函数 $[z^{n}] F (z)$ 表示权值为 $n$ 的答案。

我们考虑转移的时候要么是可以直接增加一个叶子节点贡献是 $1$ ，要么是按照题目要求枚举一下度数进行乘积。

可以得到方程 $F (z) = z + \sum_{d \in D e g} F^{d} (z)$ 。

我们移项得到 $F (z) - \sum_{d \in D e g} F^{d} (z) = z$

我们设 $G (z) = z - \sum_{i \geq 0} [d \in D e g] z^{i}$ 。

直接带入得到 $G (F (z)) = x$ 。根据下文的拉格朗日反演可以得到答案。

$(6)$ 解决复合的方法 $-$ 拉格朗日反演

网上证明还是比较多的，就不证明了。

留作练习。

如果有 $F (G (z)) = G (F (z)) = x$ 。不妨拿 $F (G (z))$ 当做例子，我们可以得到：

$\begin{array}{r} G (z) = \frac{1}{n} [z^{n - 1}] (\frac{z}{F (z)})^{n} \end{array}$

$注意$ 我们不能只拘泥于这种形式，其本质是：

$\begin{array}{r} G (z) = \frac{1}{n} [z^{- 1}] \frac{1}{F^{n} (z)} \end{array}$

我们上面进行平移是为了保证其能用整数来表示出来，注意我们对于 $F$ 需要进行平移直到第一项非零为止，所以这个 $- 1$ 本质上就是减去向左平移的位置，之后 $n$ 就是单纯来平衡的。

证明的话考虑我们之前说的，对于复合之后的函数进行求导和平移即可。

$(7)$ 解决复合的方法 $-$ 扩展拉格朗日反演

主要是感觉写到一起不是很明显，但是事实上这个东西的用处更大一些。

$\begin{array}{r} H (F (z)) = \frac{1}{n} [z^{n - 1}] (\frac{z}{G (z)})^{n} H^{'} (z) \end{array}$

$(8)$ 常用的多项式形式

$\begin{aligned} \frac{1}{1 - z} & = \sum_{i \geq 0} z^{i} \\ e^{z} & = \sum_{i \geq 0} \frac{z^{i}}{i!} \\ \frac{1}{(1 - z)^{m}} & = \sum_{i \geq 0} (\binom{i + m - 1}{i}) z^{i} \\ \frac{e^{z} + e^{- z}}{2} & = \sum_{i \geq 0} \frac{z^{2 i}}{(2 i)!} \\ \frac{e^{z} - e^{- z}}{2} & = \sum_{i \geq 0} \frac{z^{2 i + 1}}{(2 i + 1)!} \\ \int \frac{1}{1 - z} = \ln \frac{1}{1 - z} & = \sum_{i \geq 1} \frac{z^{i}}{i} \\ \int \frac{1}{1 + z} = \ln (1 + z) & = \sum_{i \geq 1} \frac{(- 1)^{i - 1} z^{i}}{i} \end{aligned}$

其实我们还可以将 $z$ 替换成 $a z$ 这样就变成了 $a^{i} z^{i}$ 了。

$(9)$ 生成函数求通向

根据上文的一些套路，您肯定可以将一些简单的递推式子得到通向了。

但是如果比较复杂怎么办，比如说斐波那契数列就是我们不能直接看出来的数列。

当然您可以通过我们最早提起的特征方程来解决这个问题。

我们知道 $F i b (z) = \frac{z}{1 - z - z^{2}}$ 。

$(1)$ 直接拆分成和 $z$ 一次项有关的式子

$\begin{aligned} F i b (z) & = \frac{z}{1 - z - z^{2}} \\ = \frac{1}{\sqrt{5}} (- \frac{1}{1 - \frac{1 - \sqrt{5}}{2} z} + \frac{1}{1 - \frac{\sqrt{5} + 1}{2} z}) \end{aligned}$

发现里面的式子本质上和 $\frac{1}{1 - a z}$ 是一样的，根据加法原理我们直接可以得到：

$\begin{array}{r} F i b (z) = \frac{1}{\sqrt{5}} (- {(\frac{1 - \sqrt{5}}{2})}^{n} + {(\frac{1 + \sqrt{5}}{2})}^{n}) \end{array}$

$(2)$ 使用牛顿二项式定理

我们考虑一个常见的卡特兰数的生成函数 $C (z) = \frac{1 - \sqrt{1 - 4 z}}{2 z}$ 。

我们不用考虑左边的部分直接使用牛顿二项式定理展开 $\sqrt{1 - 4 z}$ 。

$\begin{aligned} \sqrt{1 - 4 z} & = \sum_{i \geq 0} (\binom{\frac{1}{2}}{i}) (- 4 z^{i}) \\ = - \sum_{i \geq 0} \frac{(2 i - 2)!}{(i - 1)! 2^{2 i - 1} i!} 4^{i} z^{i} \\ = - 2 \sum_{i \geq 0} \frac{(2 i - 2)!}{(i - 1)! i!} z^{i} \\ C (z) & = \sum_{i \geq 0} \frac{(\binom{2 i}{i})}{i + 1} z^{i} \end{aligned}$

我们注意一下，我们对于 $\sqrt{1 - 4 z}$ 可以拆出来第一项与 $1$ 相消除。

$(3)$ 构造拉格朗日反演的形式

上面的那种太麻烦了，我们能不能有快一点的做法。

对于卡特兰数有 $C (z) = 1 + z C^{2} (z)$ 成立，我们考虑直接进行构造。

首先进行移项得到 $\frac{C (z) - 1}{C^{2} (z)} = z$ 已经符合了反演的一个条件，很简单我们构造 $F (z) = \frac{z - 1}{z^{2}}$ 即可，那么 $F (C (z)) = z$ 进行反演得到。

$\begin{aligned} C (z) & = \frac{1}{n} [z^{n - 1}] (\frac{z}{F (z)})^{n} \\ = \frac{1}{n} [z^{n - 1}] (\frac{z^{3}}{z - 1})^{n} \end{aligned}$

右边进行展开可以得到：

$\begin{aligned} (\frac{z^{3}}{z - 1})^{n} & = z^{3 n} \sum_{i \geq 0} (\binom{i + n - 1}{i}) (- 1)^{i} z^{i} \\ [z^{n - 1}] (\frac{z^{3}}{z - 1}) & = (\binom{- n - 2}{- 2 n - 1}) \times (- 1)^{- 2 n - 1} \end{aligned}$

但是你会发现二项式系数下面是 $- 2 n - 1$ 是不行的，我们考虑对于原来的 $F$ 稍作改动。

也就是需要将 $z - 1$ 消掉即可，很简单我们让 $z - 1 \to z$ 也就是让 $z$ 加 $1$ 。

设 $F (z) = \frac{z}{(1 + z)^{2}}$ 那么我们有 $F (C (z) - 1) = z$ 。

$\begin{aligned} (C (z) - 1) & = \frac{1}{n} [z^{n - 1}] (\frac{z}{F (z)})^{n} \\ = \frac{1}{n} [z^{n - 1}] (z + 1)^{2 n} \\ = \frac{(\binom{2 n}{n - 1})}{n} \\ = \frac{(\binom{2 n}{n})}{n + 1} \end{aligned}$