本节对应原书 PDF 第 248–256 页。定义、定理、公式、例题及其原解答逐字取自原书；原书大段解释文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

生成函数是与序列相对应的形式幂级数，利用生成函数可以直接求解组合计数序列.第 9 章已经遇到了一个生成函数的实例，就是棋盘多项式，它与给定棋盘的布棋方案数序列相对应.这里将对生成函数的性质进一步加以分析，并给出更多的应用实例.

解读：生成函数的思路是「把数列装进一个幂级数的系数里」，序列的加法、卷积、移位等操作就变成函数的加法、乘法、代入，于是数列问题可以转成代数问题来解。

10.2.1 牛顿二项式定理与牛顿二项式系数

为了处理幂级数的需要，先引入牛顿二项式系数 \dbinom{r}{n}.

定义 10.5 设 r 为实数，n 为整数，引入形式符号

\dbinom{r}{n}=\begin{cases} 0 & n<0\\ 1 & n=0\\ \dfrac{r(r-1)\cdots(r-n+1)}{n!} & n>0 \end{cases}

称为牛顿二项式系数.

例如：

\dbinom{-2}{5}=\dfrac{(-2)(-3)(-4)(-5)(-6)}{5!}=-6
\dbinom{1/2}{4}=\dfrac{\dfrac{1}{2}\left(\dfrac{1}{2}-1\right)\left(\dfrac{1}{2}-2\right)\left(\dfrac{1}{2}-3\right)}{4!}=\dfrac{1(-1)(-3)(-5)}{2^44!}=\dfrac{-5}{128}
\dbinom{4}{3}=\dfrac{4 \cdot 3 \cdot 2}{3!}=4

表面上看，这个符号与二项式系数的符号一样，但是在这里它只是一个形式符号，不具有任何组合意义.当 r 为自然数时，牛顿二项式系数就成为普通的二项式系数，这时才与集合的组合计数联系到一起.

和二项式定理对应，也有一个牛顿二项式定理，它恰好表示了某些函数的幂级数.

定理 10.6 牛顿二项式定理.

设 \alpha 为实数，则对一切实数 x,y，|x/y|<1，有

(x+y)^\alpha=\sum_{n=0}^{\infty}\dbinom{\alpha}{n}x^ny^{\alpha-n},\quad \text{其中 } \dbinom{\alpha}{n}=\dfrac{\alpha(\alpha-1)\cdots(\alpha-n+1)}{n!}

这个定理的证明可以在一般的数学分析书中找到，这里不再赘述.当 \alpha=m 时，其中 m 为正整数，这个定理就变成二项式定理（定义 8.5）；若 \alpha=-m，那么

\begin{aligned} \dbinom{\alpha}{n} &=\dbinom{-m}{n}=\dfrac{(-m)(-m-1)\cdots(-m-n+1)}{n!}\\ &=\dfrac{(-1)^nm(m+1)\cdots(m+n-1)}{n!}=(-1)^n\dbinom{m+n-1}{n} \end{aligned}

这时令 x=z,y=1，那么牛顿二项式定理就变成

(1+z)^{-m}=\frac{1}{(1+z)^m}=\sum_{n=0}^{\infty}(-1)^n\binom{m+n-1}{n}z^n\qquad |z|<1

在上面式子中用 -z 代替 z，则有

(1-z)^{-m}=\frac{1}{(1-z)^m}=\sum_{n=0}^{\infty}\binom{m+n-1}{n}z^n\qquad |z|<1

特别地有

m=1,\qquad \frac{1}{1-x}=1+x+x^2+\cdots
m=2,\qquad \frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}(n+1)x^n

以上有关幂级数的结果在生成函数中经常会用到.

解读：牛顿二项式系数把二项式系数从「m 为正整数」推广到任意实数，代价是它失去组合意义、只作为形式符号存在；而 \alpha 取负整数时得到的 \frac{1}{(1\pm z)^m} 展开式，正是后面把生成函数化回数列时最常用的两个基本块。

10.2.2 生成函数的定义及其性质

定义 10.6 设序列 \{a_n\}，构造形式幂级数

G(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots

称 G(x) 为序列 \{a_n\} 的生成函数.

例如，\{C(m,n)\} 的生成函数为 (1+x)^m，给定正整数 k，\{k^n\} 的生成函数为

G(x)=1+kx+k^2x^2+k^3x^3+\cdots=\frac{1}{1-kx}

下面给出生成函数的性质，其中 A(x),B(x),C(x) 分别表示序列 \{a_n\},\{b_n\},\{c_n\} 的生成函数.

（1）若 b_n=\alpha a_n，\alpha 为常数，则 B(x)=\alpha A(x).

（2）若 c_n=a_n+b_n，则 C(x)=A(x)+B(x).

（3）若 c_n=\sum\limits_{i=0}^{n}a_ib_{n-i}，则 C(x)=A(x) \cdot B(x).

（4）若 b_n=\begin{cases}0 & n<l\\ a_{n-l} & n \geqslant l\end{cases}，则 B(x)=x^lA(x).

（5）若 b_n=a_{n+l}，则 B(x)=\dfrac{A(x)-\sum\limits_{n=0}^{l-1}a_nx^n}{x^l}.

（6）若 b_n=\sum\limits_{i=0}^{n}a_i，则 B(x)=\dfrac{A(x)}{1-x}.

（7）若 b_n=\sum\limits_{i=n}^{\infty}a_i，且 A(1)=\sum\limits_{n=0}^{\infty}a_n 收敛，则 B(x)=\dfrac{A(1)-xA(x)}{1-x}.

（8）若 b_n=\alpha^na_n，\alpha 为常数，则 B(x)=A(\alpha x).

（9）若 b_n=na_n，则 B(x)=xA'(x)，其中 A'(x) 为 A(x) 的导数.

（10）若 b_n=\dfrac{a_n}{n+1}，则 B(x)=\dfrac{1}{x}\int_0^xA(x)\mathrm{d}x.

这里的性质涉及生成函数的线性性质、乘积性质、移位性质、求和性质、换元性质、微商与积分性质等，证明方法比较简单，只需将生成函数定义代入，利用幂级数的性质就可以证明上述结果.有关证明留给读者思考.

生成函数与序列是一一对应的.给定序列 \{a_n\} 或关于 a_n 的递推方程，如何求它的生成函数 G(x) 呢？反之，给定生成函数 G(x)，如何求对应序列的通项表达式 a_n 呢？这些都是使用生成函数过程中经常遇到的问题，为了解决这些问题，除了利用生成函数的性质以外，还经常用到下述幂级数的展开式.

\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n
\frac{1}{1+x}=\sum_{n=0}^{\infty}(-1)^nx^n
\begin{aligned} (1+x)^{\frac{1}{2}} &=\sum_{k=0}^{\infty}\binom{1/2}{k}x^k=1+\sum_{k=1}^{\infty}\frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\cdots\left(\frac{1}{2}-k+1\right)}{k!}x^k\\ &=1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1} \cdot 1 \cdot 3 \cdot 5 \cdot \cdots \cdot (2k-3)}{2^kk!}x^k\\ &=1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1}(2k-2)!}{2^kk! \cdot 2^{k-1}(k-1)!}x^k\\ &=1+\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{2^{2k-1}k}\binom{2k-2}{k-1}x^k \end{aligned}

例 10.20 求序列 \{a_n\} 的生成函数.

（1）a_n=7 \cdot 3^n.

（2）a_n=n(n+1).

解 （1）G(x)=7\sum\limits_{n=0}^{\infty}3^nx^n=7\sum\limits_{n=0}^{\infty}(3x)^n=\dfrac{7}{1-3x}.

（2）G(x)=\sum\limits_{n=0}^{\infty}n(n+1)x^n.

对 G(x) 积分得

\begin{aligned} \int_0^xG(x)\mathrm{d}x &=\int_0^x\sum_{n=0}^{\infty}n(n+1)x^n\mathrm{d}x=\sum_{n=0}^{\infty}\int_0^xn(n+1)x^n\mathrm{d}x\\ &=\sum_{n=1}^{\infty}nx^{n+1}=x^2\sum_{n=1}^{\infty}nx^{n-1}=x^2H(x) \end{aligned}

其中

H(x)=\sum_{n=1}^{\infty}nx^{n-1}=\sum_{n=0}^{\infty}(n+1)x^n

为求 H(x)，先求右边级数的和.为此进行积分，得

\int_0^xH(x)\mathrm{d}x=\sum_{n=0}^{\infty}x^{n+1}=\frac{1}{1-x}-1=\frac{x}{1-x}
H(x)=\frac{1}{1-x}-x\frac{-1}{(1-x)^2}=\frac{1}{(1-x)^2}

代入得

\int_0^xG(x)\mathrm{d}x=\frac{x^2}{(1-x)^2}

对这个等式求导得到

G(x)=\left[\frac{x^2}{(1-x)^2}\right]'=\frac{2x}{(1-x)^2}+x^2(-2)\frac{(-1)}{(1-x)^3}=\frac{2x(1-x)+2x^2}{(1-x)^3}=\frac{2x}{(1-x)^3}

解读：例 10.20（2）用的是「先积分把系数 n(n+1) 消成常数、求和后再求导还原」这一套路。积分与求导之所以可行，是因为形式幂级数可以逐项积分、逐项求导。

给定序列 \{a_n\} 的生成函数，求 a_n.基本方法就是利用部分分式的待定系数法将原来的函数化成基本生成函数的表达式之和，然后利用这些基本生成函数的展开式求出 a_n.

例 10.21 已知 \{a_n\} 的生成函数为 G(x)=\dfrac{2+3x-6x^2}{1-2x}，求 a_n.

解 G(x)=\dfrac{2+3x-6x^2}{1-2x}=\dfrac{2}{1-2x}+3x=2\sum\limits_{n=0}^{\infty}(2x)^n+3x=\sum\limits_{n=0}^{\infty}2^{n+1}x^n+3x

因此 a_n=\begin{cases}2^{n+1} & n \neq 1\\ 2^2+3=7 & n=1\end{cases}.

解读：3x 这一项只影响 x^1 的系数，所以通项公式在 n=1 处要单独修正，其他位置仍按 2^{n+1} 给出——这是生成函数反求数列时容易漏掉的一步。

10.2.3 生成函数的应用

生成函数在组合问题中有着广泛的应用.可以用生成函数求解递推方程，特别是某些不适合使用公式法和迭代归纳法的方程.

例 10.22 求解递推方程

\begin{cases} h_n=\sum\limits_{k=1}^{n-1}h_kh_{n-k} & n \geqslant 2\\ h_1=1 \end{cases}

解 设 \{h_n\} 的生成函数为 H(x)=\sum\limits_{n=1}^{\infty}h_nx^n，两边平方得

\begin{aligned} H^2(x) &=\sum_{k=1}^{\infty}h_kx^k \cdot \sum_{l=1}^{\infty}h_lx^l=\sum_{k=1}^{\infty}\sum_{l=1}^{\infty}h_kh_lx^{k+l}\\ &=\sum_{n=2}^{\infty}x^n\sum_{k=1}^{n-1}h_kh_{n-k}=\sum_{n=2}^{\infty}h_nx^n\\ &=H(x)-h_1x=H(x)-x \end{aligned}

这是一个关于 H(x) 的一元二次方程，利用求根公式得到

H_1(x)=\frac{1+(1-4x)^{\frac{1}{2}}}{2},\qquad H_2(x)=\frac{1-(1-4x)^{\frac{1}{2}}}{2}

由于 H(0)=0，因此取 H(x)=H_2(x).将 H(x) 展开得

\begin{aligned} H(x) &=\frac{1-(1-4x)^{\frac{1}{2}}}{2}=\frac{1}{2}-\frac{1}{2}(1-4x)^{\frac{1}{2}}\\ &=\frac{1}{2}-\frac{1}{2}\left[1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n2^{2n-1}}\binom{2n-2}{n-1}(-4x)^n\right]\\ &=\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n2^{2n}}\binom{2n-2}{n-1}(-1)^n2^{2n}x^n\\ &=\sum_{n=1}^{\infty}\frac{1}{n}\binom{2n-2}{n-1}x^n \end{aligned}

因此 h_n=\dfrac{1}{n}\dbinom{2n-2}{n-1}.

以上递推方程是关于 Catalan 数的递推方程，通过求解这个方程，得到了第 n 个 Catalan 数的值 h_n.关于 Catalan 数的定义和性质将在后面进一步讨论.

回顾例 8.18 关于栈输出结果的计数实例，通过使用非降路径的模型，得到 n 个元素的栈的不同输出的个数是 \dfrac{1}{n+1}\dbinom{2n}{n}，这个数恰好是第 n+1 Catalan 数.下面使用生成函数的方法求解这个问题.

考虑字符 1,2,\cdots,n，当某个字符 X 进栈时记录一个左括号“(”，当 X 出栈时记录一个右括号“)”，在这两个括号中间的字符就是在 X 之后进栈并且在 X 之前出栈的字符.例如 (1(2(3))(4)) 表示的过程是：

1 进栈，2 进栈，3 进栈，3 出栈，2 出栈，4 进栈，4 出栈，1 出栈

每个输出序列对应于 n 对括号的合理配对的方法数.由于进栈的次数不少于出栈次数，这就意味着在配对的任何位置，从左边算起，左括号的数目都不少于右括号的数目.设 n 对括号的配对方法数是 T(n)，考虑与最左边的左括号配对的右括号的位置，在这对括号中间有 k 对其他括号，这 k 对括号有 T(k) 种配对方法；而在这对括号的后面有 n-1-k 对括号，这些括号的配对方法数是 T(n-1-k).因此，对于给定的 k，构成输出序列的方法数是 T(k)T(n-1-k).由于 k 可能的取值是 0,1,2,\cdots,n-1.根据加法法则，可以得到递推方程

\begin{cases} T(n)=\sum\limits_{k=0}^{n-1}T(k)T(n-1-k)\\ T(0)=1 \end{cases}

设序列 \{T(n)\} 的生成函数是 T(x)，那么有 T(x)=\sum\limits_{n=0}^{\infty}T(n)x^n，从而得到

\begin{aligned} T^2(x) &=\left(\sum_{k=0}^{\infty}T(k)x^k\right)\left(\sum_{l=0}^{\infty}T(l)x^l\right)=\sum_{n=1}^{\infty}x^{n-1}\left(\sum_{k=0}^{n-1}T(k)T(n-1-k)\right)\\ &=\sum_{n=1}^{\infty}T(n)x^{n-1}=\frac{T(x)-1}{x} \end{aligned}

求解关于 T(x) 的一元二次方程，得到 2xT(x)=1 \pm \sqrt{1-4x}.由于 x \to 0 时，T(x) \to 1，取根为 T(x)=\dfrac{1-\sqrt{1-4x}}{2x}，展开成幂级数得

T(x)=\sum_{n=0}^{\infty}\frac{1}{n+1}\binom{2n}{n}x^n

因此，不同的输出个数为 \dfrac{1}{n+1}\dbinom{2n}{n}.

解读：例 10.22 与栈输出问题都是同一招：把递推式里出现的「卷积」\sum h_kh_{n-k} 看成 H^2(x)，于是递推方程被抬升成一个关于 H(x) 的代数方程，解出 H(x) 后再查展开式就得到通项。这也是生成函数比迭代归纳更强的场合。

利用生成函数可以计算多重集的 r 组合数.设

S=\{n_1 \cdot a_1,n_2 \cdot a_2,\cdots,n_k \cdot a_k\}

是多重集，S 的 r-组合数就是不定方程

x_1+x_2+\cdots+x_k=r,\quad x_i \leqslant n_i,\quad i=1,2,\cdots,k

的非负整数解的个数.考虑函数

G(y)=(1+y+\cdots+y^{n_1})(1+y+\cdots+y^{n_2})\cdots(1+y+\cdots+y^{n_k})

的展开式中的项，应该是下述形式：y^{x_1+x_2+\cdots+x_k}，其中 x_i 是非负整数，且 x_i \leqslant n_i，i=1,2,\cdots,k.因此展开式中 y^r 的系数，恰好是多重集 S 的 r-组合数.

例 10.23 求 S=\{3 \cdot a,4 \cdot b,5 \cdot c\} 的 10-组合数 N.

解 生成函数

\begin{aligned} G(y) &=(1+y+y^2+y^3)(1+y+y^2+y^3+y^4)(1+y+y^2+y^3+y^4+y^5)\\ &=(1+2y+3y^2+4y^3+4y^4+3y^5+2y^6+y^7)(1+y+y^2+y^3+y^4+y^5)\\ &=(1+\cdots+3y^{10}+2y^{10}+y^{10}+\cdots) \end{aligned}

其中 y^{10} 的系数是 6，因此 N=6.

从上面的分析可以看到，利用生成函数可以求不定方程的解的个数.下面对不定方程解的计数问题（计数模型 4）进一步加以推广.考虑不定方程

x_1+x_2+\cdots+x_k=r,\quad x_i\text{ 为自然数}

根据定理 8.4，解的个数是 C(k+r-1,r)，下面通过生成函数的方法求解这个问题.类似于上面的分析，生成函数为

\begin{aligned} G(y) &=(1+y+\cdots)^k=\frac{1}{(1-y)^k}\\ &=\sum_{r=0}^{\infty}\frac{(-k)(-k-1)\cdots(-k-r+1)}{r!}(-y)^r\\ &=\sum_{r=0}^{\infty}\frac{(-1)^rk(k+1)\cdots(k+r-1)}{r!}(-1)^ry^r\\ &=\sum_{r=0}^{\infty}\binom{k+r-1}{r}y^r \end{aligned}

其中 y^r 的系数是 N=C(k+r-1,r).

考虑对变量取值存在限制情况下的不定方程

x_1+x_2+\cdots+x_k=r,\quad l_i \leqslant x_i \leqslant n_i,\quad i=1,2,\cdots,k

这时关于方程非负整数解的计数没有一般的公式，生成函数是

G(y)=(y^{l_1}+y^{l_1+1}+\cdots+y^{n_1})(y^{l_2}+y^{l_2+1}+\cdots+y^{n_2})\cdots(y^{l_k}+y^{l_k+1}+\cdots+y^{n_k})

G(y) 的展开式中 y^r 的系数就是不定方程的解的个数.

对于某些不定方程，变量的系数不全是 1，而用其他正整数作为系数，即

p_1x_1+p_2x_2+\cdots+p_kx_k=r,\quad x_i \in \mathbf{N},\quad p_1,p_2,\cdots,p_k\text{ 为正整数}

那么也可以使用生成函数的方法求解，对应的生成函数是

G(y)=(1+y^{p_1}+y^{2p_1}+\cdots)(1+y^{p_2}+y^{2p_2}+\cdots)\cdots(1+y^{p_k}+y^{2p_k}+\cdots)

G(y) 的展开式中 y^r 的系数就是这个不定方程的解的个数.

最后需要说明的是，在不定方程既存在限制条件，同时系数也不全为 1 的情况下，也可以参照上面的方法写出对应的生成函数.请看下面的例子.

例 10.24 有 1 克砝码 2 个，2 克砝码 1 个，4 克砝码 2 个，问能称出哪些重量，方案有多少种？

解 根据题意列出不定方程如下：

1x_1+2x_2+4x_3=r
0 \leqslant x_1 \leqslant 2,\quad 0 \leqslant x_2 \leqslant 1,\quad 0 \leqslant x_3 \leqslant 2

对应的生成函数为

\begin{aligned} G(y) &=(1+y+y^2)(1+y^2)(1+y^4+y^8)\\ &=1+y+2y^2+y^3+2y^4+y^5+2y^6+y^7+2y^8+y^9+2y^{10}+y^{11}+y^{12} \end{aligned}

根据这个函数可以写出下面的表 10.1，其中重量表示可以称的重量，方案表示对于给定重量，可能的称重方案数.

表 10.1

重量0123456789101112
方案1121212121211

使用生成函数可以求解正整数拆分的计数问题.这也是一个常用的组合计数模型（组合计数模型 5）.所谓正整数的拆分就是将给定正整数 N 表示成若干个正整数之和.根据拆分后的组成部分是否允许重复、是否有序，可以将拆分问题划分成 4 类.表 10.2 给出了 3 的对应于不同分类的拆分方案.

表 10.2

重复 ＼ 有序有 序无 序
不重复3=3；3=1+2；3=2+13=3；3=1+2
重复3=3；3=1+2；3=2+1；3=1+1+13=3；3=1+2；3=1+1+1

下面考虑拆分问题的计数，首先考虑无序拆分.

设 N 是给定正整数，将 N 无序拆分成正整数 a_1,a_2,\cdots,a_n，则有等式

a_1x_1+a_2x_2+\cdots+a_nx_n=N

这个问题可以归结为不定方程的解的计数问题.如果拆分后的部分不允许重复，那么对应的生成函数是

G(y)=(1+y^{a_1})(1+y^{a_2})\cdots(1+y^{a_n})

如果允许重复，对应的生成函数是

\begin{aligned} G(y) &=(1+y^{a_1}+y^{2a_1}+\cdots)(1+y^{a_2}+y^{2a_2}+\cdots)\cdots(1+y^{a_n}+y^{2a_n}+\cdots)\\ &=\frac{1}{(1-y^{a_1})(1-y^{a_2})\cdots(1-y^{a_n})} \end{aligned}

例 10.25 证明任何正整数都可以唯一地表示成二进制数.

证明 设正整数为 N，不难看出，将 N 拆分成 2 的幂 2^0,2^1,2^2,2^3,\cdots 且不允许重复的方案，恰好与 N 表示成一个二进制数的方法对应.因此，N 的二进制表示法的个数与上述拆分方案数相等.对任意正整数 n，n 的拆分方案数记为 a_n，根据前面的分析，拆分方案数的生成函数是

G(y)=(1+y)(1+y^2)(1+y^4)(1+y^8)\cdots

展开为

G(y)=\frac{1-y^2}{1-y}\cdot\frac{1-y^4}{1-y^2}\cdot\frac{1-y^8}{1-y^4}\cdots=\frac{1}{1-y}=\sum_{n=0}^{\infty}y^n

在上述幂级数中，由于每项的系数都是 1，因此对于所有的 n，a_n=1，这就证明了正整数 N 只能表示成唯一的二进制数.

解读：例 10.25 把「二进制表示唯一」翻译成「2 的幂的不重复拆分方案唯一」。生成函数里相邻分式的分子分母逐个约掉，只剩 \frac{1}{1-y}，系数恒为 1 就等价于拆法唯一——这就是全部证明的内容。

如果对正整数被拆分后的部分存在大小限制，那么可以使用生成函数计算拆分的方案数.如果对拆分部分的数目加以限制，则不能直接写出相应的生成函数，但是可以使用组合对应的方法来解决这类问题.

例 10.26 给定 r，求将正整数 N 无序并允许重复地拆分成 k 个部分（k \leqslant r）的方法数.

解 考虑任意一个将 N 无序并允许重复地拆分成 k 个部分（k \leqslant r）的方案，可以用一个图来表示这个方案.首先将被拆分后的部分按照从大到小的顺序排列.例如对于下述拆分方案 16=6+5+3+2（k \leqslant 4），4 个部分的排列顺序是：6,5,3,2.如图 10.6（a）所示，拆分后的每个数从左到右分别用一列点来表示，即第一列 6 个点，第二列 5 个点，第三列 3 个点，第四列 2 个点.这个图称为 Ferrers 图.由于数是从大到小排列的，因此左边的列上的点数不少于右边的列上的点数.

原书图10.6

将 Ferrers 图看作一个直角坐标系，然后将它围绕 y=x 的直线翻转 180^{\circ}，就得到另一个共轭的 Ferrers 图，如图 10.6（b）所示.这个图恰好对应了拆分后每个部分都不超过 4 的一种方案，即

16=4+4+3+2+2+1

因此，问题就转变为：求将 N 无序并允许重复地拆分且拆分后的每个数都不超过 r 的方案数.对应的生成函数是

G(y)=\frac{1}{(1-y)(1-y^2)\cdots(1-y^r)}

G(y) 的展开式中 y^N 的系数就是所需要的结果.

解读：N 拆成不超过 r 个部分，与 N 拆成每部分都不超过 r，这两类拆分数相等——因为 Ferrers 图转置后行列互换，正好把「列数不超过 r」变成「每列高度不超过 r」。例 10.26 正是靠这个对应绕开了「部分数目受限」写不出生成函数的困难。

下面考虑有序拆分的计数问题.

定理 10.7 设 N 是正整数，将 N 允许重复地有序拆分成 r 个部分的方案数为 C(N-1,r-1).

证明 设 N=a_1+a_2+\cdots+a_r 是满足条件的拆分，则令

S_i=\sum_{t=1}^{i}a_t\qquad i=1,2,\cdots,r

那么

0<S_1<S_2<\cdots<S_r=N

不难看出拆分方案与这些 S_i 的选择方法是一一对应的.下面计数对这些 S_i 有多少种不同的选择方法.由于 r-1 个 S_i(i=1,2,\cdots,r-1) 取值于集合 \{1,2,\cdots,N-1\}，选择方法数是 C(N-1,r-1).

根据这个定理，使用加法法则，不难得到下述推论.

推论 对正整数 N 做任意重复的有序拆分，方案数为 \sum\limits_{r=1}^{N}\dbinom{N-1}{r-1}=2^{N-1}.

对于不允许重复的有序拆分问题，可以分两步处理.先将 N 不允许重复进行无序拆分，对应的生成函数是

G(x)=(1+x)(1+x^2)\cdots(1+x^N)

G(x) 中 x^N 的系数就是无序拆分的方案数.针对每种无序的拆分方案，计数被拆分部分的全部排列数，然后将所有的结果相加，就可以得到所求的拆分方案数.

以上用生成函数解决了多重集的 r-组合数、不定方程解的计数、正整数拆分方案的计数等问题.除此之外，利用生成函数还可以证明组合恒等式.限于篇幅，这里不再赘述，有兴趣的读者可以阅读相关的参考书.