小蓝书 16.3

本文写于较早时候，所以可能存在一些问题。

小蓝书上讲的母函数就是普通生成函数。传送门：生成函数学习笔记

对于一个数列 \(\{f_n\}\) ，定义它的普通生成函数 \(F(x)\) 为以 \(x\) 为未定元的一个形式幂级数，则 \[ F(x) = \sum_{n \ge 0} f_nx^n \\f_n = [x^n]F(x) \] 另一种易于理解的写法是这样的（数列为 \(\{a_n\}\) ） \[ F(x) = \sum_{i=0}^{\infty}a_ix^i = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots \]

一些常用的公式&技巧：

公式I

\(\forall x : |x| < 1\) \[ \dfrac{1}{1-x} = \sum_{n=0}^{\infty} x^n = 1+x+x^2 + \cdots + x^n + \cdots \] 公式II

\(\forall x : |x| < 1,~ k \in \mathbb{Z}_{+}\) \[ \begin{aligned} \dfrac{1}{(1-x)^k} &= \sum_{n=0}^{\infty}\dbinom{n+k-1}{k-1} x^n \\[6pt]&= 1+\dbinom{k}{k-1}x+\dbinom{k+1}{k-1}x^2 + \cdots + \dbinom{n+k-1}{k-1}x^n + \cdots \end{aligned} \] 对于以下封闭形式，常拆成若干项「形如 \(\frac{1}{1-px}\) 的式子」之和 \[ \frac{f(x)}{(1-ax)(1-bx)^{m}} \] 其中：

\(m \in \mathbb{Z_+},~a,b\in \mathbb{R}\)

\(f(x)\) 为 \(x\) 的一个有穷幂级数（即形如 \(a_0 + a_1x+a_2x^2 +\cdots+a_nx^n\) 的多项式）

并且 \(n\) 一般小于等于分母最高次项的次数（在这里是 \(m+1\)）

我们一般拆成如下形式 \[ \frac{A}{1-ax} + \frac{B_1}{(1-bx)^{m}}+\frac{B_2}{(1-bx)^{m-1}}+\cdots + \frac{B_m}{(1-bx)} \] > 注：这里要展开出 \(A_1\) 和 \(B_1,B_2,\cdots B_m\) 的原因是： > > 它的分母是最高次项次数为 \(m+1\) 的多项式，需要 \(m+1\) 个系数。

然后通分求出 \(A,B_1,B_2,\cdots,B_m\) ，最后用公式 I, II 等将其展开即可。

当然另外还有一种可能比较简洁的方法。由于是形式幂级数，不考虑其解析意义

也可利用类似「等式两边乘 \((1-ax)\) 后令 \(x=\frac{1}{b}\) 」的方法消掉其它项，解出要用的项，详见例题1。

反正我不推荐这个解法，不要问我为什么。

2022-09-28 OI