高中數學擴充套件/計數與生成函式/解答

高中數學擴充套件

---

補充章節 — 素數與模算術 — 邏輯

數學證明 — 集合論與無窮過程 — 計數與生成函式 — 離散機率

矩陣 — 進一步模算術 — 數學規劃 — 馬爾可夫鏈

計數與生成函式

目前，主要精力集中在編寫每個章節的主要內容。因此，此練習解答部分可能已過時，並且看起來很混亂。

如果您有任何問題，請在“討論區”中留言，或聯絡作者或任何主要貢獻者。

這些解答並非由本書的作者編寫。它們只是我在做練習時認為正確的答案。我希望這些答案對某人有用，並且如果我犯了一些錯誤，人們會糾正我的工作。

生成函式練習

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}}}$