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

高中數學擴充套件

---

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

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

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

在我們開始之前: 本章假設您已掌握以下知識

1. 有序選擇（排列）和無序選擇（組合），這些內容在 基本計數 中有所介紹，
2. 部分分數法 以及，
3. 熟練運用 求和符號

一些計數問題

..待續

生成函式

..一些需要補充的動機

要理解本節內容，您需要了解為什麼這是真的

$\lim _{x\to \infty }{\frac {x^{2}+x}{x^{2}}}=1+\lim _{x\to \infty }{\frac {1}{x}}=1$

有關上述內容的更詳細討論，請前往 無限與無限過程.

生成函式，也稱為形式冪級數，對於解決以下問題很有用

$x_{1}+x_{2}+2x_{3}=m$

其中

$x_{n}\geq 0$; n = 1, 2, 3

如果$m=55$，有多少個不同的解？

在解決這個問題之前，讓我們考慮無限多項式

$S=1+x+x^{2}+x^{3}+...+x^{n}+x^{n+1}...$

我們想要得到這個無限多項式的封閉形式。封閉形式只是表達多項式的一種方式，以便它只涉及有限數量的操作。

為了找到封閉形式，我們從我們的函式開始

$S=1+x+x^{2}+x^{3}+...$

我們把函式的兩邊都乘以x，得到：$xS=x+x^{2}+x^{3}+...$

接下來，我們減去S-xS，得到

S - xS = 1 + x + x^2 + x^3 ... - x - x^2 - x^3 ...

分組類似項，我們得到

(1 - x)S = 1 + (x - x) + (x^2 - x^2) + (x^3 - x^3)

簡化為

(1 - x)S = 1

把兩邊都除以${\frac {1}{1-x}}$，我們得到$S={\frac {1}{1-x}}$

所以的封閉形式是

1 + x + x² + x³ + ...

是

${\frac {1}{1-x}}$

為了方便起見，我們可以寫成，雖然這對任何特定的x值都不成立。

$1+x+x^{2}+x^{3}+...={\frac {1}{1-x}}\ ;\ -1<x<1$

資訊 - 無限求和

這兩個表示式並不相等。只是對於x的某些值（-1 < x < 1），我們可以透過在左側累加大量項來儘可能接近地逼近右側。例如，假設x = 1/2，RHS = 2；我們僅使用 5 個項來逼近 LHS，得到 LHS 等於 1 + 1/2 + 1/4 + 1/8 + 1/16 = 1.9375，這接近 2，你可以想象，透過新增越來越多的項，我們將越來越接近 2。

無論如何，我們實際上只關心它的好的代數性質，而不是它的數值。從現在起，我們在寫出生成函式時將省略相等成立的條件。

考慮一個更一般的情況

$S=A+ABx+AB^{2}x^{2}+AB^{3}x^{3}+...$

其中A和B是常數。

我們可以如下推匯出封閉形式

${\begin{matrix}S&=&A+&ABx+AB^{2}x^{2}+AB^{3}x^{3}+...\\BxS&=&&ABx+AB^{2}x^{2}+AB^{3}x^{3}+...\\\\(1-Bx)S&=&A\\S&=&{\frac {A}{1-Bx}}\end{matrix}}$

上面推匯出的以下恆等式值得花時間和精力去記憶。

$A+ABx+AB^{2}x^{2}+AB^{3}x^{3}+...={\frac {A}{1-Bx}}$

練習

1. 求閉合形式

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

(b)$1+2z+4z^{2}+8z^{3}+16z^{4}+32z^{5}+...$

(c)$z+z^{2}+z^{3}+z^{4}+z^{5}+...$

(d)$3-4z+4z^{2}-4z^{3}+4z^{4}-4z^{5}+...$

(e)$1-z^{2}+z^{4}-z^{6}+z^{8}-z^{10}+...$

2. 給定閉合形式，求 xⁿ 係數的函式 f(n)

(a)${\frac {1}{1+z}}$ (提示：注意分母中的加號)

(b)${\frac {1}{1-2z}}$ (提示：將 A=1 和 B=2 代入 ${\frac {A}{1-Bz}}$)

(c)${\frac {z}{1-z}}$ (提示：將 ${\frac {1}{1-z}}$ 中的所有項乘以 z)

代換法

我們知道

1 + z + z² + ... = 1/(1 - z)

透過代換，我們可以得到許多其他生成函式。例如：令 z = x²，我們有

1 + x² + x⁴ + ... = 1/(1 - x²)

同樣地

A + ABx + A(Bx)² + ... = A/(1 - Bx)

是透過令 z = Bx 然後將整個表示式乘以 A 獲得的。

練習

1. x 的冪的係數是什麼

1/(1 - 2x³)

2. x 的冪的係數是什麼（提示：提出 1/2）

1/(2 - x)

線性遞推關係

斐波那契數列

1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

其中，除前兩個數外，每個數都是它前兩個數之和。如果一個數的值取決於序列中它前面的數的值，我們稱這些數是相關的。斐波那契數列是一個遞推關係的例子，它表示為

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

其中，x_n 是序列中的第 (n+ 1) 個數。請注意，序列中的第一個數用 x₀ 表示。給定這個遞推關係，我們想問的問題是“我們能否找到序列中第 (n+ 1) 個數的公式？”答案是肯定的，但在我們給出答案之前，讓我們來看一些例子。

示例 1

表示式

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

定義一個遞推關係。該序列為：1, 1, 5, 13, 41, 121, 365... 求序列中第（n+1）項的公式。

解 設 G(z) 為序列的生成函式，即每個冪的係數（按升序排列）是序列中相應的數字。因此，生成函式看起來像這樣

$G(z)=1+z+5z^{2}+13z^{3}+41z^{4}+121z^{5}+...$

現在，透過一系列代數運算，我們可以找到生成函式的閉合形式，並從中得到每個係數的公式

${\begin{matrix}&&G(z)&=&x_{0}+&x_{1}z+&x_{2}z^{2}&+&x_{3}z^{3}+x_{4}z^{4}+x_{5}z^{5}+...\\2z&\times &G(z)&=&&2x_{0}z+&2x_{1}z^{2}&+&...\\3z^{2}&\times &G(z)&=&&&3x_{0}z^{2}&+&...\\\end{matrix}}$

${\begin{matrix}G(z)-2zG(z)-3z^{2}G(z)&=&x_{0}+(x_{1}-2x_{0})z&+\\&&(x_{2}-2x_{1}-3x_{0})z^{2}&+\\&&(x_{3}-2x_{2}-3x_{1})z^{3}&+&...\end{matrix}}$

根據定義 x_n - 2x_{n - 1} - 3x_{n - 2} = 0

${\begin{matrix}(1-2z-3z^{2})&\times &G(z)&=&x_{0}+(x_{1}-2x_{0})z\\\\&&G(z)&=&{\frac {1-z}{1-2z-3z^{2}}}\\\\&&G(z)&=&{\frac {1-z}{(1-3z)(1+z)}}\end{matrix}}$

透過部分分式法，我們得到

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

和式中的每一項都具有可識別的閉合形式。我們可以得出結論

$x_{n}={\frac {1}{2}}\times 3^{n}+{\frac {1}{2}}\times (-1)^{n}$

讀者可以輕鬆檢查公式的準確性。

示例 2

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

求 x_n 的非遞迴公式。

解 令 G(z) 為上述序列的生成函式。

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

${\begin{matrix}G(z)(1-z-z^{2}+z^{3})&=&x_{0}&+&(x_{1}-x_{0})z+(x_{2}-x_{1}-x_{0})z^{2}\\G(z)(1-z-z^{2}+z^{3})&=&1-z^{2}\\\\\end{matrix}}$

${\begin{matrix}G(z)&=&{\frac {1-z^{2}}{1-z-z^{2}+z^{3}}}\\\\G(z)&=&{\frac {1-z}{1-2z+z^{2}}}\\\\G(z)&=&{\frac {1}{1-z}}\end{matrix}}$

因此，對於所有 n，x_n = 1。

示例 3

線性遞推關係定義為

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

求 x_n 的一般公式。

解 令 G(z) 為遞推關係的生成函式。

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

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

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

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

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

${\begin{matrix}G(z)&=&{\frac {1-z+z^{2}}{(1-z)(1+2z)(1-3z)}}\\G(z)&=&-{\frac {1}{6(1-z)}}+{\frac {7}{15(1+2z)}}+{\frac {7}{10(1-3z)}}\end{matrix}}$

因此

$x_{n}=-{\frac {1}{6}}+{\frac {7}{15}}(-2)^{n}+{\frac {7}{10}}3^{n}$

練習

1. 推匯出由以下線性遞推關係定義的序列中第（n+1）個數字的公式

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

2. 推匯出由以下線性遞推關係定義的序列中第（n+1）個數字的公式

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

3. （可選）推匯出第（n+1）個斐波那契數的公式。

進一步計數

考慮以下等式

a + b = n; a, b ≥ 0 為整數

對於固定的正整數 n，有多少個解？我們可以計算解的數量

0 + n = n

1 + (n - 1) = n

2 + (n - 2) = n

...

n + 0 = n

如您所見，有 (n + 1) 個解。解決該問題的另一種方法是考慮生成函式

G(z) = 1 + z + z² + ... + zⁿ

令 H(z) = G(z)G(z)，即

H(z) = (1 + z + z² + ... + zⁿ)²

我斷言，H(z) 中 zⁿ 的係數是 a + b = n，a, b > 0 的解的個數。原因在於 *當乘以同類項時，指數會相加*。

考慮

A(z) = 1 + z + z² + z³ + ...

令

B(z) = A²(z)

則

B(z) = (1 + z + z² + z³ + ...) + z(1 + z + z² + z³ + ...) + z²(1 + z + z² + z³ + ...) + z³(1 + z + z² + z³) + ...

B(z) = 1 + 2z + 3z² + ...

現在 zⁿ 的係數（對於 n ≥ 0）顯然是 a + b = n (a, b > 0) 的解的個數。

我們現在準備推匯出一個非常重要的結果：令 t_k 為 a + b = n (a, b > 0) 的解的個數。那麼序列 t_k 的生成函式為

T(z) = (1 + z + z² + ... + zⁿ + ...)(1 + z + z² + ... + zⁿ + ...)

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

即

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

計算 a₁ + a₂ + ... + a_m = n 的解

考慮以下等式的解的個數

a₁ + a₂ + ... + a_m = n

其中 a_i ≥ 0; i = 1, 2, ... m。透過應用先前討論的方法，如果 t_k 是當 n = k 時上述等式的解的個數，則 t_k 的生成函式為

$T(z)={\frac {1}{(1-z)^{m}}}$

但是，t_k 是什麼呢？除非您學過微積分，否則很難僅透過觀察 T(z) 的方程來推匯出公式。在不假設微積分知識的情況下，我們考慮以下計數問題。

“你有三個姐妹，你有 n（n ≥ 3）顆糖果。你決定至少給每個姐妹一顆糖果。有多少種方法可以做到這一點？”

解決這個問題的一種方法是將所有糖果按直線排放在桌子上。由於有 n 顆糖果，因此它們之間有 (n - 1) 個空隙（就像你的每隻手有 5 根手指，它們之間有 4 個空隙一樣）。現在拿兩個分隔物，從可用的 (n - 1) 個空隙中，選擇 2 個並把一個分隔物放在你選擇的每個空隙中！就這樣，你把 n 顆糖果分成三部分，每個姐妹一部分。有 $n-1 \choose 2$ 種方法可以做到這一點！如果你有 4 個姐妹，那麼有 $n-1 \choose 3$ 種方法可以做到這一點。如果你有 m 個姐妹，那麼有 $n-1 \choose m-1$ 種方法可以做到這一點。

現在考慮：“你有三個姐妹，你有 n 顆糖果。你決定給每個姐妹一些糖果（對給每個姐妹多少顆糖果沒有限制）。有多少種方法可以做到這一點？”

請注意，你只是在求解

a₁ + a₂ + a₃ = n

其中 a_i ≥ 0；i = 1, 2, 3。

你可以透過將 n + 3 顆糖果按直線排放在桌子上解決這個問題。拿兩個分隔物，從可用的 n + 2 個空隙中選擇 2 個空隙。現在你把 n + 3 顆糖果分成了 3 部分，每部分至少有 1 顆糖果。現在從每部分拿回 1 顆糖果，你就可以解決這個問題了！所以解的個數是 $n+2 \choose 2$。更一般地，如果你有 m 個姐妹和 n 顆糖果，那麼分享糖果的方法數為

${{n+m-1} \choose {m-1}}={{n+m-1} \choose {n}}$ .

現在得到重要結果，如上所述，方程的解的個數為

a₁ + a₂ + ... + a_m = n

其中 a_i ≥ 0；i = 1, 2, 3 ... m 為

${{n+m-1} \choose {n}}$

即

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

示例 1

生成函式 T(z) 的封閉形式為

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

以及 T(z) 中 z^k 的係數為 t_k。求 t_k 的顯式公式。

解

${\begin{matrix}{\frac {1}{(1-z)^{2}}}&=&\sum _{i=0}^{\infty }(i+1)z^{i}\\\\{\frac {z}{(1-z)^{2}}}&=&z\sum _{i=0}^{\infty }(i+1)z^{i}\\\\&=&\sum _{i=0}^{\infty }(i+1)z^{i+1}\\\end{matrix}}$

因此 t_k = k

示例 2

求解方程的解的個數

a + b + c + d = n

對於所有正整數 n（包括零），並受限制 a, b, c, d ≥ 0。

解 根據公式

${\begin{matrix}{\frac {1}{(1-z)^{4}}}&=&\sum _{i=0}^{\infty }{{n+3} \choose {3}}z^{i}\\\\\end{matrix}}$

所以

解的個數是 ${{n+3} \choose {3}}$

更多計數

我們轉向一個稍微難一點的同類問題。假設我們要計算以下方程的解的個數：

2a + 3b + c = n

其中n為整數且$n\geq 0$，且a、b和c大於或等於零。我們可以直接寫出封閉形式，我們注意到以下式子的xⁿ項的係數

$(1+x^{2}+x^{4}+...)(1+x^{3}+x^{6}+...)(1+x+x^{2}+...)={\frac {1}{(1-x^{2})(1-x^{3})(1-x)}}$

是所需要的解。這再次歸因於，在相乘冪次時，指數相加。

為了獲得解的個數，我們用部分分式法將表示式分解成可識別的封閉形式。

示例 1

設s_k是以下方程的解的個數：

2a + 2b = n; a, b ≥ 0

求出s_k的生成函式，然後用n表示出s_n的顯式公式。

解

設T(z)為t_k的生成函式

T(z) = (1 + z² + z⁴ + ... + z²ⁿ + ...)²

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

不難看出

$s_{n}=0\ {\mbox{if n is odd}}$

$s_{n}={n/2+1 \choose n/2}={n/2+1 \choose 1}=n/2+1\ {\mbox{if n is even}}$

示例 2

設t_k是以下方程的解的個數：

a + 2b = n; a, b ≥ 0

求出t_k的生成函式，然後用n表示出t_n的顯式公式。

解

設T(z)為t_k的生成函式

T(z) = (1 + z + z² + ... + zⁿ + ...)(1 + z² + z⁴ + ... + z²ⁿ + ...)

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

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

$T(z)={\frac {Az+B}{(1-z)^{2}}}+{\frac {C}{1+z}}$

A = -1/4, B = 3/4, C = 1/4

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

$t_{k}=-{\frac {1}{4}}k+{\frac {3}{4}}(k+1)+{\frac {1}{4}}(-1)^{k}$

練習

1. 假設

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

是 t_k (k = 0, 1, 2 ...) 的生成函式。求出 t_k 關於 k 的顯式公式。

2. 當 m 為給定常數時，以下方程有多少解

$a+b+2c=m$

其中 a，b 和 c ≥ 0

習題集

1. 一家新公司借了 250,000 美元的初始資本。月利率為 3%。公司計劃在每個月底前償還 x 美元。利息在每月最後一天計入債務（按月複利）。

令 D_n 表示 n 個月後剩餘的債務。

a) 遞迴地定義 D_n。

b) 求出 x 的最小值。

c) 求出 D_n 的一般公式。

d) 因此，確定如果 x = 12,000，需要多少個月才能償還債務。

2. n 的一個劃分是一個正整數序列 (λ1,λ1,..,λr)，使得 λ1 ≥ λ2 ≥ .. ≥ λr 且 λ1 + λ2 + .. + λr = n。例如，令 n = 5，則 (5)，(4,1)，(3,2)，(3,1,1)，(2,2,1)，(2,1,1,1)，(1,1,1,1,1) 都是 5 的所有劃分。所以我們說 5 的劃分數是 7。推匯出一個關於一般 n 的劃分數的公式。

3. 二叉樹是一種樹，其中每個節點最多可以有兩個子節點。下圖是一個二叉樹的例子。

a) 令 c_n 表示總共 n 個節點的二叉樹的唯一排列數。令 C(z) 為 c_n 的生成函式。

(i) 使用遞迴定義 C(z)。

(ii) 從而找到 C(z) 的閉合形式。

b) 令 $P(x)={\sqrt {1+ax}}=p_{0}+p_{1}x+p_{2}x^{2}+p_{3}x^{3}...$ 是一個冪級數。

(i) 透過考慮 P(x) 的 n 次導數，找到 p_n 的公式。

(ii) 使用 a) 和 b)(i) 的結果，或其他方法，推匯出 c_n 的公式。

提示：與其遞迴地查詢在底部新增節點時 c_n 的變化，不如嘗試從相反的方向和方向思考。（而且，不是刪除節點）

專案 - 指數生成函式

本專案假設您瞭解微分。

(可選)0.

(a)

(i) 透過第一原理微分 log x。

(ii)*** 證明最後一部分中無法求值的剩餘極限確實收斂。從而透過將該數作為常數來完成微分。

(b) 從而微分 $a^{x}$.

1. 考慮 $E(x)=e^{x}$

(a) 求出 E(x) 的 n 次導數。

(b) 透過考慮 E(x) 在 x = 0 處的 n 次導數的值，將 E(x) 表示為冪級數/無窮多項式形式。

(可選)2.

(a) 求出等比數列（即本章開頭介紹的普通生成函式）收斂的條件。（提示：求出部分和）

(b) 因此，證明上一個問題中的 E(x) 在所有實數 x 的值上都收斂。（提示：對於任何固定的 x，一般項的分子是指數函式，而一般項的分母是階乘。然後呢？）

3. 函式 E(x) 是最基本最重要的指數生成函式，它類似於普通生成函式，但有一些不同，最明顯的區別是每一項都帶有階乘分數。

(a) 類似於普通生成函式，E(x) 的多項式展開中的每一項都可以有數字作為係數。現在考慮 $A(x)=a_{1}+a_{2}{\frac {x}{1!}}+a_{3}{\frac {x^{2}}{2!}}+a_{4}{\frac {x^{3}}{3!}}+...$

求 $A'(x)$ 並將其與 A(x) 進行比較。你發現了什麼？

(b) 將 nz 代入 E(x)，其中 n 是一個實數，z 是一個自由變數，即 E(nz)。你發現了什麼？

4. 除了問題 2 中定義的 A(x) 之外，令 $B(x)=b_{1}+b_{2}{\frac {x}{1!}}+b_{3}{\frac {x^{2}}{2!}}+b_{4}{\frac {x^{3}}{3!}}+...$

(a) A(x) 乘以 B(x) 是多少？將其與普通生成函式進行比較，有什麼不同？

(b) 如果我們盲目地將 A(x) 乘以 x（或一般情況下乘以 xⁿ）會怎麼樣？它會像普通生成函式一樣移動係數嗎？

注意：帶有 *** 的問題是難題，雖然你不一定能回答這些問題，但請隨意嘗試一下，盡力而為。

反饋

你覺得怎麼樣？ 太簡單還是太難？資訊太多還是不夠？我們如何改進？請在討論區留下評論告訴我們。更好的是，自己編輯它，讓它變得更好。