高中数学扩展/计数与生成函数/解答

高中数学扩展

---

补充章节 — 素数与模算术 — 逻辑

数学证明 — 集合论与无穷过程 — 计数与生成函数 — 离散概率

矩阵 — 进一步模算术 — 数学规划 — 马尔可夫链

计数与生成函数

目前，主要精力集中在编写每个章节的主要内容。因此，此练习解答部分可能已过时，并且看起来很混乱。

如果您有任何问题，请在“讨论区”中留言，或联系作者或任何主要贡献者。

这些解答并非由本书的作者编写。它们只是我在做练习时认为正确的答案。我希望这些答案对某人有用，并且如果我犯了一些错误，人们会纠正我的工作。

生成函数练习

1.

(a)$S=1-z+z^{2}-z^{3}+z^{4}-z^{5}+...$

$zS=z-z^{2}+z^{3}-z^{4}+z^{5}-...$

$(1+z)S=1$

$S={\frac {1}{1+z}}$

2.

(b)$S={\frac {z^{3}}{1-z^{2}}}$

$(1-z^{2})S=z^{3}$

$S=z^{3}+z^{5}+z^{7}+z^{9}+...$

$f(n)=1;{\mbox{for n}}\geq 2{\mbox{ and even}}$

$f(n)=0;{\mbox{for n is odd}}$

目前仅包含练习，没有答案。

(c)${\frac {z^{2}-1}{1+3z^{3}}}$

线性递推关系练习

本节仅包含不完整的答案，因为我无法弄清楚如何继续。

1.

${\begin{matrix}x_{n}&=&2x_{n-1}&-&1;\ {\mbox{for n}}\geq 1\\x_{0}&=&1\end{matrix}}$

设G(z) 为上述序列的生成函数。

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

$(1-2z)G(z)=x_{0}+(x_{1}-2x_{0})z+(x_{2}-2x_{1})z^{2}+...$

$(1-2z)G(z)=1-z-z^{2}-z^{3}-z^{4}-...$

$(1-2z)G(z)=1-z(1+z+z^{2}+...)$

$(1-2z)G(z)=1-{\frac {z}{1-z}}$

$(1-2z)G(z)={\frac {1-2z}{1-z}}$

$G(z)={\frac {1}{1-z}}$

$x_{n}=1$

2.

${\begin{matrix}3x_{n}&=&-4x_{n-1}&+&x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

设G(z) 为上述序列的生成函数。

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

$(3+4z-z^{2})G(z)=3x_{0}+(3x_{1}+4x_{0})z+(3x_{2}+4x_{1}-x_{0})z^{2}+(3x_{3}+4x_{2}-x_{1})z^{3}+...$

$(3+4z-z^{2})G(z)=3x_{0}+(3x_{1}+4x_{0})z$

$(3+4z-z^{2})G(z)=3+7z$

$G(z)={\frac {3+7z}{-z^{2}+4z+3}}$

3. 令 G(z) 为上述序列的生成函数。

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

$(1-z-z^{2})G(z)=x_{0}+(x_{1}-x_{0})z+(x_{2}-x_{1}-x_{0})z^{2}+(x_{3}-x_{2}-x_{1})z^{2}+...$

$(1-z-z^{2})G(z)=1$

$G(z)={\frac {1}{1-z-z^{2}}}$

$G(z)={\frac {-1}{z^{2}+z-1}}$

我们想要将 $f(z)=z^{2}+z-1$ 因式分解成 $(z-\alpha )(z-\beta )$ ，根据因式定理的逆定理，如果 (z - p) 是 f(z) 的因式，则 f(p)=0。

因此，α 和 β 是二次方程 $z^{2}+z-1=0$ 的根。

使用二次公式求根

$\alpha ={\frac {{\sqrt {5}}-1}{2}},\beta =-{\frac {{\sqrt {5}}+1}{2}}$

事实上，这两个数字就是著名的黄金分割，为了简化，我们从现在开始使用黄金分割的希腊符号。

注意：${\frac {{\sqrt {5}}-1}{2}}$ 表示为 $\phi$ 并且 ${\frac {{\sqrt {5}}+1}{2}}$ 表示为 $\Phi$

$G(z)={\frac {-1}{(z-\phi )(z+\Phi )}}$

通过部分分式法

$G(z)={\frac {1}{{\sqrt {5}}(z+\Phi )}}-{\frac {1}{{\sqrt {5}}(z-\phi )}}$

$G(z)={\frac {1}{\Phi {\sqrt {5}}({\frac {z}{\Phi }}+1)}}-{\frac {1}{\phi {\sqrt {5}}({\frac {z}{\phi }}-1)}}$

$G(z)={\frac {1}{\Phi {\sqrt {5}}(1--\phi z)}}+{\frac {1}{\phi {\sqrt {5}}(1-\Phi z)}}$

$x_{n}={\frac {\phi }{\sqrt {5}}}\times (-\phi )^{n}+{\frac {\Phi }{\sqrt {5}}}\times \Phi ^{n}$

$x_{n}={\frac {\Phi ^{n+1}-(-\phi )^{n+1}}{\sqrt {5}}}$

进一步的计数练习

1. 我们知道

$T(z)={\frac {1}{(1-z)^{2}}}=\sum _{i=0}^{\infty }{i+1 \choose i}z^{i}=\sum _{i=0}^{\infty }(i+1)z^{i}$

因此

$T(z)={\frac {1}{(1+z)^{2}}}=\sum _{i=0}^{\infty }(i+1)(-1)^{i}z^{i}$

所以

$T_{k}=(-1)^{k}(k+1)$

2. $a+b+c=m$

$T(z)={\frac {1}{(1-z)^{3}}}=\sum _{i=0}^{\infty }{i+2 \choose i}z^{i}$

所以

$T_{k}={i+2 \choose i}$

*从基本原理微分*练习

1.

$f'(z)=\lim _{h\to 0}{\frac {1}{(1-(z+h))^{2}}}-{\frac {1}{(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {(1-z)^{2}-(1-(z+h))^{2}}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {z^{2}-2z+1-(z+h)^{2}+2(z+h)-1}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {z^{2}-2z+1-z^{2}-h^{2}-2zh+2z+2h-1}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {1}{h}}{\frac {-h^{2}-2zh+2h}{(1-z-h)^{2}(1-z)^{2}}}=$

$\lim _{h\to 0}{\frac {-h-2z+2}{(1-z-h)^{2}(1-z)^{2}}}=$

${\frac {-2z+2}{(1-z)^{4}}}=$

${\frac {-2}{(1-z)^{3}}}$