2020-2021:teams:legal_string:lgwza:生成函数理论_2_基本例子
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:生成函数理论_2_基本例子 [2021/02/10 14:45] lgwza |
2020-2021:teams:legal_string:lgwza:生成函数理论_2_基本例子 [2021/02/10 15:55] (当前版本) lgwza [基本例子] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 生成函数理论2 ====== | ====== 生成函数理论2 ====== | ||
| - | |||
| - | |||
| ===== 基本例子 ===== | ===== 基本例子 ===== | ||
| - | **例 1** 设 $n\ge 1$，$X_n=\{1,2,\cdots,n\}$。记 $a_n$ 为 $X_n$ 的子集个数，求 $a_n$。 | + | **例 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}$ 的普通生成函数为 | + | **解**：易知 $a_n=2a_{n-1}(n\ge 1)$，$\{a_n\}_{n=0}^{\infty}$ 的普通生成函数为 $$ |
| - | $$ | + | |
| \begin{align} | \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}\\ | 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), | &=1+2x\sum_{n=0}^{\infty}a_nx^n=1+2xf(x), | ||
| \end{align} | \end{align} | ||
| - | $$ | + | $$ 所以 $$ |
| - | 所以 | + | |
| - | $$ | + | |
| f(x)=\frac{1}{1-2x}=\sum_{n=0}^{\infty}(2x)^n=\sum_{n=0}^{\infty}2^nx^n. | f(x)=\frac{1}{1-2x}=\sum_{n=0}^{\infty}(2x)^n=\sum_{n=0}^{\infty}2^nx^n. | ||
| - | $$ | + | $$ 比较系数得 $a_n=2^n$. |
| - | 比较系数得 $a_n=2^n$. | + | |
| - | **例 2** 设有三种物体 $a,b,c$。令 $a_n$ 表示从中不重复地选取 $n$ 种物体的方法数，则 $\{a_n\}_{n=0}^{\infty}$ 对应的普通生成函数可如下得出： | + | **例 2** 设有三种物体 $a,b,c$。令 $a_n$ 表示从中不重复地选取 $n$ 种物体的方法数，则 $\{a_n\}_{n=0}^{\infty}$ 对应的普通生成函数可如下得出： $$ |
| - | $$ | + | |
| \begin{align} | \begin{align} | ||
| ((ax)^0&+(ax)^1)((bx)^0+(bx)^1)((cx)^0+(cx)^1)\\ | ((ax)^0&+(ax)^1)((bx)^0+(bx)^1)((cx)^0+(cx)^1)\\ | ||
| 行 27: | 行 20: | ||
| &=1+(a+b+c)x+(ab+bc+ca)x^2+abcx^3 | &=1+(a+b+c)x+(ab+bc+ca)x^2+abcx^3 | ||
| \end{align} | \end{align} | ||
| - | $$ | + | $$ 上式中 $x^i$ 的系数表明选取 $i$ 种物体的选取方式。例如，$x^2$ 的系数为 $ab+bc+ca$，表明选取 $2$ 种物体时选取的是 $a$ 和 $b$，或者 $b$ 和 $c$，或者 $c$ 和 $a$ 这三种方式。若仅仅求选取方法数，则只令 $a=b=c=1$ 即可。这时，有 $$ |
| - | 上式中 $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 | \{a_n\}\leftrightarrow (1+x)^3 | ||
| - | $$ | + | $$ 这样就得到 $\displaystyle a_n=\binom{3}{n}$. |
| - | 这样就得到 $\displaystyle a_n=\binom{3}{n}$. | + | |
| - | 现在改变规则：设 $a$ 可取 $0,1$ 或 $2$ 次，$b$ 可取 $0$ 或 $1$ 次，$c$ 可取偶数次。令 $b_n$ 表示选取 $n$ 个物体的方法数，则 $\{b_n\}_{n=0}^{\infty}$ 对应的普通生成函数即 | + | 现在改变规则：设 $a$ 可取 $0,1$ 或 $2$ 次，$b$ 可取 $0$ 或 $1$ 次，$c$ 可取偶数次。令 $b_n$ 表示选取 $n$ 个物体的方法数，则 $\{b_n\}_{n=0}^{\infty}$ 对应的普通生成函数即 $$ |
| - | $$ | + | |
| \begin{align} | \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)(1+x)(1+x^2+x^4+\cdots)&=\frac{1+x+x^2}{1-x}\\ | ||
| 行 41: | 行 30: | ||
| &=1+2x+3\sum_{n=2}^{\infty}x^n. | &=1+2x+3\sum_{n=2}^{\infty}x^n. | ||
| \end{align} | \end{align} | ||
| - | $$ | + | $$ 从以上的生成函数不难看出，当 $n\ge 2$ 时，$b_n=3$。 |
| - | 从以上的生成函数不难看出，当 $n\ge 2$ 时，$b_n=3$。 | + | |
| - | **例 3** 给定正整数 $k$，令 $h_n$ 表示方程 | + | **例 3** 给定正整数 $k$，令 $h_n$ 表示方程 $$ |
| - | $$ | + | |
| x_1+x_2+\cdots +x_k=n | x_1+x_2+\cdots +x_k=n | ||
| - | $$ | + | $$ 的非负整数解的个数。我们已经知道 $$ |
| - | 的非负整数解的个数。我们已经知道 | + | |
| - | $$ | + | |
| h_n=\binom{n+k-1}{n} | h_n=\binom{n+k-1}{n} | ||
| - | $$ | + | $$ 求 $\{h_n\}_{n=0}^{\infty}$ 对应的普通生成函数的闭形式。 |
| - | 求 $\{h_n\}_{n=0}^{\infty}$ 对应的普通生成函数的闭形式。 | + | |
| - | **解** 令 $h(x)$ 表示 $\{h_n\}_{n=0}^{\infty}$ 的普通生成函数，则有 | + | **解** 令 $h(x)$ 表示 $\{h_n\}_{n=0}^{\infty}$ 的普通生成函数，则有 $$ |
| - | $$ | + | |
| \begin{align} | \begin{align} | ||
| h(x)&=\underbrace{(1+x+x^2+\cdots)(1+x+x^2+\cdots)\cdots(1+x+x^2+\cdots)}_\text{k 个}\\ | h(x)&=\underbrace{(1+x+x^2+\cdots)(1+x+x^2+\cdots)\cdots(1+x+x^2+\cdots)}_\text{k 个}\\ | ||
| 行 61: | 行 44: | ||
| &=\frac{1}{(1-x)^k} | &=\frac{1}{(1-x)^k} | ||
| \end{align} | \end{align} | ||
| - | $$ | + | $$ **推论 4** $\displaystyle \left\{\binom{n+k-1}{n}\right\}_{n=0}^{\infty}\leftrightarrow \frac{1}{(1-x)^k}.$ |
| - | a | + | **例 5** 从数量不限的苹果、香蕉、橘子和梨中，选取 $n$ 个水果装成一袋，且选取的苹果数是偶数，香蕉数是 $5$ 的倍数，橘子最多有 $4$ 个，而梨最多有 $1$ 个。记这样的装法有 $h_n$ 种，求 $h_n$。 |
| - | **推论 4** | + | **解** 令 $g(x)$ 为 $\{h_n\}_{n=0}^{\infty}$ 的普通生成函数，则 $$ |
| - | + | ||
| - | $ | + | |
| - | \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} | \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)\\ | g(x)&=(1+x^2+x^4+\cdots)(1+x^5+x^{10}+\cdots)(1+x+x^2+x^3+x^4)(1+x)\\ | ||
| 行 80: | 行 54: | ||
| &=\frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}\binom{n+1}{n}x^n, | &=\frac{1}{(1-x)^2}=\sum_{n=0}^{\infty}\binom{n+1}{n}x^n, | ||
| \end{align} | \end{align} | ||
| - | $$ | + | $$ 从而由推论 4 有 $h_n=n+1$ |
| - | 从而由推论 4 有 $h_n=n+1$ | + | |
| - | **例 6** 推导斐波那契数列的通项公式，其中 $a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}(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)$ 的方程： | + | **解** 设 $\{a_n\}_{n=0}^{\infty}$ 的普通生成函数是 $f(x)$，那么根据其递推式，可以得到一个有关 $f(x)$ 的方程： $$ |
| - | $$ | + | |
| f(x)=xf(x)+x^2f(x)-a_0x+a_1x+a_0 | f(x)=xf(x)+x^2f(x)-a_0x+a_1x+a_0 | ||
| - | $$ | + | $$ 那么解得 $$ |
| - | 那么解得 | + | |
| - | $$ | + | |
| \begin{align} | \begin{align} | ||
| f(x)=\frac{x}{1-x-x^2} | f(x)=\frac{x}{1-x-x^2} | ||
| \end{align} | \end{align} | ||
| - | $$ | + | $$ 用待定系数法对分母降次 $$ |
| - | 用待定系数法对分母降次 | + | |
| - | $$ | + | |
| f(x)=\frac{A}{1-ax}+\frac{B}{1-bx}=\frac{x}{1-x-x^2} | 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)} | =\frac{A-Abx+B-aBx}{(1-ax)(1-bx)} | ||
| - | $$ | + | $$ 得到 $$ |
| - | 得到 | + | |
| - | $$ | + | |
| \begin{cases} | \begin{cases} | ||
| A+B=0\\ | A+B=0\\ | ||
| 行 108: | 行 74: | ||
| ab=-1 | ab=-1 | ||
| \end{cases} | \end{cases} | ||
| - | $$ | + | $$ 解得 |
| - | 解得 | + | |
| $$ | $$ | ||
| \begin{cases} | \begin{cases} | ||
| - | A=\frac{1}{\sqrt 5}\\ | + | A=\frac{1}{\sqrt 5}\\ B=-\frac{1}{\sqrt 5}\\ a=\frac{1+\sqrt 5}{2}\\ b=\frac{1-\sqrt 5}{2} |
| - | B=-\frac{1}{\sqrt 5}\\ | + | |
| - | a=\frac{1+\sqrt 5}{2}\\ | + | |
| - | b=\frac{1-\sqrt 5}{2} | + | |
| \end{cases} | \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) | \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)$ | 即斐波那契数列的通项公式为 $\displaystyle a_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)$ | ||
| - | |||
| - | |||
2020-2021/teams/legal_string/lgwza/生成函数理论_2_基本例子.1612939539.txt.gz · 最后更改: 2021/02/10 14:45 由 lgwza
