Quod Erat Demonstrandum

2015/02/17

數算球入盒

Filed under: mathematics,NSS,Pure Mathematics — johnmayhk @ 11:40 上午
Tags: ,

基本問題:把若干球放入若干盒子,共多少種放法?下表是總結:

johnmayhk-balls-and-boxes-01

以下 3 個情況屬 core mathematics 的範圍:

(一)

johnmayhk-balls-and-boxes-04

e.g.
k = 4 個球上分別寫上 a,b,c,d,即 4 個球是不同的,是可分辨的;n = 3 個盒子上,分別貼上號碼 1,2,3,即 3 個盒子是不同的,是可分辨

的。

a 球可以入盒 1, 盒 2 或盒 3,共 3 種選擇;
b 球可以入盒 1, 盒 2 或盒 3,共 3 種選擇;
c 球可以入盒 1, 盒 2 或盒 3,共 3 種選擇;
d 球可以入盒 1, 盒 2 或盒 3,共 3 種選擇;

故入盒方法共 3\times 3\times 3\times 3 =3^4

一般地,把 k 個可分辨的球,放在 n 個可分辨的盒子內,共 n^k 種方法。

(二)

johnmayhk-balls-and-boxes-05

把 k 個可分辨的球,放在 n 個可分辨的盒子內,要求盒子不可放超過 1 個球,即容許空盒。既是如此,必有 n \ge k
e.g.
設 k = 3 個球分別寫上 a,b,c;在 n = 4 個盒子分別貼上 1,2,3,4 號碼。
用 (a,2),(b,1),(c,4) 代表 a 球在 1 盒;b 球在 1 盒;c 球在 4 盒。
現在想像 a,b,c 是固定了,我們從 4 個盒選 3 個,蓋在 a,b,c 上;所以
(a,2),(b,1),(c,4) 對應 [2,1,3] 這個排法;
類似地,
(a,4),(b,3),(c,1) 對應 [4,3,1] 這個排法;
(a,3),(b,1),(c,2) 對應 [3,1,2] 這個排法;
諸如此類;所以
把 3 個可分辨的球,放在 4 個可分辨的盒子內,要求盒子不可放超過 1 個球,有多少放法,相當於
把 4 個數字 {1,2,3,4} 排 3 個位的隊(e.g. [3,1,2])有多少種排法,即 P^4_3 種。
一般地,把 k 個可分辨的球,放在 n 個可分辨的盒子內,要求盒子不可放超過 1 個球,共 P^n_k 種放法。

(三)

johnmayhk-balls-and-boxes-06

把 k 個不可分辨的球,放在 n 個可分辨的盒子內,要求盒子不可放超過 1 個球,即容許空盒。既是如此,必有 n \ge k
e.g.
設 k = 3 個不可分辨的球:O O O;在 n = 4 個盒子分別貼上 1,2,3,4 號碼。
用 (O,2),(O,1),(O,4) 代表 3 個球分別放在 2 號盒,1 號盒及 4 號盒;
用 (O,4),(O,2),(O,1) 代表 3 個球分別放在 4 號盒,2 號盒及 1 號盒等,
留意上述兩個情況根本一樣是代表盒子 1,2,4 有一個球,表之曰 {1,2,4}。
故把 3 個不可分辨的球,放在 4 個可分辨盒子的放法,相當於
把 4 個數字 {1,2,3,4} 選 3 個(e.g. {1,2,4})的選法,即 C^4_3 種。
一般地,把 k 個不可分辨的球,放在 n 個可分辨的盒子內,要求盒子不可放超過 1 個球,共 C^n_k 種放法。

以下介紹 2 個情況,相信讀 core mathematics 的同學應該可以理解:

(四)

johnmayhk-balls-and-boxes-07

把 k 個不可分辨的球,放在 n 個可分辨的盒子內,要求盒子放至少 1 個球,即不容許空盒。既是如此,必有 k \ge n
e.g.
設 k = 6 個不可分辨的球:O O O O O O;在 n = 3 個盒子分別貼上 1,2,3 號碼。

用 (OO,1),(O,2),(OOO,3) 代表 2 個球入 1 號盒,1 個球入 2 號盒,3 個球入 3 號盒;
用 (OOOO,1),(O,2),(O,3) 代表 4 個球入 1 號盒,1 個球入 2 號盒,1 個球入 3 號盒;
用 (OOO,1),(OO,2),(O,3) 代表 3 個球入 1 號盒,2 個球入 2 號盒,1 個球入 3 號盒;

固定盒號(由左至右:1,2,3),只畫出球,那麼上面 3 個情況,分別可表成:

O O,O,O O O 及
O O O O,O,O 及
O O O,O O,O

可見,把 2 個逗號,放在 O 與 O 之間不同的空位,就代表把球放盒不同的方式。
由於不容許空盒,那麼 6 個 O 只有 6-1=5 個空位,安放逗號(每個空位最多只能放 1 個):

O_O_O_O_O_O

有 3 個盒子,便用 3-1=2 個逗號把 6 個 O 分 3 組。
所以,
把 6 個不可分辨的球,放在 3 個可分辨盒子(不容許空盒)有多少方法,相當於
把 3-1 個逗號,放在 6-1 個(可分辨的)空位有多少方法,
易知,共 C^{6-1}_{3-1}=10 種。
驗算,10 種情況如下:

(4,1,1):即 4 個球在 1 號盒,1 個在 2 號,1 個在 3 號。
(3,2,1)
(2,3,1)
(1,4,1)
(3,1,2)
(2,2,2)
(1,3,2)
(1,2,3)
(2,1,3)
(1,1,4)

一般地,把 k 個不可分辨的球,放在 n 個可分辨的盒子內,且不容空盒,共 C^{k-1}_{n-1} 種放法。

(五)

johnmayhk-balls-and-boxes-02

把 k 個不可分辨的球,放在 n 個可分辨的盒子內。放球數目沒限制,即容許空盒。
這裡用的符號:H^n_r,是以前讀中學時,在數學參考書"Aids to Advanced Level Pure Mathematics Part 2 (Greenwood Press)"學到的,其意為:H^n_k=C^{n+k-1}_k
e.g.
設 k = 6 個不可分辨的球:O O O O O O;在 n = 3 個盒子分別貼上 1,2,3 號碼。

用 (OO,1),(O,2),(OOO,3) 代表 2 個球入 1 號盒,1 個球入 2 號盒,3 個球入 3 號盒;
用 (OOOO,1),(OO,3) 代表 4 個球入 1 號盒,0 個球入 2 號盒,2 個球入 3 號盒;
用 (OOOOOO,3) 代表 0 個球入 1 號盒,0 個球入 2 號盒,6 個球入 3 號盒;

固定盒號(由左至右:1,2,3),只畫出球,那麼上面 3 個情況,分別可表成:

OO,O,OOO 及
OOOO,,OO 及
,,OOOOOO

這和上段(四)不同,兩個 O 之間,不一定只能放至多 1 個逗號,可以放 2 個(見上例第二行),逗號甚或可以在第一個位或最後一位(見上例第三行)。
如何數算?我們可以想像 O 和逗號有「同等地位」,現在就有 6+2 個物件(6 個 O,2 個逗號)在排隊。
有多少種情況,即是把 2 個(相同的)逗號,放在 6+2 個(不同的)位置,共有 C^{6+2}_2=28 種。
即 6 個不可分辨的球,放在 3 個可分辨盒子,共 C^{6+2}_2=28 種放法。
一般地,把 k 個不可分辨的球,放在 n 個可分辨的盒子內,共 C^{n+k-1}_{n-1}=C^{n+k-1}_{k} 種放法。

以下 3 個涉及 S^n_k 的情況,技巧已屬 A-Level 範圍,高中同學閱讀時或會辛苦,我盡量說。

(六)

johnmayhk-balls-and-boxes-08

把 k 個可分辨的球,放在 n 個不可分辨的盒子內,且不容許空盒。

起碼兩個方法處理:
1.容斥原理
2.生成函數
個人經驗,方法 1 較方法 2 易,但想先引入 S^n_k,故先談生成函數。

設「把 k 個可分辨的球,放在 n 個不可分辨的盒子內,且不容許空盒。」的方法數有 S^n_k 種。

先想想一些簡單情況:

e.g.1 S^1_k=?
k 球入 1 盒,當然只有 1 種方式,故 S^1_k=1

e.g.2 S^k_k=?
k 球入 k 盒(不可分辨的),當然只有 1 種方式,故 S^k_k=1

e.g.3 S^2_k=?
S^2_4 為例,4 個可分辨球:{a,b,c,d},放入 2 個不可分辨的盒,情況共有 7 種,見下:
{a}{b,c,d}
{b}{a,c,d}
{c}{a,b,d}
{d}{a,b,c}
{a,b}{c,d}
{a,c}{b,d}
{a,d}{b,c}

如何數算?
兩盒名之曰 1 和 2,那麼 a 球可放於 1 或 2,兩個選擇;之後,b 球也可放於 1 或 2,又有兩個選擇;如此類推。以 tree diagram 表之如

下:

johnmayhk-2S4

可見共有 2^4 個情況。但當中,如圖指出,比如 {a,b}{c,d} 和 {c,d}{a,b} 是相同的,因為盒子本來是不可分辨的,沒有甚麼 1 號

2 號之分別;故只有 2^4\div 2=2^3 個不同情況。當中的 {a,b,c,d}{ } 是不容許的,因為我們不容許空盒。所以 S^2_4=2^3-1=7。一般地,S^2_k=2^{k-1}-1

另一個得出 S^2_k=2^{k-1}-1 的想法是,先把一個球,比如 a,放在其中一個盒子。那麼,兩個不可分辨的盒子,便有分別了(一個

有球,一個冇),變成可分辨。餘下的 k-1 個球,各有 2 個選擇入盒,共 2^{k-1} 個選擇。當中一個情況是:餘下的 k-1 個也放進已有球 a 的盒子,出現空盒,不合;故 S^2_k=2^{k-1}-1

好了,現在希望得出 S^n_k 的具體公式。以遞迴關係(recurrence relation)開始:

考慮先把一個球,比如 a,放在其中一個盒子。好了,餘下的 k-1 個球,放盒情況有兩類:

情況 1:k-1 個球皆不放在有球 a 的那盒子。
情況 2:不是情況 1。

情況 1,相當於把 k-1 個可分辨球放在 n-1 個不可分辨的盒子,且不容空盒。故共有 S^{n-1}_{k-1} 種可能。
情況 2,不是情況 1,指球 a 不孤單,有別的球和它共盒。此情況如何數算?讓我以 5 個可分辨球 {a,b,c,d,e} 放入 3 個不可分辨盒子說明

之。把 a 放某盒後,暫時無視它,考慮餘下 5-1=4 個球入 3 個盒,且不容許空盒,那麼,a 一定不孤單。而 5-1=4 球入 3 盒,且不容許空

盒的方法有 S^{3}_{5-1} 種,當中包括(比方說){b}{c}{d,e}。好了,如果把球 a 也顯示出來,可以有以下

{a,b}{c}{d,e}
{b}{a,c}{d,e}
{b}{c}{a,d,e}

3 個情況,因球 a 可放在 3 個盒的其中一個(注:放了 b,c,d,e 後,3 個盒子就變成可分辨了),於是,一般地,情況 2 有 nS^    {n}_{k-1} 種方式。結合情況 1 和 2,得

S^n_k=S^{n-1}_{k-1}+nS^{n}_{k-1}

這個遞迴關係。

如果 n 和 k 的數目不大,只要不斷運用上式,不難計算出 S^n_k。比如設 n = 3, k = 5;由上式,得

S^3_5=S^{2}_{4}+3S^{3}_{4}=(2^{4-1}-1)+3(S^2_3+3S^3_3)=7+3(2^{3-1}-1+3)=25

即「把 5 個可分辨的球,放在 3 個不可分辨的盒子內,且不容許空盒」共 25 種放法,見:

{a}{b}{c,d,e}
{a}{c}{b,d,e}
{a}{d}{b,c,e}
{a}{e}{b,c,d}
{b}{c}{a,d,e}
{b}{d}{a,c,e}
{b}{e}{a,c,d}
{c}{d}{a,b,e}
{c}{e}{a,b,d}
{d}{e}{a,b,c}

{b,c}{a}{d,e}
{b,d}{a}{c,e}
{b,e}{a}{c,d}
{a,c}{b}{d,e}
{a,d}{b}{c,e}
{c,d}{b}{a,e}
{a,b}{c}{d,e}
{a,d}{c}{b,e}
{b,d}{c}{a,e}
{a,b}{d}{c,e}
{a,c}{d}{b,e}
{b,c}{d}{a,e}
{a,b}{e}{c,d}
{a,c}{e}{d,e}
{b,c}{e}{a,e}

利用 Excel,不難表列出一些 S^n_k 的值,見下(注:這裡定義 S^0_0=1

johnmayhk-excel-nSk

現在利用生成函數(generating function),希望得出 S^n_k 的較具體的公式。

為簡化表達,以下無可避免地用到 \sum\prod 符號,可能要修 M2 的同學才比較容易看明,見諒。

對於 n\ge 0,定義

f_n(x)=\displaystyle \sum_{k=0}^{\infty}S^n_kx^k

(其中 S^0_0=1。對於 k \ge 1S^0_k=0;從而 f_0(x)=1。)

可見,S^n_kf_n(x)x^k 的系數;有辦法找出 x^k 的系數,就有辦法找到 S^n_k

好了,利用 S^n_k=S^{n-1}_{k-1}+nS^{n}_{k-1} 這個遞迴關係,得

f_n(x)

=\displaystyle \sum_{k=0}^{\infty}S^n_kx^k

=\displaystyle \sum_{k=1}^{\infty}(S^{n-1}_{k-1}+nS^{n}_{k-1})x^k

=\displaystyle x\sum_{k=1}^{\infty}S^{n-1}_{k-1}x^{k-1}+nx\sum_{k=1}^{\infty}S^{n}_{k-1}x^{k-1}

=\displaystyle x\sum_{k=0}^{\infty}S^{n-1}_{k}x^{k}+nx\sum_{k=0}^{\infty}S^{n}_{k}x^{k}

=xf_{n-1}(x)+nxf_n(x)

於是

f_n(x)=\frac{x}{1-nx}f_{n-1}(x)

更進一步,

f_n(x)

=\frac{x}{1-nx}f_{n-1}(x)

=\frac{x}{1-nx}\frac{x}{1-(n-1)x}f_{n-2}(x)

\dots

=\frac{x^n}{(1-x)(1-2x)(1-3x)\dots (1-nx)}

如何尋求 x^k 的系數?兩個步驟:

1.分解部分分式(resolve into partial fractions)
2.化成等比級數(geometric series)

詳情如下,設

\frac{x^n}{(1-x)(1-2x)(1-3x)\dots (1-nx)}\equiv 1+\frac{x^n-(1-x)(1-2x)(1-3x)\dots (1-nx)}{(1-x)(1-2x)(1-3x)\dots (1-nx)}\equiv 1+\displaystyle \sum^{n}_{j=1}\frac{a_j}{1-jx}

x^n\equiv (1-x)(1-2x)(1-3x)\dots (1-nx)+\displaystyle \sum^n_{j=1}a_j\prod_{1\le i \le n,i\ne j}(1-ix)

代入 x=\frac{1}{j} (其中 j=1,2,\dots n)得

\frac{1}{j^n}=a_j(1-\frac{1}{j})(1-\frac{2}{j})(1-\frac{3}{j})\dots (1-\frac{j-1}{j})(1-\frac{j+1}{j})\dots (1-\frac{n}{j})

\Rightarrow \frac{1}{j}=a_j(j-1)!(-1)^{n-j}(n-j)!

\Rightarrow a_j=\frac{(-1)^{n-k}}{j!(n-j)!}=\frac{(-1)^{n-j}}{n!}C^n_j

所以

f_n(x)=\sum_{j=0}^n\frac{(-1)^{n-j}}{n!}C^n_j\frac{1}{1-jx}

好了,等比級數出場,假設級數收斂,知

1+(jx)+(jx)^2+(jx)^3+\dots =\frac{1}{1-jx}

f_n(x)=\displaystyle \sum_{j=0}^n\frac{(-1)^{n-j}}{n!}C^n_j(1+(jx)+(jx)^2+(jx)^3+\dots)

於是,x^k 的系數就是

\displaystyle \sum_{j=0}^n\frac{(-1)^{n-j}}{n!}C^n_jj^k

即是說

S^n_k=\frac{1}{n!}\displaystyle \sum_{j=0}^n(-1)^{n-j}C^n_jj^k

故,「把 5 個可分辨的球,放在 3 個不可分辨的盒子內,且不容許空盒」共

S^3_5=\frac{1}{3!}\displaystyle \sum_{j=0}^n(-1)^{3-j}C^3_jj^5=\frac{1}{3!}(C^3_1-C^3_2(2^5)+C^3_3(3^5))=25 種。

以上用了生成函數,但其實用容斥原理更直接快捷,下面再談。

補充一下,純粹因為上表有 C^n_kP^n_kH^n_k,我隨便自創符號 S^n_k,其實常見符號應是

名為第二類斯特林數(Stirling number of the second kind),維基有更詳細介紹,見:

http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

(七)

johnmayhk-balls-and-boxes-09

把 k 個可分辨的球,放在 n 個不可分辨的盒子內。

只要把情況分類成:把 k 個可分辨的球,放在 n 個不可分辨的盒子內,當中空盒數目可以是

0 個,放法共 S^n_k 種;
1 個,放法共 S^{n-1}_k 種;
2 個,放法共 S^{n-2}_k 種;

(n-1) 個,放法共 S^1_k=1 種;

即把 k 個可分辨的球,放在 n 個不可分辨的盒子內,放法共有 \displaystyle \sum^n_{r=1}S^r_k 種。

(八)

johnmayhk-balls-and-boxes-10

把 k 個可分辨的球,放在 n 個可分辨的盒子內,且不容許空盒。

先考慮情況(六),即把 k 個可分辨的球,放在 n 個不可分辨的盒子內。

比如 k=5 個可分辨的球,放在 n=3 個不可分辨的盒子內,以下是 S^3_5 種放法中的一個

{a}{b}{c,d,e}

但當盒子是可分辨,即上面其實還可以有不同排列,即盒一至盒三,由左至右可以有以下情況

{a}{b}{c,d,e}
{a}{c,d,e}{b}
{b}{a}{c,d,e}
{b}{c,d,e}{a}
{c,d,e}{a}{b}
{c,d,e}{b}{a}

共 3! 種排法;於是 5 個可分辨的球,放在 3 個可分辨的盒子內,放法共有 3!S^3_5 種。

一般地,把 k 個可分辨的球,放在 n 個可分辨的盒子內,放法共有 n!S^k_n 種。

現在以容斥原理解之。以前修應數的中學生也接觸過,先溫習一下。設(有限的)樣本空間為 S,兩個事件 A,B;以圖示之,見下

johnmayhk-venn1

n(A\bigcup B)=n(A)+n(B)-n(A\bigcap B)

n(\overline{A}\bigcap \overline{B})=n(S)-n(A\bigcup B)=n(S)-(n(A)+n(B))+n(A\bigcap B)

考慮 3 件事件 A,B,C;見下

johnmayhk-venn2

不難得出

n(\overline{A}\bigcap \overline{B}\bigcap \overline{C})

=n(S)-n(A\bigcup B\bigcup C)

=n(S)-(n(A)+n(B)+n(C))+(n(A\bigcap B)+n(B\bigcap C)+n(C\bigcap A))-n(A\bigcap B\bigcap C)

一般地,考慮 n 件事件 A_1,A_2,\dots ,A_n;可得

n(\displaystyle \bigcap^n_{i=1} \overline{A_i})

=n(S)-\displaystyle \sum^n_{i=1}n(A_i)+\displaystyle \sum_{1\le i  < j\le n}n(A_i\bigcap A_j)-\displaystyle \sum_{1\le i  < j < k\le n}n(A_i\bigcap A_j\bigcap A_k)+\dots+(-1)^{n-1}n(\displaystyle \bigcap^n_{i=1}A_i)

這就是所謂容斥原理(inclusion–exclusion principle),詳見

http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

應用在本例,

S 是 k 個可分辨的球,放在 n 個可分辨的盒子內的所有情況,即

n(S)=n^k

又設 A_i 代表「第 i 個盒子是空」這事件,不難知

n(A_i)=(n-1)^k

n(A_i\bigcap A_j)=(n-2)^k 其中 i\ne j

n(A_i\bigcap A_j\bigcap A_k)=(n-3)^k 其中 i\ne j\ne k

\dots

n(\displaystyle \bigcap^n_{i=1}A_j)=(n-n)^k=0

於是,把 k 個可分辨的球,放在 n 個可分辨的盒子內,且不容許空盒的放法共

n(\displaystyle \bigcap^n_{i=1} \overline{A_i}) 種。

由容斥原理,立即知上值是

n(S)-\displaystyle \sum^n_{i=1}n(A_i)+\displaystyle \sum_{1\le i  < j\le n}n(A_i\bigcap A_j)-\displaystyle \sum_{1\le i  < j < k\le n}n(A_i\bigcap A_j\bigcap A_k)+\dots+(-1)^{n-1}n(\displaystyle \bigcap^n_{i=1}A_i)

=n^k-C^n_1(n-1)^k+C^n_2(n-2)^k-C^n_3(n-3)^k+\dots+(-1)^{n-1}C^n_{n-1}1^k

=\displaystyle \sum^n_{j=0}(-1)^{n-j}C^n_jj^k

=n!\frac{1}{n!}\displaystyle \sum^n_{j=0}(-1)^{n-j}C^n_jj^k=n!S^n_k

注:我得承認,由容斥原則先得(八),再證(六)是很簡單的。

以下 2 個情況,涉及另一個經典問題:整數分拆(partition of integers),略談之。

(九)

johnmayhk-balls-and-boxes-11

把 k 個不可分辨的球,放在 n 個不可分辨的盒子內,且不容許空盒。

例如 k=5,n=3;有以下 2 種情況,

{O}{O O}{O O}
{O}{O}{O O O}

即 p(k,n) = p(5,3) = 2

又例如 k=7,n=3;

{O}{O}{O O O O O}
{O}{O O}{O O O O}
{O}{O O O}{O O O}
{O O}{O O}{O O O}

即 p(k,n) = p(7,3) = 4

上述放法,對應著

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

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

等情況,即把 k 分拆為 n 部份。

p(k,n) 有沒有像 S^n_k 般的遞迴關係?有,如下:

p(k,n)=p(k-1,n-1)+p(k-n,n)

可以想像以下兩種把 k 分拆為 n 部份的互斥情況:

分拆包含 1
分拆不包含 1

例如把 7 分拆為 3 部份,包含 1 者有:

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

不包含 1 者有:

2+2+3

好了,包含 1 的分拆情況有多少個,相當於把 7-1=6 分拆成 2 部份的情況有多少,即 p(7-1,3-1)=p(6,3) 種;而不包含 1 的分拆情況,例如上述的 2+2+3,把每項減 1,即 (2-1)+(2-1)+(3-1)=1+1+2;其實正是把 7-3=4 分拆為 3 個部份的其中 1 個情況;所以,一般地,

p(k,n)=p(k-1,n-1)+p(k-n,n)

當中規定

p(k,n)=0 for k < n or n < 0
p(k,0)=0 for all k > 0
p(0,0)=1

試用上式計算 p(7,3)

p(7,3)
=p(6,2)+p(4,3)
=p(5,1)+p(4,2)+p(3,2)
=1+p(3,2)+p(2,2)+p(2,1)
=1+p(2,1)+1+1=1+1+1+1=4

暫時未找到 p(k,n) 的具體公式,但可以研究其生成函數。

定義 p(k) 為把 k 分拆的所有可能數目。

例如 p(7) 是多少,且看把 7 分拆的情況

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

共 15 個,即 p(7) = 15。

(注:上 wolframalpha,輸入 partition of 7,即得結果。)

不難知 p(k) 其實是以下式子中 x^k 的系數:

\displaystyle \prod_{r=1}^{\infty}\frac{1}{(1-x^r)}

讓我以 p(7) 解說之。

要得 x^7,上述那個無限項積,只要考慮到 r=7 即可:

\displaystyle \prod_{r=1}^{7}\frac{1}{(1-x^r)}

=(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots (1+x^7+x^{14}+\dots)

例如

分拆情況 3+2+1+1,
對應項為 x^{3+2+1+1}
即 2 個 1,1 個 2,1 個 3;
即在第 1 個括弧取 x^2;第 2 個括弧取 x^2;第 3 個括弧取 x^3;其餘括弧取 1。

又例如

分拆情況 2+1+1+1+1+1,
對應項為 x^{2+1+1+1+1+1}
即 5 個 1,1 個 2;
即在第 1 個括弧取 x^5;第 2 個括弧取 x^2;其餘括弧取 1。

可見,7 有多少分拆,即有多少 x^7 的項在 \displaystyle \prod_{r=1}^{7}\frac{1}{(1-x^r)} 內產生,亦即 x^7 的系數。

之前寫過篇網誌,也是以生成函數找分拆數的,可參考下:

https://johnmayhk.wordpress.com/2009/08/31/number-of-combination-of-forming-100-dollars/

這個 p(k) 有具體公式,見下:

johnmayhk-partition

(參考 http://en.wikipedia.org/wiki/Partition_%28number_theory%29

我不懂證明上述式子,這個留待高人了。

至於 p(k,n),原來它是下式中 x^k 的系數:

\displaystyle x^n\prod_{r=1}^{\infty}\frac{1}{(1-x^r)}

略略解說一下。

比如 p(7,3),其中一個情況 4+2+1,以圖表之曰

●●●●
●●

上圖,若以各列(column)加之,即得對應的分拆法 3+2+1+1。

又例如 3+2+2,以圖表之曰

●●●
●●
●●

上圖,若以各列加之,即得對應的分拆法 3+3+1。

可見,p(7,3) 中的情況,一定對應著另一種,以 3 為最大數的分拆。

一般地,p(k,n) 中的情況,一定對應著另一種,以 n 為最大數的分拆。

所以 p(k,n) 就是「把 k 以 n 為最大數的分拆」的數目。

\displaystyle x^n\prod_{r=1}^{\infty}\frac{1}{(1-x^r)} 的每項,必已包含 x^n 這個因式,故 p(k,n) 即是 \displaystyle x^n\prod_{r=1}^{\infty}\frac{1}{(1-x^r)}x^k 的系數。

不過,就算知道 \displaystyle x^n\prod_{r=1}^{\infty}\frac{1}{(1-x^r)} 這個生成函數,以人手找較大的 p(k,n) 似乎不太方便。

(十)

johnmayhk-balls-and-boxes-12

把 k 個不可分辨的球,放在 n 個不可分辨的盒子內。由情況(九),知

0 空盒,分法 p(k,n);
1 空盒,分法 p(k,n-1);
2 空盒,分法 p(k,n-2);

n-1 空盒,分法 p(k,1);

故總放法共有 \displaystyle \sum^n_{r=1}p(k,r) 種。

以下純粹補充表中的空格,想想便明,不多說。

(十一)

johnmayhk-balls-and-boxes-13

發表迴響 »

仍無迴響。

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 位部落客按了讚: