Saturday, December 15, 2012

容斥原理与应用之广义容斥

继续转载
http://chowkafat.net/Enumeration8.html

點算的奧秘：廣義容斥原理

在《點算的奧秘：容斥原理基本公式》中，筆者介紹了「容斥原理」的基本公式。這些公式可用來計算以下兩個集合的元素個數：|S₁ ∪ S₂ ∪ ... S_n|和|S₁' ∩ S₂' ∩ ... S_n'|。用日常語言來表達，上述第一個集合代表屬於S₁ ... S_n中「至少1個」集合的元素，第二個集合則代表屬於S₁ ... S_n中「剛好0個」集合的元素。以上兩個集合的共同點是，它們代表某種「極端」情況。在本節我們要把「容斥原理」推廣至更一般的集合，這些集合的元素屬於S₁ ... S_n中的「至少p個」或「剛好s個」集合，其中1 ≤ p ≤ n − 1和0 ≤ s ≤ n。

首先考慮「剛好s個」集合的情況。設有S₁ ... S_n等n個集合，現在要求屬於這n個集合中的「剛好s個」集合的那些元素的個數。我們把這個數記為N(n, s)(註1)，以下給出這個數的公式：
N(n, s) = Σ_{s ≤ k ≤ n}(−1)^{k − s} C(k, s) S_{n, k} (1) 其中S_{n, k}的定義如下。若k = 0，則把S_{n, k}定義為論域U中元素的個數，即 S_{n, 0} = |U|。若k > 0，則S_{n, k}是由C(n, k)個項加起來的總和，每個項都是由 S₁ ... S_n這n個集合中抽k個出來構成的交集的元素個數。上式就是「廣義容斥原理」(Generalized Inclusion and Exclusion Principle)的其中一種形式。以下筆者證明上述公式能正確給出N(n, s)的值，方法是證明論域中每個剛好屬於s個集合的元素在上述公式中都被加一次，而且只有這些元素被加在上述公式中(註2)。

對於論域中任何一個元素而言，這個元素屬於S₁ ... S_n中的i個集合(0 ≤ i ≤ n)，這個元素將被計算在S_{n, i}中。此外，由於這個元素也必然同時屬於這i個集合之中的k個(k < i)，因此對於任何k < i而言，這個元素必然也被計算在S_{n, j}中。但對於任何k > i而言，這個元素不可能被計算在S_{n, k}中。以上事實對於了解下面的證明是至關重要的，請讀者務必弄明白。由於i與s可以存在三種關係：i < s；i = s和i > s，以下逐一考慮這三種情況。

首先考慮i < s的情況。在這種情況下，有關元素屬於少於s個集合。由於上述公式中求和符號Σ的下限是 s，S_n,i根本不會被加進上式中。換句話說，有關元素不會被加在上述公式中。

接著考慮i = s的情況。在這種情況下，有關元素剛好屬於s個集合，即它們會被計算在S_{n, s}中，並且對於任何k < s而言，這些元素也會被計算在S_{n, k}中。但由於上述公式中求和符號Σ的下限是s，我們只須考慮S_{n, s}的情況而無須考慮比s小的情況。請注意，如果某元素剛好屬於s個集合，那麼這個元素只會出現於S_{n, s}中的某一個項(註3)，即S_{n, s}只會把這個元素計算一次。此外，由於(−1)^{s − s} = 1並且C(s, s) = 1，這些元素在上述公式中剛好被加一次。

最後考慮i > s的情況。在這種情況下，有關元素屬於超過s個集合。這類元素將被計算在S_{n, i}中，並且對於任何k < i而言，這類元素也會被計算在S_{n, k}中。但由於上述公式中求和符號Σ 的下限是s，我們只須考慮S_{n, s}、S_n,s+1 ... S_{n, i−1}、 S_{n, i}的情況。對於任何k ≤ i而言，由於從i個集合中抽k個出來構成交集共有C(i, k)種抽法，所以每個這類元素在S_{n, k}中將會被計算C(i, k)次。因此每個這類元素在上述公式中被加的次數為
Σ_{s ≤ k ≤ i}(−1)^{k − s} C(k, s) × C(i, k) (2) 現在讓我們證明上式等於0。首先我們把式(2)中的C(k, s) × C(i, k)改寫：

C(k, s) × C(i, k) × 1

	k!		i!		(i − s)!
=	-----------------	×	-----------------	×	-----------------
	(k − s)! × s!		(i − k)! × k!		(i − s)!
	i!		(i − s)!
=	-----------------	×	-----------------------
	(i − s)! × s!		(i − k)! × (k − s)!

=	C(i, s) × C(i − s, k − s)

這樣便可以把式(2)改寫成
C(i, s) × Σ_{s ≤ k ≤ i}(−1)^{k −
s} C(i − s, k − s) (註4) 接著我們對上式中求和符號Σ的變項k進行變換，變換公式為r = k − s，即用r代替上式中的k − s。但不要忘記Σ的上、限也要作相應變換。由於r = k − s，所以原來k的下限s應變為s − s = 0，而原來k的上限i則變成i − s。經過變換後，式(2)便進一步變成
C(i, s) × Σ_{0 ≤ r ≤ i−s}(−1)^r C(i − s, r) (註5) 現在把上式與「二項式定理」：(a + b)ⁿ = Σ _{0 ≤ r ≤ n} C(n, r) a^r b^{n − r}對照一下。如果把定理中的a、b和n分別設定為−1、1和i − s，便可以把式(2)進一步變成
C(i, s) × (−1 + 1)^{i − s} = 0 (註6) 至此我們證明了當i > s時，有關元素在公式(1)中將被加0次。綜合上述三種情況，我們證明了公式(1)是正確的。

請注意若把s = 0代入公式(1)，便得到
N(n, 0) = Σ_{0 ≤ k ≤ n}(−1)^k S_{n, k}     (3) 上式等同於《點算的奧秘：容斥原理基本公式》中的公式(4)(不要忘記我們把S_{n, 0}定義為|U|)，即|S₁' ∩ S₂' ∩ ... S_n'| 的公式，由此可見公式(1)的確是「容斥原理」公式的推廣。

若S₁ ... S_n是「可交換集合」，那麼公式(1)中的S_{n, k}便可以簡化如下：就某一個特定的k而言，S_{n, k}是由C(n, k)個相同的數加起來的總和，我們可以把這個相同的數記為n_k。這樣便可以把公式(1)改寫為
N(n, s) = Σ_{s ≤ k ≤ n}(−1)^{k − s} C(k, s) C(n, k) n_k 利用上面C(k, s) × C(i, k) = C(i, s) × C(i − s, k − s)的關係，上式可以化簡為
N(n, s) = C(n, s) Σ_{s ≤ k ≤ n}(−1)^{k − s} C(n − s, k − s) n_k 再對上式的求和變項k進行變換(利用r = k − s，即k = r + s)，上式最終變為
N(n, s) = C(n, s) Σ_{0 ≤ r ≤ n−s}(−1)^r C(n − s, r) n_r+s    (4) 同樣，若把s = 0代入上式，便得到
N(n, 0) = Σ_{0 ≤ r ≤ n}(−1)^r C(n, r) n_r     (5) 請注意上式等同於《點算的奧秘：容斥原理基本公式》中的公式(5)。

例題1：從A、B ... J這10類字母中可重覆地抽5個出來排列，若規定所得序列必須包含剛好4類字母(例如A-B-C-B-D是合格的序列，而A-A-C-D-E則是不合格的序列)，問有多少種合格的序列？

答1：設S_A為從上述字母中可重覆地抽5個出來排列但不包括字母A的序列組成的集合， S_B ... S_J的定義照此類推。由於包含剛好4類字母等於不包含剛好6類字母，本題所求答案為N(10, 6)。顯然S_A ... S_J是「可交換集合」，所以可用上述公式(4)求解。

接著讓我們求n_k的值。對1 ≤ k ≤ 10而言，n_k表示S_A ... S_J中k個集合構成的交集的元素個數，這個交集就是從上述字母中可重覆地抽5個出來排列但不包括其中k個字母的序列組成的集合。由於不包括其中k個字母，所以有關序列乃由餘下的10 − k個字母構成，即從10 − k個字母中可重覆地抽5個出來排成的序列。這是一個「無限重覆排列問題」，應用有關公式，得n_k = (10 − k)⁵，而n_r+6 = (10 − r − 6)⁴ = (4 − r)⁵。

最後應用公式(4)，求得答案為

N(10, 6)	= C(10, 6) Σ_{0 ≤ r ≤ 4}(−1)^r C(4, r) (4 − r)⁵
	= 210 × (1 × 4⁵ − 4 × 3⁵ + 6 × 2⁵ − 4 × 1⁵ + 1 × 0⁵)
	= 50400 □

以上筆者介紹了「剛好s個」集合的情況，接下來討論「至少p個」集合的情況。設有S₁ ... S_n等n個集合，現在要求屬於這n個集合中的「至少p個」集合的那些元素的個數。我們把這個數記為L(n, p)(註7)，現在讓我們嘗試推導這個數的公式。由於「n個集合中的至少p個」集合乃由以下各個情況構成：剛好p個集合；剛好p + 1個集合 ... 剛好n個集合，根據「加法原理」並應用公式(1)，應有

L(n, p)	= Σ_{p ≤ k ≤ n} N(n, k)
	= Σ_{p ≤ k ≤ n} Σ_{k ≤ r ≤ n} (−1)^{r − k} C(r, k) S_{n, r} (6)

接著讓我們化簡上式，這要用到多種技巧。為了方便後面的推導，首先要把上式的兩個Σ符號對調位置，但由於第二個Σ的下限依賴於第一個Σ而變化，我們在對調兩個Σ符號時必須對其上、下限作出調整，這實際上等於互換兩個變項的依賴關係。為方便讀者理解，現把兩個變項k和r的取值範圍列表如下：

k的取值範圍	k取定左欄的值後r的取值範圍
p	p, p + 1, ... n − 1, n
p + 1	p + 1, p + 2, ... n − 1, n
......	......
n − 1	n − 1, n
n	n

從上表可以看到k與r的取值範圍都是最小p，最大n，但兩者必須符合這樣的關係：k ≤ r。把式(6)的兩個 Σ對調後，應該保存這種關係，因此我們應有
L(n, p) = Σ_{p ≤ r ≤ n} Σ_{p ≤ k ≤ r} (−1)^{r − k} C(r, k) S_{n, r} 接著我們把上式中(−1)的冪次r − k分拆為r − p + p − k，把上式變為
L(n, p) = Σ_{p ≤ r ≤ n} Σ_{p ≤ k ≤ r} (−1)^{r − p} × (−1)^{p − k} C(r, k) S_{n, r} 接著我們把上式中第二個Σ後不含變項k的因子統統抽到第二個Σ前面，並且利用 (−1)^{p − k} = (−1)^{k − p}，從而把上式進一步變為
L(n, p) = Σ_{p ≤ r ≤ n} (−1)^{r − p} S_{n, r} × Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r, k) (7) 接著我們證明Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r, k) = C(r − 1, p − 1)，這樣便可以消去其中一個Σ。證明方法是這樣的：首先利用《點算的奧秘：二項式定理和多項式定理》中的公式(2)把C(r, k)寫成C(r − 1, k − 1) + C(r − 1, k)。這樣我們便得到

Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r, k)	= Σ_{p ≤ k ≤ r}(−1)^{k − p} [C(r − 1, k − 1) + C(r − 1, k)]
	= Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r − 1, k − 1) + Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r − 1, k)
	= Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r − 1, k − 1) + Σ_{p+1 ≤ k ≤ r+1}(−1)^{k − p − 1} C(r − 1, k − 1)

請注意上面最後一行其實應用了對求和變項k進行變換的運算，具體地說，就是把k寫成k − 1，並把k的上、下限同時加1。現在我們看到上面兩個求和項具有相同的形式C(r − 1, k − 1)，兩者的差別僅在於上、下限以及(−1)的冪次不同。由於前後兩個求和項中(−1)的冪次相差1，兩者中k取值相同的項都互相抵消，只剩下前者k值為p和後者k值為r + 1的項，即

Σ_{p ≤ k ≤ r}(−1)^{k − p} C(r, k)	= (−1)^{p − p}C(r − 1, p − 1) + (−1)^{r + 1 − p − 1} C(r − 1, r + 1 − 1)
	= C(r − 1, p − 1) + (−1)^{r − p} C(r − 1, r)

由於r − 1 < r，我們有C(r − 1, r) = 0。由此我們證得Σ_{p ≤ k ≤ r} (−1)^{k − p} C(r, k) = C(r − 1, p − 1)。把此一結果代入上面式(7)，我們最終得到
L(n, p) = Σ_{p ≤ r ≤ n}(−1)^{r − p} C(r − 1, p − 1) S_{n, r} (8) 上式就是「廣義容斥原理」的另一種形式。請注意若把p = 1代入公式(8)，便得到
L(n, 1) = Σ_{1 ≤ r ≤ n}(−1)^{r − 1} S_{n, r} (9) 上式等同於《點算的奧秘：容斥原理基本公式》中的公式(2)，即 |S₁ ∪ S₂ ∪ ... S_n|的公式，由此可見公式(8)的確是「容斥原理」公式的推廣。

若S₁ ... S_n是「可交換集合」，那麼公式(8)中的S_{n, r}便變成C(n, r) n_r。這樣便可以把公式(8)改寫為

L(n, p)	= Σ_{p ≤ r ≤ n}(−1)^{r − p} C(r − 1, p − 1) × C(n, r) n_r
	= Σ_{p ≤ r ≤ n}(−1)^{r − p} C(r − 1, p − 1) × C(n − 1, r − 1) × (n / r) n_r

接著利用上面C(k, s) × C(i, k) = C(i, s) × C(i − s, k − s)的關係，上式可以化簡為
L(n, p) = n × C(n − 1, p − 1) Σ_{p ≤ r ≤ n} (−1)^{r − p} C(n − p, r − p) × n_r / r 對上式的求和變項r進行變換，變換公式為j = r − p，我們最終得到
L(n, p) = n × C(n − 1, p − 1) Σ_{0 ≤ j ≤ n−p} (−1)^j C(n − p, j) × n_j+p / (j + p) (10) 同樣，若把p = 1代入上式，便得到
L(n, 1) = n × Σ_{0 ≤ j ≤ n−1}(−1)^j C(n − 1, j) × n_j+1 / (j + 1) (11) 只要利用k = j + 1對上式進行變換，並利用關係式C(n − 1, k − 1) × n / k = C(n, k) ，便可證明上式等同於《點算的奧秘：容斥原理基本公式》中的公式(3)。

例題2：從A、B ... J這10類字母中可重覆地抽5個出來排列，若規定所得序列最多只可包含4類字母 (例如A-A-B-B-C是合格的序列，而A-B-C-D-E則是不合格的序列)，問有多少種合格的序列？

答2：首先我們沿用跟答1相同的集合定義S_A ... S_J。由於包含最多4類字母等同於不含至少6類字母，本題所求答案為L(10, 6)。根據答1，n_j+6 = (4 − j)⁵。因此根據公式(10)，我們求得答案為

L(10, 6)	= 10 × C(9, 5) × Σ_{0 ≤ j ≤ 4} (−1)^j C(4, j) × (4 − j)⁵ / (j + 6)
	= 10 × 126 × (1 × 4⁵ / 6 − 4 × 3⁵ / 7 + 6 × 2⁵ / 8 − 4 × 1⁵ / 9 + 1 × 0⁵ / 10)
	= 69760 □

在本節中，筆者除了介紹「廣義容斥原理」外，還介紹了「點算組合學」上常用的多種運算技巧，包括對求和變項進行變換、把兩個求和符號Σ對調位置以及應用「點算組合學」的某些常用公式等，這些技巧在以後還會經常用到，請讀者務必掌握。
註1：按照這個記法，|S₁' ∩ S₂' ∩ ... S_n'|就等於N(n, 0)。

註2：請注意本文對公式(1)的證明只能證明它的正確性，而不能揭示該公式是如何推導出來的。這一點與「數學歸納法」的證明有點類似。

註3：因為如果某元素出現於S_{n, s}中的兩個或更多不同的項，那麼這個元素就一定同時屬於不只s 個集合。舉例說，設s為3，並設某元素x既出現於S₁ ∩ S₂ ∩ S₃ ，又出現於S₂ ∩ S₃ ∩ S₄，那麼x便同時屬於4個而非3個集合。

註4：由於C(i, s)的i和s兩者都不等於式(2)求和符號Σ中的變項k，所以我們可以把C(i, s)從Σ的右邊抽出來。這種做法就正如我們可以從(a × b + a × c)中把a抽出來，使之成為a × (b + c)一樣。

註5：學過微積分的讀者對這種變換應不會感到陌生，因為在進行積分時經常要對積分變項進行變換。事實上，我們可以把「求和」(Summation)看成一種「離散」的「積分」(Integration)，或者把「積分」看成一種「連續」的「求和」。

註6：由於我們在前面假定了i > s，即i − s > 0，所以這裡(−1 + 1)^{i − s}有定義，即等於0。

註7：按照這個記法，|S₁ ∪ S₂ ∪ ... S_n|就等於L(n, 1)。

返回數學專題

容斥原理与应用

写了半天，原来这个写的很好了
http://chowkafat.net/Enumeration6.html

點算的奧秘：容斥原理基本公式

「容斥原理」(Principle of Inclusion and Exclusion)(亦作「排容原理」)是「點算組合學」中的一條重要原理。但凡略為複雜、包含多種限制條件的點算問題，都要用到這條原理。現在首先從一個點算問題說起。

例題1：設某班每名學生都要選修至少一種外語，其中選修英語的學生人數為25，選修法語的學生人數為18，選修德語的學生人數為20，同時選修英語和法語的學生人數為8，同時選修英語和德語的學生人數為13 ，同時選修法語和德語的學生人數為6，而同時選修上述三種外語的學生人數則為3，問該班共有多少名學生？

答1：我們可以把上述問題表達為下圖：

其中紅色、綠色和藍色圓圈分別代表選修英語、法語和德語的學生。根據三個圓圈之間的交叉關係，可把上圖分為七個區域，分別標以A至G七個字母。如果我們用這七個字母分別代表各字母所在區域的學生人數，那麼根據題意，我們有以下七條等式：(1) A+D+E+G = 25；(2) B+D+F+G = 18；(3) C+E+F+G = 20；(4) D+G = 8； (5) E+G = 13；(6) F+G = 6；(7) G = 3。現在我們要求的是A+B+C+D+E+F+G。如何利用以上資料求得答案？

把頭三條等式加起來，我們得到A+B+C+2D+2E+2F+3G = 63。可是這結果包含了多餘的D、E、F和G，必須設法把多餘的部分減去。由於等式(4)－(6)各有一個D、E和F，若從上述結果減去這三條等式，便可以把多餘的D、E和 F減去，得A+B+C+D+E+F = 36。可是這麼一來，本來重覆重現的G卻變被完全減去了，所以最後還得把等式(7)加上去，得最終結果為A+B+C+D+E+F+G = 39，即該班共有39名學生。□

在以上例題中，給定的資料是三個集合的元素個數以及這些集合之間的交集的元素個數。在該題的解答中，我們交替加上及減去這些給定的資料。如果我們用S₁、S₂和S₃分別代表選修英語、法語和德語學生的集合，那麼我們要求的答案就是|S₁ ∪ S₂ ∪ S₃|，而該題的解答則可以重新表達為
|S₁ ∪ S₂ ∪ S₃| = (|S₁| + |S₂| + |S₃|) − (|S₁ ∩ S₂| + |S₁ ∩ S₃| + |S₂ ∩ S₃|) + |S₁ ∩ S₂ ∩ S₃| 我們可以把上式推廣至集合個數為n的情況，便得到以下的「容斥原理」。設有n個集合 S₁、S₂ ... S_n，那麼

\|S₁ ∪ S₂ ∪ ... S_n\| =	(\|S₁\| + \|S₂\| + ... \|S_n\|)
	− (\|S₁ ∩ S₂\| + \|S₁ ∩ S₃\| + ... \|S_{n − 1} ∩ S_n\|)
	+ (\|S₁ ∩ S₂ ∩ S₃\| + \|S₁ ∩ S₂ ∩ S₄\| + ... \|S_{n − 2} ∩ S_{n − 1} ∩ S_n\|)
	− (\|S₁ ∩ S₂ ∩ S₃ ∩ S₄\| + ... \|S_{n − 3} ∩ S_{n − 2} ∩ S_{n − 1} ∩ S_n\|)
	......
	+ (−1)^{n − 1} \|S₁ ∩ S₂ ∩ ... S_{n − 1} ∩ S_n\| (1)

有必要對上式作一些解釋。為易於理解，上式分數行列出，每一行都是一些集合元素個數的總和，其中第1行包含全部n個集合S₁、S₂ ... S_n；第2行包含所有由2個集合構成的交集，應共有C(n, 2)個項；第3行包含所有由3個集合構成的交集，應共有C(n, 3)個項...第n行包含由全部n個集合構成的交集，這樣的交集只有C(n, n) = 1個。每行的開首交替為一個「加」(相當於「容納」)和一個「減」(相當於「排斥」)號，第1行開首為「加」號，第2行為「減」號，第3行為「加」號，第4行為「減」號...。由於當k 為奇數時，(−1)^k = −1；當k為偶數時，(−1)^k = 1，我們可以把第1行開首的「加」號改寫為「+ (−1)⁰」，把第2行開首的「減」號改寫為「+ (−1)¹」...如此類推，我們可知第k行開首應有一個「+ (−1)^{k − 1}」。

我們還可以把上式化簡，方法是引入一個新的變項S_{n, k}來代表上式等號右邊的第k行。 S_{n, k}是由C(n, k)個項加起來的總和，每個項都是由S₁、S₂ ... S_n這n個集合中抽r個出來構成的交集的元素個數。舉例說，當n = 5，k = 3時，S_{5, 3} 是由C(5, 3) = 10個項加起來的總和，這10個項都是由S₁ ... S₅這5個集合中抽3個出來構成的交集的元素個數，其中一個是|S₂ ∩ S₄ ∩ S₅|，其餘類推。利用S_{n, k}以及Σ求和符號，我們便可以把上面的「容斥原理」公式大大簡化為：
|S₁ ∪ S₂ ∪ ... S_n| = Σ_{1 ≤ k ≤ n}(−1)^{k − 1} S_{n, k} (2) 接著讓我們證明以上「容斥原理」公式(1)的正確性，為此我們必須證明，S₁ ... S_n 這n個集合中的每一個元素在公式中都只被加一次。我們逐一考慮各種集合元素的情況。首先考慮那些只包含於一個集合中的元素，每個這類元素只出現於上述公式的第1行n個集合的其中一個，因此只會被加一次。其次考慮那些包含於兩個集合的元素，每個這類元素都出現於上述公式的第1行n個集合的其中兩個，並且出現於第2行 C(n, 2)個交集的其中一個。由於每個這類元素在第1行中被加兩次並在第2行中被減一次，因此結果該元素在公式中被加一次。

我們把上述推理推廣至一般情況，即考慮那些包含於k個集合的元素。每個這類元素都出現於第1行的其中 C(k, 1) = k個集合，並且出現於第2行的其中C(k, 2)個交集，並且出現於第3行的其中C(k, 3)個交集...並且出現於第k行的其中C(k, k) = 1個交集(註1)。總括而言，每個這類元素在公式中被加的次數為
C(k, 1) − C(k, 2) + C(k, 3) − C(k, 4) ... (−)^{k − 1} C(k, k) = Σ_{1 ≤ r ≤ k}(−1)^{r − 1} C(k, r) 現在的問題是，如何證明上式等於1？答案是借助《點算的奧秘：二項式定理和多項式定理》中介紹的「二項式定理」：(a + b)ⁿ = Σ _{0 ≤ r ≤ n} C(n, r) a^r b^{n − r}。為了應用「二項式定理」，我們首先把上式等號右邊重寫：

Σ_{1 ≤ r ≤ k}(−1)^{r − 1} C(k, r)	= − Σ_{1 ≤ r ≤ k}(−1)^r C(k, r)
	= − [Σ_{0 ≤ r ≤ k}(−1)^r C(k, r) − (−1)⁰ C(k, 0)]
	= − Σ_{0 ≤ r ≤ k}C(k, r) (−1)^r + 1

現在如果把「二項式定理」中的a、b和n分別設定為−1、1和k，便得到Σ_{0 ≤ r ≤ k}C(k, r) (−1)^r = (−1 + 1)^k = 0。把這個結果代入上面最後一行，我們便得到Σ_{1 ≤ r ≤ k}(−1)^{r − 1} C(k, r) = −0 + 1 = 1。至此我們證明了每一個元素在「容斥原理」公式中都被加一次，因此該公式是正確的。

在應用上述「容斥原理」公式(1)時，我們必須逐一找出所有集合以及各種交集的元素個數，有時這是頗為繁瑣的工作，會令上述公式失去價值，因此「容斥原理」一般應用於「可交換集合」(Exchangeable Sets)。如果從 n個集合S₁、S₂ ... S_n中任意抽取k個出來(1 ≤ r ≤ n)，所得交集的元素個數只跟k有關，而跟抽取結果無關，則我們說這n個集合是「可交換」的。換句話說，不論是由哪k個集合構成的交集，所得交集的元素個數都是同一個數字。

上面「容斥原理」公式(1)的第k行的每一項都是由k個集合構成的交集的元素個數。如果S₁、 S₂ ... S_n是「可交換集合」，那麼該行的每一項都是同一個數字，可不妨用符號 n_k來代表。由於該行共有C(n, k)個項，所以該行可簡化為(−1)^{k − 1} C(n, k) n_k。因此，「可交換集合」的「容斥原理」公式便是
|S₁ ∪ S₂ ∪ ... S_n| = Σ_{1 ≤ k ≤ n}(−1)^{k − 1} C(n, k) n_k     (3) 在某些應用中，所求的答案是不屬任何指定集合的元素個數，因此我們需要找出以上「容斥原理」公式的變化形式。設某論域U包含n個集合S₁、S₂ ... S_n，現在我們要求不屬這n個集合的任何一個的元素個數，即|S₁' ∩ S₂' ∩ ... S_n'|(註2)。根據集合論的「德.摩根律」(De Morgan's Law)，S₁' ∩ S₂' ∩ ... S_n'等於U − (S₁ ∪ S₂ ∪ ... S_n)，因此 |S₁' ∩ S₂' ∩ ... S_n'| = |U| − |S₁ ∪ S₂ ∪ ... S_n| = |U| + (−|S₁ ∪ S₂ ∪ ... S_n|)(註3)。應用上面的「容斥原理」公式(2)，我們便得到
|S₁' ∩ S₂' ∩ ... S_n'| = |U| + Σ_{1 ≤
k ≤ n}(−1)^k S_{n, k}     (4) 同理，如果S₁、S₂ ... S_n是「可交換集合」，那麼上式便變成
|S₁' ∩ S₂' ∩ ... S_n'| = |U| + Σ_{1 ≤
k ≤ n}(−1)^k C(n, k) n_k     (5) 現在讓我們來看看「容斥原理」的一些簡單應用例子。有關該原理的其他應用，以後還會談到。

例題2：從26個英文字母中(可重覆地)抽取10個出來排成字串(String)(無需考慮這個字串是否構成一個英文單詞)，其中不可包含全部5個元音字母(即A、E、I、O、U)，問有多少種排法？

答2：利用「容斥原理」解題的關鍵在於，把原題表達為適當的集合。就本題而言，如果我們用 S_A來代表所有由10個字母組成但不含A的字串集合...用S_U來代表所有由10個字母組成但不含U的字串集合，那麼本題所要求的答案就是|S_A ∪ S_E ∪ S_I ∪ S_O ∪ S_U|。由於5個元音字母具有平等的地位，從S_A、 S_E、S_I、S_O和S_U這5個集合中任意抽取k個出來所構成的交集的元素個數都是一樣的，所以這5個集合是「可交換」的。因此我們可以用上面的公式(3)來解題，但須先求得 n_k (1 ≤ k ≤ 5)的值。

我們先求n₁的值，這個值相當於由10個字母組成但不含A、E、I、O、U中某一個字母的字串的數目。由於撇除了一個字母，我們可以從餘下的25個字母中(可重覆地)抽取10個出來排成字串，這是一個「無限重覆排列」問題，應共有25¹⁰個這樣的字串，即n₁ = 25¹⁰。

接著考慮n₂，這個值相當於由10個字母組成但不含A、E、I、O、U中某兩個字母的字串的數目。由於撇除了兩個字母，我們可以從餘下的24個字母中(可重覆地)抽取10個出來排成字串，因此n₂ = 24¹⁰。讀到這裡，相信讀者應能看到n_k = (26 − k)¹⁰。

最後，運用上面公式(3)，本題的答案是
Σ_{1 ≤ k ≤ 5}(−1)^{k − 1} C(5, k) (26 − k) ¹⁰ = 5 × 25¹⁰ − 10 × 24¹⁰ + 10 × 23¹⁰ − 5 × 22¹⁰ + 21¹⁰ 由於具體數字太大，這裡只列出其算式。事實上，「點算組合學」經常要和這樣的「天文數字」打交道。若非靠邏輯思維，實在難以想像人類有何方法求得這類問題的答案，由此可見邏輯思維的巨大力量！□

例題3：現要把一對可區別的火星人、一對可區別的木星人和一對可區別的土星人安排坐在一排共6個座位上。如規定同一類外星人不得坐在相鄰的位置上，問有多少種不同坐法？

答3：如果我們用U代表由各種不加限制的坐法組成的集合，並用S_M(S_J、 S_S)代表由兩個火星人(木星人、土星人)坐在相鄰位置的各種坐法組成的集合，那麼本題要求的答案就是|S_M' ∩ S_J' ∩ S_S'|。本題的S_M、 S_J和S_S顯然是「可交換」的集合，因此可以用上面的公式(5)解題。

首先求|U|的值。由於6個外星人是可區別的，我們不妨用M₁、M₂、J₁、 J₂、S₁、S₂代表他們(其中M、J和S分別代表火星人、木星人和土星人)。因此|U|的值等於把上述6個符號進行「全排列」的問題，故|U| = 6!。

接著求n₁的值，這個值相當於兩個火星人(或木星人、土星人)坐在相鄰位置的各種坐法的總數。由於M₁、M₂總是聚在一塊，我們可以先把M₁和M₂合併為一個符號M，然後求這個M與其餘4個符號進行「全排列」的總數，這個數應為5!。接著考慮M的「內部構造」， M₁和M₂有兩種可能形式構成M，即M₁-M₂和 M₂-M₁。總上所述，得n₁ = 5! × 2。

接著求n₂的值，這個值相當於兩個火星人以及兩個木星人(或其他組合)坐在相鄰位置的各種坐法的總數。類似上段的做法，我們可以先把M₁和M₂以及J₁和J₂合併為兩個新的符號M和J，然後求M、J與其餘2個符號進行「全排列」的總數，這個數應為4!。接著考慮M和J的「內部構造」，各有兩種可能形式。總上所述，得n₂ = 4! × 2²。

接著求n₃的值，這個值相當於兩個火星人、兩個木星人和兩個土星人坐在相鄰位置的各種坐法的總數。同樣，我們可以先把M₁和M₂、J₁和J₂以及S₁ 和S₂合併為三個新的符號M、J和S，然後求M、J和S進行「全排列」的總數，這個數應為3!。接著考慮M、J和S的「內部構造」，各有兩種可能形式。總上所述，得n₃ = 3! × 2³。

最後，運用上面的公式(5)，求得本題答案為

	\|U\| − C(3, 1) n₁ + C(3, 2) n₂ − C(3, 3) n₃
=	6! − 3 × 5! × 2 + 3 × 4! × 2² − 1 × 3! × 2³
=	720 − 720 + 288 − 48
=	240 □

註1：如果讀者不明白本段的推理，可以嘗試用一個具體的例子代入上述推理，這樣便能較易明白。設n = 5，k = 4，並且假設某元素x包含於S₁、S₃、S₄和S₅這4個集合中。那麼x出現於第1行的其中C(4, 1) = 4個集合，並且出現於第2行的其中C(4, 2) = 6個交集，這6個交集分別是 S₁ ∩ S₃、S₁ ∩ S₄、S₁ ∩ S₅、S₃ ∩ S₄、S₃ ∩ S₅和 S₄ ∩ S₅。在第3行中，x出現於C(4, 3) = 4個交集，這4個交集分別是 S₁ ∩ S₃ ∩ S₄、S₁ ∩ S₃ ∩ S₅、S₁ ∩ S₄ ∩ S₅和S₃ ∩ S₄ ∩ S₅。在4行中，x只出現於C(4, 4) = 1個交集，此即S₁ ∩ S₃ ∩ S₄ ∩ S₅。請注意x不會出現於第5行。總括而言，x在公式中被加的次數為4 − 6 + 4 − 1 = 1次。

註2：這裡用S'代表集合S的補集(Complement Set)，即S' = U − S。

註3：這裡其實應用了集合論中的一個原理，即若T是S的子集，那麼|S − T| = |S| − |T|。

Friday, December 14, 2012

备用将DD-MM-YYYY HH:MM:SS转化为SQLite 支持的YY-MM-DD HH:MM:SS

UPDATE t2 SET Comeback_Date = (SELECT CASE WHEN (SUBSTR(Comeback_Date,-8,1)=' ') THEN SUBSTR(Comeback_Date,-12,4) ELSE SUBSTR(Comeback_Date,-13,4) END)|| '-'|| (SELECT CASE WHEN (CAST(SUBSTR(Comeback_Date,1,2) AS INTEGER) >=10 and SUBSTR(Comeback_Date,5,1)!='-') THEN SUBSTR(Comeback_Date,4,2) WHEN (CAST(SUBSTR(Comeback_Date,1,2) AS INTEGER) >=10 and SUBSTR(Comeback_Date,5,1)='-') THEN SUBSTR(Comeback_Date,4,1) WHEN (CAST(SUBSTR(Comeback_Date,1,2) AS INTEGER) <10 and SUBSTR(Comeback_Date,4,1)='-') THEN SUBSTR(Comeback_Date,3,1) ELSE SUBSTR(Comeback_Date,3,2) END)|| '-'|| (SELECT CASE WHEN (CAST(SUBSTR(Comeback_Date,1,2) AS INTEGER) >=10) THEN SUBSTR(Comeback_Date,1,2) ELSE SUBSTR(Comeback_Date,1,1) END) ||' '|| (SELECT CASE WHEN SUBSTR(Comeback_Date,-8,1)=' 'THEN SUBSTR(Comeback_Date,-7) ELSE SUBSTR(Comeback_Date,-8) END) where Comeback_Date is not null;

update t1 set comeback_date=(substr(comeback_date, 1,4)||'-'||
(select case when(cast(substr(comeback_date,6,2) as integer)>=10) then substr(comeback_date,6,2) else '0'||substr(comeback_date,6,1) end) ||'-'||
(select case when(cast(substr(comeback_date,8,2) as integer)>=10) then substr(comeback_date,8,2) when(cast(substr(comeback_date,9,2) as integer)>=10) then substr(comeback_date,9,2) when(cast(substr(comeback_date,8,2) as integer)>0) then '0'||substr(comeback_date,8,1) else '0'||substr(comeback_date,9,1) end) ||' '||(select case when (substr(comeback_date,-8,1)=' ') then '0'||substr(comeback_date,-7) else substr(comeback_date,-8) end)
)
where comeback_date is not null

Tuesday, November 27, 2012

排列数、组合数生成算法

输入n，r
输出C（r，n），A（r，n）即所有的排列方式，组合方式

先考虑组合，如果能够得到所有的组合数情况，只要分别对这些组合做排列计算即可
要想输出所有的组合情况，必须按照一定的次序，可以按照字典顺序输出所有情况。假设n=4，r=2，那么第一个组合数是1 2，第二个是13。。。第六个是3 4。可以看出组合数的倒数第一位不超过n，倒数第二位不超过n-1，。。。倒数第r位不能超过n-r+1，同时右边的数总是大于左边的数。所以对于任意给定的一个组合，如果其最右边没达到所能达到的最大值，只需将最右边数+1即可得到下一个组合数，如果最右边已经不能再大了，考虑倒数第二位，如果倒数第二位没有达到最大值，将倒数第二位+1，同时这位以后的数字依次比前一个数大1，如果倒数第二位不能再大了，考虑倒数第三位，将倒数第三位+1，同时这位以后的数字依次比前一个数大1。。。。直到倒数第r个数即第一个数已经不能再大了
算法实现如下：

int next_combination(int *num, int n, int r)
{
bool has_next = false;
int i = 0;
for (i = 0; i < r; i++)
if (num[r - i - 1] < n - i) {
num[r - i - 1]++;
has_next = true;
break;
}
if (has_next) {
for (int j = i; j > 0; j--) {
num[r - j] = num[r - j - 1] + 1;
}
return 1;
}
return 0;
}

下面考虑排列
这里也按照字典顺序输出所有排列，假设有排列S₁，S₂，，。。。S_n，要想得到下一个排列，则需要从右向左扫描，找出第一个位置S_m，满足S_m<S_m+1，S_m左边的部分不变，调整S_m及其右边部分即可得到下一个排列。S_m右边部分是递减的，从右向左扫描，找出第一个S_k，满足S_k>S_m，交换S_k，S_m的值，现在的情况是，从S_m+1到S_n是递减的，再将这部分元素逆置，得到最终结果，算法描述如下：

int next_permutation(int *num, int n)
{
if (n <= 1)
return 0;
int m = n - 2;
while (num[m] > num[m + 1] && m >= 0)
m--;
if (m < 0)
return 0;
int k = n - 1;
while (num[m] > num[k])
k--;
std::swap(num[m], num[k]);
int p = m + 1;
int q = n - 1;
while (p < q) {
std::swap(num[p], num[q]);
p++;
q--;
}
return 1;
}

回到开头，输入n，r，先调用next_combination得到一个排列，再对这个排列调用next_permutation即可得到最后的排列情况。如果只需要组合情况，只需调用next_combination

测试程序：

for (int i = 0; i < r; i++)

res[i] = i + 1;

int *tmp = new int[r];

do {

memcpy(tmp, res, r * sizeof(int));

do {

output_combination(tmp, r);

} while (next_permutation(tmp, r));

} while (next_combination(res, n, r));

delete tmp;

delete res;

Wednesday, November 21, 2012

要把第一次实现RMI的过程记录下来

服务器端：
定义客户端要访问的接口
package com.tx.distributed;

import java.rmi.Remote;
import java.rmi.RemoteException;

public interface TimeGenerator extends Remote {

    java.util.Date getCurrentTime() throws RemoteException;

    String sayHello() throws RemoteException;

    void attach(DistributedClient obj, long d) throws RemoteException;

    void detach(DistributedClient obj) throws RemoteException;
}

实现接口
package com.tx.distributed;

import java.io.Serializable;
import java.rmi.NotBoundException;
import java.rmi.RMISecurityManager;
import java.rmi.RemoteException;
import java.rmi.registry.LocateRegistry;
import java.rmi.registry.Registry;
import java.rmi.server.UnicastRemoteObject;
import java.util.Calendar;
import java.util.Date;
import java.util.HashMap;

public class TimeGeneratorImpl implements TimeGenerator, Serializable {

    /**
    *
    */
    private static final long serialVersionUID = -3123942071701576393L;

    /**
    *
    */
    private HashMap<DistributedClient, Object> clients = new HashMap<DistributedClient, Object>();

    protected TimeGeneratorImpl() throws RemoteException {
        super();
    }

    public static void main(String[] args)
    {
        if (System.getSecurityManager() == null) {
            System.setSecurityManager(new RMISecurityManager());
        }
        try {
            String name = "TimeGenerator";
            TimeGenerator timeGenerator = new TimeGeneratorImpl();
            TimeGenerator stub = (TimeGenerator) UnicastRemoteObject
                    .exportObject(timeGenerator, 0);
            Registry registry = LocateRegistry.getRegistry();
            registry.rebind(name, stub);
            TimeGenerator t = (TimeGenerator) registry.lookup(name);
            System.out.println("Server started on: " + t.getCurrentTime());
        } catch (RemoteException e) {
            e.printStackTrace();
        } catch (NotBoundException e) {
            e.printStackTrace();

        }

    }

    @Override
    public Date getCurrentTime() throws RemoteException
    {
        Date date = new Date();

        return date;
    }

    @Override
    public String sayHello() throws RemoteException
    {
        return "Hello";
    }

    @Override
    public void attach(DistributedClient obj,long d) throws RemoteException
    {
        clients.put(obj, "");
        obj.update(new Date(Calendar.getInstance().getTimeInMillis() + d));
    }

    @Override
    public void detach(DistributedClient obj) throws RemoteException
    {
        clients.remove(obj);
    }

}
客户端回调接口
package com.tx.distributed;

import java.rmi.Remote;
import java.rmi.RemoteException;
import java.util.Date;

public interface DistributedClient extends Remote {
    public void update(Date d) throws RemoteException;
}
客户端
定义服务器端接口，跟服务器端接口一样
package com.tx.distributed;

import java.rmi.Remote;
import java.rmi.RemoteException;

public interface TimeGenerator extends Remote {
    java.util.Date getCurrentTime() throws RemoteException;

    String sayHello() throws RemoteException;

    void attach(DistributedClient obj, long d) throws RemoteException;

    void detach(DistributedClient obj) throws RemoteException;
}
模拟时钟客户端定义了回调函数的操作
package com.tx.distributed;

import java.io.Serializable;
import java.rmi.RemoteException;
import java.rmi.server.UnicastRemoteObject;
import java.util.Date;

public class AnalogueClock extends UnicastRemoteObject implements Serializable,
        DistributedClient {

    protected AnalogueClock() throws RemoteException {
        super();
    }

    /**
    *
    */
    private static final long serialVersionUID = -3432644283769542956L;

    @Override
    public void update(Date d) throws RemoteException
    {
        System.out.println("Analogue: " + d);
    }

}

实验
package com.tx.distributed;

import java.rmi.NotBoundException;
import java.rmi.RMISecurityManager;
import java.rmi.RemoteException;
import java.rmi.registry.LocateRegistry;
import java.rmi.registry.Registry;
import java.util.Date;

public class Test {

    /**
    * @param args
    */
    public static void main(String[] args)
    {
       if (System.getSecurityManager() == null) {
           System.setSecurityManager(new RMISecurityManager() {
               @Override
               public void checkConnect(String host, int port)
               {
               }

               @Override
               public void checkConnect(String host, int port, Object context)
               {
               }
           });
       }

       try {
           String name = "TimeGenerator";
           Registry registry = LocateRegistry.getRegistry("114.212.81.47");
           TimeGenerator timeGenerator = (TimeGenerator) registry.lookup(name);
           Date date = timeGenerator.getCurrentTime();
           System.out.println("Current time: " + date);
           AnalogueClock analogueClock = new AnalogueClock();
           DigitalClock digitalClock = new DigitalClock();
           timeGenerator.attach(analogueClock, 3600000);
           timeGenerator.attach(digitalClock, 3600000 * 2);
       } catch (RemoteException e) {
           e.printStackTrace();
       } catch (NotBoundException e) {
           e.printStackTrace();
       }
    }

}

Thursday, November 15, 2012

2n个MM围成一圈，求相互接吻而不打扰另一对的方法数

将2n个人从0开始编号，从0到2n-1，从此往后，0只能和奇数号MM接吻，否则和一个偶数号MM发生关系的情况下，她们中间剩下奇数个MM，最后必然落单一个人
假设2n个人共有h（n）种接吻方法，当0号MM和1号MM接吻时，仅剩下2n-2个人，共有h(n-1)种方法，当0号MM和3号MM接吻时，她们的一边有2个人，有h（1）种方法，一边有2n-4个人，有h（n-2）种方法，当0号MM和5号MM接吻时，她们的一边有4个人，有h（2）种方法，一边有2n-6个人，有h（n-3）种方法，。。。。当0号MM和2n-1号MM接吻时，仅剩下2n-2个人，共有h（n-1)种方法。
可见，h（n）=h（0）×h（n-1）+h（1）×h（n-2）+h（2）×h（n-3）+......+h（n-1）×h（0）
这是Catalan数的一种形式，共有C（n，2n）/（n+1）种方法。

Wednesday, October 31, 2012

Euclidean时间复杂度

gcd(a, b) = gcd(b, r) r=a%b
每调用一次gcd，需要计算一次a%b，所以gcd的时间复杂度可用a%b的执行次数衡量。
Finonacci序列 1, 2, 3, 5, 8, 13, ...f₁ =1, f₂=2, ...f_k=f_k-1+f_k-2

a	b	求余运算次数
1	0	0
2	1	1
3	2	2
5	3	3
8	5	4
13	8	5
21	13	6

从上图出发，可以假设若欧几里德算法执行n次时，a>=f_n+1, b>=f_n

证明：

当n=1时假设成立，假设在n时成立，只需证当n+1时成立即可

假设 gcd(a, b)需要执行n+1次，r=a%b, 则 gcd(b, r)需要执行n次

所以有 b>=f_n+1，r>=f_n，a = bq + r >= b + r >=f_n+1 + f_n = f_n+2

从而有a>=f_n+2， b>=f_n+1 所以假设在n+1时也成立

\|S₁ ∪ S₂ ∪ ... S_n\| =	(\|S₁\| + \|S₂\| + ... \|S_n\|)
	− (\|S₁ ∩ S₂\| + \|S₁ ∩ S₃\| + ... \|S_{n − 1} ∩ S_n\|)
	+ (\|S₁ ∩ S₂ ∩ S₃\| + \|S₁ ∩ S₂ ∩ S₄\| + ... \|S_{n − 2} ∩ S_{n − 1} ∩ S_n\|)
	− (\|S₁ ∩ S₂ ∩ S₃ ∩ S₄\| + ... \|S_{n − 3} ∩ S_{n − 2} ∩ S_{n − 1} ∩ S_n\|)
	......
	+ (−1)^{n − 1} \|S₁ ∩ S₂ ∩ ... S_{n − 1} ∩ S_n\| (1)