生成函数趣题三则

大家好我是渡鸦，好像这周悟理停更了，正好我放假了我更一期。

今天的文章里我来简单介绍一下生成函数的概念，之后会用它解决三道具有一定代表性的例题。

（出于阅读的连贯性考虑，以下是很基础的介绍，可以跳过不看）

生成函数，或者也叫做“母函数”，就是可以包含下某个数列的全部信息的函数的统称。通常说来生成函数都会比它所代表的数列包含一些甚至许多更好用的性质，然后我们就可以利用这些额外的性质来得到一些关于数列本身的结论。

这篇文章里主要要介绍的是生成函数里被称作形式幂级数的一类亚种，简单点说就是多项式：如果原始的数列是 \((a_0,a_1,a_2,a_3,\dots)\)，那么它的生成函数就是\[f(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots\]

把一个数列写成这样能带来的一个好性质就是多项式乘法，最简单的一个例子是二项式定理，它的经典证明是这样的：如果我们要展开 \((1+x)^n\)，那么得到的 \(x^k\) 项系数来自于对每一种 “能从 \((1+x)^n\) 的乘积里的每个括号里挑一项 \(c_ix^{p_i}\)，并且乘出来的 \((c_1x^{p_1})(c_2x^{p_2})\dots(c_nx^{p_n})\) 正好是个 \(x^k\) 项” 的方式求和。很巧在这里因为每一项都是 \((1+x)\)，所以挑出来的 \(c_ix^{p_i}\) 的系数都是1，而且次数只有0或1两种可能。那么如果想求 \(x^k\) 项系数，就首先要找到所有能使 \(p_1+p_2+\dots+p_n=k\) 且每个 \(p_i\) 都是0或1的方式，并且每找到一次都要给手里在记录的这个系数加1，这就等效于求所有\(n-k\) 个0和 \(k\) 个1的排列方式，也就是 \(C_n^k\) 或者也写作 \(n \choose k\) 了。

在后面我们会见到相对来说更复杂的多项式乘积，但是分析那些的方法和上面这一段里的思路都是一样的。

说回二项式定理，这里实际上隐藏着一个等比数列的求和公式：我们令 \(n=-1\)，再代入 \(x=-z\)，那么 \((1+x)^n\) 就变成了 \(\frac{1}{1-z}\)，其中每个 \(C_{n}^{k}\,x^k\) 项会变成 \(C_{-1}^{k}(-1)^kz^k\)，让我们看看这个系数可不可以化简：

\[\begin{align*}&\phantom{=~}C_{-1}^{k}\,(-1)^k\\[3px]
&=\frac{(-1)(-2)\dots(-k)}{(k)(k-1)\dots(1)}(-1)^k\\[3px]
&=1\end{align*}\]

我们毫不惊讶地发现每个 \(z^k\) 项系数都是1，因此有了以下的结论：\[\frac{1}{1-z}=1+z+z^2+z^3+\dots\]

如果继续代入 \(z=x^r\)，其中 \(r\) 可以是任意常数，就可以得到一个稍微更普适一点的写法：\[\frac{1}{1-x^r}=1+x^r+x^{2r}+\dots\]

我们将在之后用到这个结论。

---

 

好了闲话就讲到这里，我们上主菜：

第一题：请构造两个六面的色子（骰子），这两个之间可以不相同，但要使得它们每一面都有正整数个点，并且在扔出之后，两个色子点数的和跟两个正常的色子（从一到六）有相同的概率分布。

解：一个正常的六面色子的生成函数可以这样定义：

\[d_6(x)=\frac16(x^1+x^2+x^3+x^4+x^5+x^6)\]

于是每个 \(x^n\) 的系数就是n个点正面朝上的概率，也就是六分之一。两个色子扔出的和的概率分布是什么呢？对啦就是 \(\big(d_6(x)\big)^2\)，原因是这个平方里的 \(x^n\) 项系数是所有能在指数上相加组成这一项的对应概率的乘积之和，也就是扔出n的概率。因此同理如果我们要构造两个新的色子 \(d_A\) 和 \(d_B\)，那么首先就得满足 \(d_A\cdot d_B=(d_6)^2\)。

这里实际上还有两个隐藏的条件：两个色子都是六面的，还有每一面上都必须是正整数。所以不妨把 \(\frac16\) 都先挪到等式另一侧，类比着 \(d_6\) 的生成函数，我们要让 \(6d_A\) 和 \(6d_B\) 也都同时等于6个 \(x\) 的幂之和。有了这些条件就可能会想到下一步需要 \((6d_6)^2\) 的因式分解了。依次用等比数列求和、平方差和立方差公式就不难得出：

\[\Big(6d_6(x)\Big)^2=x^2(x+1)^2\left(x^2+x+1\right)^2\left(x^2-x+1\right)^2\]

事实上，这里的 \(x\) 负责给两个色子清空常数项，\((x+1)\) 和 \((x^2+x+1)\) 分别给 \(x=1\) 时的函数值提供2和3两个质因数（注意 \(x\) 取1的时候函数就是在计数它自己的项数(！)），所以这些因子都是必须每个色子各占一个的，但是最后的 \((x^2-x+1)\) 没有任何作用，是可以随意摆布的。于是可以把这两个因子全都分配给 \(d_B\)，得到如下两个色子：

\[\left\{\begin{align*}&d_A(x)=\frac16(x^1+2x^2+2x^3+x^4)\\[3px]
&d_B(x)=\frac16(x^1+x^3+x^4+x^5+x^6+x^8)\end{align*}\right.\]

把加法表写出来之后就不难发现这个概率分布确实是我们想要的了：

\[\begin{array} {r|cccccc}
&1&2&2&3&3&4\\\hline
1&2&3&3&4&4&5\\
3&4&5&5&6&6&7\\
4&5&6&6&7&7&8\\
5&6&7&7&8&8&9\\
6&7&8&8&9&9&10\\
8&9&10&10&11&11&12\end{array}\]

---

 

第二题（普特南2001 A2）：有 \(n\) 枚硬币排成一列，每一枚硬币正面朝上的概率分别是 \(\frac13,\frac15,\frac17,\dots,\frac{1}{2n+1}\)，求在把所有硬币一次性抛出之后，有奇数个正面朝上的概率。

解：在有了上一题的经验之后，这题不难猜到也会是个概率大小的生成函数。令：

\[P(x)=\left(\frac23+\frac13x\right)\left(\frac45+\frac15x\right)\cdots\left(\frac{2n}{2n+1}+\frac{1}{2n+1}x\right)\]

那么不难发现 \(x^k\) 项的系数就是恰好 \(k\) 个硬币正面朝上的概率，这是因为每个 \(x\) 都会贡献一个某个硬币被扔出正面的概率，而每个常数项都会贡献一个反面的概率。我们想求这个函数里所有奇数次项的系数的和，从幂函数奇偶性的角度下手这个和就等于：

\[\begin{align*}&\phantom{=~}\frac{P(1)-P(-1)}{2}\\[3px]
&=\frac12\left(1-\frac13\cdot\frac35\cdot\frac57\cdots\frac{2n-1}{2n+1}\right)\\[5px]
&=\frac{n}{2n+1}\end{align*}\]

（可以这么做是因为每个奇数项 \(a_mx^m\) 在这么变换之后会变成 \(a_m\frac{1-(-1)}{2}=a_m\)，而每个偶数项 \(a_mx^m\) 会变成 \(a_m\frac{1-1}{2}=0\)。）

这就是我们要求的概率了。

---

 

第三题（欧拉拆分等式）：任取一个正整数 \(n\)，设 \(\mathcal{D}_n\) 是把 \(n\) 拆写成互不相等的数的和的方式数，\(\mathcal{O}_n\) 是把 \(n\) 拆写成奇数的和的方式数，求证 \(\mathcal D_n=\mathcal O_n\)。以下是 \(n=10\) 的一个例子：

\[\begin{array}{c|c}
\text{不相等拆分}&\text{奇数拆分}\\\hline
10&9+1\\
9+1&7+3\\
8+2&7+1+1+1\\
7+3&5+5\\
7+2+1&5+3+1+1\\
6+4&5+1+1+1+1+1\\
6+3+1&3+3+3+1\\
5+4+1&3+3+1+1+1+1\\
5+3+2&3+1+1+\dots+1\\
4+3+2+1&1+1+\dots+1\end{array}\]

解：很明显这道题已经和概率论没什么关系了，但是我们直接得到了两个数列，所以接下来我们只需要证明它们的生成函数相等就可以了。

首先 \(\mathcal D_n\) 的生成函数是这样的：

\[(1+x)(1+x^2)(1+x^3)\cdots\]

这是因为这个乘积的 \(x^n\) 项系数需要从每个括号里挑一个数，但是每个括号里的 \(x\) 的幂都不相等，且从系数上只贡献一个1，所以求和之后 \(x^n\) 项的系数就是 \(n\) 的不相等拆分的数量 \(\mathcal D_n\) 了。

同理 \(\mathcal O_n\) 的生成函数是这样的：

\[(1+x+x^2+\dots)(1+x^3+x^6+\dots)(1+x^5+x^{10}+\dots)\cdots\]

其中每个括号里的幂次都是一个固定的奇数的各个倍数。这是因为在一个和式里，同一个奇数可以出现任意多次，但是都需要按一个和式计算，所以把每个奇数的倍数都放在同一个括号里并且系数都取1，这样取完一个奇数的若干倍之后就不用担心同一个奇数再取一遍了。然后由于介绍段里最后的等式，这个生成函数也可以写成：

\[\frac{1}{1-x}\,\frac{1}{1-x^3}\,\frac{1}{1-x^5}\cdots\]

剩下的就是在这两个生成函数之间相互转化了，那么请看：

\[\begin{align*}&\phantom{=~}(1+x)(1+x^2)(1+x^3)\cdots\\[3px]
&=\frac{1-x^2}{1-x}\,\frac{1-x^4}{1-x^2}\,\frac{1-x^6}{1-x^3}\cdots\qquad\left(\text{平方差公式}\right)\\[5px]
&=\frac{1}{1-x}\,\frac{1-x^2}{1-x^2}\,\frac{1}{1-x^3}\,\frac{1-x^4}{1-x^4}\cdots\qquad\left(\text{重新整理}\right)\\[5px]
&=\frac{1}{1-x}\,\frac{1}{1-x^3}\,\frac{1}{1-x^5}\cdots
\end{align*}\]

这就是我们想要的结果了。

---

 

关于这方面的东西还想读到更多的话，这边是一些补充链接：

欧拉拆分等式的一个构造一一映射的证明：
https://math.stackexchange.com/a/54976

Matrix67也写过生成函数方面的内容：
http://www.matrix67.com/blog/archives/4534

一本关于生成函数的不错的书：
https://www.math.upenn.edu/~wilf/DownldGF.html

最后感谢阅读(=´∀｀)人(´∀｀=)