CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 生成函数理论2 ======

===== 基本例子 =====

 **例 1** 设 $n\ge 1$，$X_n=\{1,2,\cdots,n\}$。记 $a_n$ 为 $X_n$ 的子集个数，求 $a_n$。

 **解**：易知 $a_n=2a_{n-1}(n\ge 1)$，$\{a_n\}_{n=0}^{\infty}$ 的普通生成函数为 $$
\begin{align}
f(x)&=\sum_{n=0}^{\infty}a_nx^n=1+\sum_{n=1}^{\infty}a_nx^n=1+\sum_{n=0}^{\infty}2a_nx^{n+1}\\
&=1+2x\sum_{n=0}^{\infty}a_nx^n=1+2xf(x),
\end{align}
$$ 所以 $$
f(x)=\frac{1}{1-2x}=\sum_{n=0}^{\infty}(2x)^n=\sum_{n=0}^{\infty}2^nx^n.
$$ 比较系数得 $a_n=2^n$.

 **例 2** 设有三种物体 $a,b,c$。令 $a_n$ 表示从中不重复地选取 $n$ 种物体的方法数，则 $\{a_n\}_{n=0}^{\infty}$ 对应的普通生成函数可如下得出： $$
\begin{align}
((ax)^0&+(ax)^1)((bx)^0+(bx)^1)((cx)^0+(cx)^1)\\
&=(1+ax)(1+bx)(1+cx)\\
&=1+(a+b+c)x+(ab+bc+ca)x^2+abcx^3
\end{align}
$$ 上式中 $x^i$ 的系数表明选取 $i$ 种物体的选取方式。例如，$x^2$ 的系数为 $ab+bc+ca$，表明选取 $2$ 种物体时选取的是 $a$ 和 $b$，或者 $b$ 和 $c$，或者 $c$ 和 $a$ 这三种方式。若仅仅求选取方法数，则只令 $a=b=c=1$ 即可。这时，有 $$
\{a_n\}\leftrightarrow (1+x)^3
$$ 这样就得到 $\displaystyle a_n=\binom{3}{n}$.

 现在改变规则：设 $a$ 可取 $0,1$ 或 $2$ 次，$b$ 可取 $0$ 或 $1$ 次，$c$ 可取偶数次。令 $b_n$ 表示选取 $n$ 个物体的方法数，则 $\{b_n\}_{n=0}^{\infty}$ 对应的普通生成函数即 $$
\begin{align}
(1+x+x^2)(1+x)(1+x^2+x^4+\cdots)&=\frac{1+x+x^2}{1-x}\\
&=(1+x+x^2)\sum_{n=0}^{\infty}x^n\\
&=1+2x+3\sum_{n=2}^{\infty}x^n.
\end{align}
$$ 从以上的生成函数不难看出，当 $n\ge 2$ 时，$b_n=3$。

 **例 3** 给定正整数 $k$，令 $h_n$ 表示方程 $$
x_1+x_2+\cdots +x_k=n
$$ 的非负整数解的个数。我们已经知道 $$
h_n=\binom{n+k-1}{n}
$$ 求 $\{h_n\}_{n=0}^{\infty}$ 对应的普通生成函数的闭形式。

 **解** 令 $h(x)$ 表示 $\{h_n\}_{n=0}^{\infty}$ 的普通生成函数，则有 $$
\begin{align}
h(x)&=\underbrace{(1+x+x^2+\cdots)(1+x+x^2+\cdots)\cdots(1+x+x^2+\cdots)}_\text{k 个}\\
&=\left(\sum_{i_1=0}^{\infty}x^{i_1}\right)\left(\sum_{i_2=0}^{\infty}x^{i_2}\right)\cdots\left(\sum_{i_k=0}^{\infty}x^{i_k}\right)\\
&=\frac{1}{(1-x)^k}
\end{align}
$$  **推论 4** $\displaystyle \left\{\binom{n+k-1}{n}\right\}_{n=0}^{\infty}\leftrightarrow \frac{1}{(1-x)^k}.$

 **例 5** 从数量不限的苹果、香蕉、橘子和梨中，选取 $n$ 个水果装成一袋，且选取的苹果数是偶数，香蕉数是 $5$ 的倍数，橘子最多有 $4$ 个，而梨最多有 $1$ 个。记这样的装法有 $h_n$ 种，求 $h_n$。

 **解** 令 $g(x)$ 为 $\{h_n\}_{n=0}^{\infty}$ 的普通生成函数，则 $$
\begin{align}
g(x)&=(1+x^2+x^4+\cdots)(1+x^5+x^{10}+\cdots)(1+x+x^2+x^3+x^4)(1+x)\\
&=\frac{1}{1-x^2}\cdot\frac{1}{1-x^5}\cdot\frac{1-x^5}{1-x}(1+x)\\
&=\frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}\binom{n+1}{n}x^n,
\end{align}
$$ 从而由推论 4 有 $h_n=n+1$

**例 6** 推导斐波那契数列的通项公式，其中 $a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}(n>1)$

 **解** 设 $\{a_n\}_{n=0}^{\infty}$ 的普通生成函数是 $f(x)$，那么根据其递推式，可以得到一个有关 $f(x)$ 的方程： $$
f(x)=xf(x)+x^2f(x)-a_0x+a_1x+a_0
$$ 那么解得 $$
\begin{align}
f(x)=\frac{x}{1-x-x^2}
\end{align}
$$ 用待定系数法对分母降次 $$
f(x)=\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{x}{1-x-x^2}
=\frac{A-Abx+B-aBx}{(1-ax)(1-bx)}
$$ 得到 $$
\begin{cases}
A+B=0\\
-Ab-aB=1\\
a+b=1\\
ab=-1
\end{cases}
$$ 解得 

$$
\begin{cases}
A=\frac{1}{\sqrt 5}\\ B=-\frac{1}{\sqrt 5}\\ a=\frac{1+\sqrt 5}{2}\\ b=\frac{1-\sqrt 5}{2}
\end{cases}
$$ 

由此得到， 

$$
\frac{x}{1-x-x^2}=\sum_{n=0}^{\infty}x^n\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)
$$ 

即斐波那契数列的通项公式为 $\displaystyle a_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)$
CVBB ACM Team

用户工具

站点工具

页面工具
