Quod Erat Demonstrandum

2011/01/06

生成函數某應用

Filed under: Fun,mathematics — johnmayhk @ 6:10 下午

又談舊東西。

把 5 寫成若干正整數的和,有以下 7 個情況:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 4
5 = 2 + 3
5 = 5

注:我們要求「分拆」出來的數列(比如:1,2,2)是非下降的,即不接納諸如

5 = 2 + 1 + 2

的分拆方式。

這裡想大家留意兩種分拆方式:

[方式 a] 各分拆部分之數目不同
[方式 b] 各分拆部分之數目是奇數

所謂 [方式 a] 各分拆部分之數目不同,以 5 為例,即

5 = 1 + 4
5 = 2 + 3
5 = 5

共 3 種情況。

所謂 [方式 b] 各分拆部分之數目是奇數,即

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 3
5 = 5

也是共有 3 種情況。

再以另一個正整數 7 為例,

考慮 [方式 a] 各分拆部分之數目不同:

7 = 1 + 2 + 4
7 = 1 + 6
7 = 2 + 5
7 = 3 + 4
7 = 7

共 5 種情況。

考慮 [方式 b] 各分拆部分之數目是奇數:

7 = 1 + 1 + 1 + 1 + 1 + 1 + 1
7 = 1 + 1 + 1 + 1 + 3
7 = 1 + 1 + 5
7 = 1 + 3 + 3
7 = 7

也是共有 5 種情況。

巧合嗎?

非也,這是必然的。

a_n 是把 n 以 [方式 a] 分拆的所有可能之數目。
b_n 是把 n 以 [方式 b] 分拆的所有可能之數目。

a_5 = b_5 = 3
a_7 = b_7 = 5

現在證明

對所有正整數 na_n = b_n

常用手法是利用生成函數(generating function),即命

f(x) = a_0 + a_1x + a_2x^2 + \dots
g(x) = b_0 + b_1x + b_2x^2 + \dots

(其中 a_0 = b_0 = 1

希望證明

f(x) \equiv g(x)

進而得出結果。

考慮

\displaystyle\prod_{k=1}^{\infty}(1 + x^k) = (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)\dots  …… (1)

想像一下,把上式「展開」後,可以得出多少個(比方說) x^7

可以有

1 個 x^{(1 + 2 + 4)}
1 個 x^{(1 + 6)}
1 個 x^{(2 + 5)}
1 個 x^{(3 + 5)}
1 個 x^{(7)}

所以,把 (1) 展開後,

共有 5 個 x^7,即

x^7 的係數是 5;

但觀察該 5 項的指數,即 1+2+4, 1+6, 2+5, 3+5, 7

即把 7 以 [方式 a] 分拆,亦即把 (1) 展開後,

應有 a_7x^7,故此

把 (1) 展開後,x^7 的係數就是 a_7

推而廣之,

把 (1) 展開後,x^n 的係數就是 a_n

亦即

f(x) \equiv (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)\dots

好了,現在嘗試找關乎 [方式 b] 的生成函數。

觀察 7 以 [方式 b] 的分拆:

1 + 1 + 1 + 1 + 1 + 1 + 1 = 7 \times 1

1 + 1 + 1 + 1 + 3 = 4 \times 1 + 1 \times 3

1 + 1 + 5 = 2 \times 1 + 1 \times 5

1 + 3 + 3 = 1 \times 1 + 2 \times 3

7 = 1 \times 7

即對於 7,[方式 b] 的分拆形如:

7 = k_1(1) + k_2(3) + k_3(5) + k_4(7)

一般地 [方式 b] 的分拆形如:

k_1(1) + k_2(3) + k_3(5) + k_4(7) + \dots

故,我們不況考慮

(1 + x + x^2 + x^3 + \dots)(1 + x^3 + x^6 + x^9 + \dots)(1 + x^5 + x^{10} + \dots)\dots

想像一下,把上式展開後,各項形如

x^{k_1(1) + k_2(3) + k_3(5) + k_4(7) + \dots}

而當中 x^n 之係數,

就是把 n 以 [方式 b] 分拆之數目,即 b_n

所以

g(x) \equiv (1 + x + x^2 + x^3 + \dots)(1 + x^3 + x^6 + x^9 + \dots)(1 + x^5 + x^{10} + \dots)\dots

進一步簡化,得

\equiv (\frac{1}{1 - x})(\frac{1}{1 - x^3})(\frac{1}{1 - x^5})\dots

還記得我們的方向嗎?就是希望證明上式就是 f(x)

f(x) \equiv (1 + x)(1 + x^2)(1 + x^3)(1 + x^4)\dots

h(x) \equiv (1 - x)(1 - x^2)(1 - x^3)(1 - x^4)\dots

f(x)h(x) \equiv (1 - x^2)(1 - x^4)(1 - x^6)\dots

另外

\frac{1}{g(x)} \equiv (1 - x)(1 - x^3)(1 - x^5)\dots

\frac{f(x)h(x)}{g(x)} \equiv (1 - x)(1 - x^2)(1 - x^3)(1 - x^4)\dots

\Rightarrow \frac{f(x)h(x)}{g(x)} \equiv h(x)

\Rightarrow f(x) \equiv g(x)

亦即

a_n = b_n (\forall n \in \mathbb{N})

這就是 Euler 定理。

想了解多一些,請看看

http://en.wikipedia.org/wiki/Partition_(number_theory)

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在 WordPress.com 建立免費網站或網誌.

%d 位部落客按了讚: