點算的奧秘：帶上、下限的排列組合問題

在點算的奧秘：有限重覆的排列組合問題中，筆者曾經討論過「帶上、下限的排列組合」問題。當時筆者並未總結出這類問題的解答公式，原因是這類問題的解答並不簡單。在本節中，筆者將利用「容斥原理」推導這些公式。為方便讀者，現把「容斥原理」的幾條常用公式重列於下。設在某論域U中有集合S₁ ... S_n，那麼

如果S₁ ... S_n是「可交換集合」，則以上兩條公式變為

我們首先從「帶上、下限的組合」問題說起，試看以下例題。

例題1：現從A、B、C這3個字母中可重覆地抽7個出來。若其中規定包含最多1個A、最少1個B和1至2個C，問有多少種抽法？

答1：本題的A、B和C受三種不同的條件限制，分別為A的「上限」，B的「下限」和C的「上、下限」。其實我們可以把這三種條件統一為同一種－「上、下限」。對於A而言，雖然題目沒有規定它的「下限」，但A的數目顯然不能少於0，因此A實際有一個「下限」，即0。對於B而言，雖然題目沒有規定它的「上限」，但由於本題規定抽取7個字母出來，B的數目顯然不能多於7，因此B實際有一個「上限」，就是7 (或任何大於7的整數)。因此如果用a、b和c分別代表字母A、B和C的出現數目，我們可以把本題的三個限制條件表達為0 ≤ a ≤ 1；1 ≤ b ≤ 7和1 ≤ c ≤ 2。

現在我們首先解決「下限」的問題。由於本題規定了在7個字母中最少有1個B和1個C，實際上已確定了7個字母中的兩個，我們只需確定其餘5個字母，因此原來的問題已轉化為從A、B、C中抽5個出來的問題，而且原來的「下限」已完全消除，即全部轉化為0。原來的「上限」也須作出調整，由於原題規定最多只有2個C，因此在餘下的5個字母中最多只有1個C，即C的「上限」轉化為2 − 1 = 1。同理，B的「上限」也轉化為7 − 1 = 6 (註1)。因此原題的三個限制條件現轉化為0 ≤ a ≤ 1；0 ≤ b ≤ 6和0 ≤ c ≤ 1。

現設U為從A、B、C中可重覆地抽5個出來且不受任何限制的各種方法組成的集合，S_A為從A、B、C中可重覆地抽5個出來且違反第一個限制條件的各種方法組成的集合，S_B和S_C的定義照此類推。那麼本題實際上是要求|S_A' ∩ S_B' ∩ S_C'|，即符合所有條件的抽法的總數。由於三個「上限」各不相同，S_A、S_B和S_C不是「可交換集合」，因此本題只能用上面的公式(2)求解。

我們先求|U|。根據「無限重覆組合」的公式，|U| = C(3 + 5 − 1, 5) = C(7, 5) = 21。

現在求|S_A|。這個集合中的元素違反第一個條件0 ≤ a ≤ 1，即有至少2個A。由於此一情況確定了5個字母中的2個，我們只需確定餘下的3個字母，這也是一個「無限重覆組合」問題，因此應有C(3 + 3 − 1, 3) = C(5, 3) = 10，即|S_A| = 10。基於相同的推理，我們知道|S_C| = 10。接著考慮|S_B|。這個集合中的元素違反第二個條件0 ≤ b ≤ 6，即有至少7個B。但這是不可能做到的，因此|S_B| = 0。以上這三個值構成公式(2)中的S_{3, 1}，故得S_{3, 1} = 10 + 10 = 20。

接著求S_{3, 2}中各項的值，S_{3, 2}中各項所代表的集合中的元素同時違反了上述三個條件中的兩個。根據上段的討論，不存在違反第二個條件的抽法，因此我們只需考慮同時違反第一和第三個條件的抽法，即有至少2個A和2個C。由於此一情況確定了5個字母中的4個，我們只需確定餘下的1個字母，這顯然只有3種抽法(這個3亦可透過公式C(3 + 1 − 1, 1) = C(3, 1)求得)，由此可以確定S_{3, 2} = 3。

接著求S_{3, 3}，S_{3, 3}只含有一項，即|S_A ∩ S_B ∩ S_C|。由於同時違反上述三個條件是不可能做到的，因此這個集合是空集，即S_{3, 3} = 0。

至此，我們可以應用公式(2)求得本題答案為

接著讓我們把上述推理推廣到一般情況。設我們要從n類物件A₁ ... A_n中可重覆地抽取r個出來，其中每類物件的數目a₁ ... a_n須符合以下限制條件：m₁ ≤ a₁ ≤ M₁ ...... m_n ≤ a_n ≤ M_n。現在要求有多少種符合全部限制條件的不同抽法。

類似例題1，我們首先解決「下限」的問題，現設m = m₁ + ... m_n。由於「下限」的存在實際為我們確定了r個被抽取出來的物件中的m個，因此原題可轉化為從n類物件中可重覆地抽取r − m個出來的問題。同時原題的「上限」也應調整為M_i − m_i (1 ≤ i ≤ n)。現設d_i = M_i − m_i，這樣原題的限制條件便轉化為0 ≤ a₁ ≤ d₁ ...... 0 ≤ a_n ≤ d_n。

現在對這個轉化後的問題求解。設U為從上述n類物件中可重覆地抽r − m個出來且不受任何限制的各種方法組成的集合，S_i為從這n類物件中可重覆地抽r − m個出來且違反第i個限制條件的各種方法組成的集合(1 ≤ i ≤ n)。那麼本題實際上是要求|S₁' ∩ ... S_n'|。我們利用上面的公式(2)求這個值。

根據「無限重覆組合」公式，|U| = C(n + r − m − 1, r − m) = C(n + r − m − 1, n − 1)。

接著求S_{n, 1}中各項的值，即|S_i|的值(1 ≤ i ≤ n)。對於任一個i而言，違反第i個條件等同於a_i ≥ d_i + 1，即有至少d_i + 1個A_i類物件。這時我們有兩個情況要考慮，如果d_i + 1 ≤ r − m，這意味著已確定了r − m個要被抽出來的物件中的d_i + 1個，我們只需確定餘下的r − m − d_i − 1個物件。因此根據「無限重覆組合」公式，|S_i| = C(n + r − m − d_i − 1 − 1, r − m − d_i − 1) = C(n + r − m − d_i − 2, n − 1)。但如果d_i + 1 > r − m，那麼這r − m個要被抽出來的物件中根本不可能包含最少d_i + 1個A_i類物件，在此情況下，|S_i| = 0。可是我們能否繼續用上面表達|S_i|的公式來表達現在這種情況？答案很簡單，只要我們規定公式當a < b時，C(a, b) = 0便行了(註2)，因為如果d_i + 1 > r − m，那麼必有n + r − m − d_i − 2 < n − 1，因而必有|S_i| = 0。至此，筆者已求得每個|S_i|的值，因此

上式中的求和符號Σ表示對所有|S_i| (1 ≤ i ≤ n)求和。

接著求S_{n, 2}中各項的值，即|S_i ∩ S_j|的值(1 ≤ i, j ≤ n； i ≠ j)。由於這個集合的元素同時違反第i個和第j個條件，即有至少有d_i + 1個A_i類物件以及d_j + 1個A_j類物件。如果d_i + d_j + 2 ≤ r − m，這意味著已確定了r − m個要被抽出來的物件中的d_i + d_j + 2個，我們只需確定餘下的r − m − d_i − d_j − 2個物件，因此|S_i ∩ S_j| = C(n + r − m − d_i − d_j − 3, n − 1)。如果d_i + d_j + 2 > r − m，上式也能給出正確的答案：|S_i ∩ S_j| = 0。由此我們得到

上式中的求和符號Σ表示對所有|S_i ∩ S_j| (i和j涵蓋從1到n抽取兩個數字出來的所有組合)求和。

容易把以上推理推廣到S_{n, k}的情況(1 ≤ k ≤ n)，並且有

上式中的求和符號Σ表示對所有|S_x ∩ ... S_z| (x ... z涵蓋從1到n抽取k個數字出來的所有組合)求和。

最後，運用「容斥原理公式」(2)，我們最終求得「帶上、下限的組合」問題的一般解答公式：

以上公式(5)很嚇人，原因是在一般情況下，A₁ ... A_n各有其上、下限，因此S₁ ... S_n不是「可交換的集合」，不能用簡單的公式概括這些集合的元素個數。但是如果各類物件有相同的上、下限，那麼S₁ ... S_n便成了「可交換的集合」，解答公式將可大大簡化，以下筆者推導這一公式。

設我們要從n類物件A₁ ... A_n中可重覆地抽取r個出來，其中每類物件的數目a_i都滿足以下限制條件：m ≤ a_i ≤ M (1 ≤ i ≤ n)。現在要求有多少種符合全部限制條件的不同抽法。

仿照前面的推理，首先把原題轉化為以下的問題：從A₁ ... A_n中可重覆地抽取r − nm個出來，其中每類物件的數目a_i都滿足以下限制條件：0 ≤ a_i ≤ M − m (1 ≤ i ≤ n)。

集合U、S₁ ... S_n的定義跟前面完全相同。但由於現在S₁ ... S_n是「可交換的集合」，我們可以運用上面的公式(4)求解。先求|U|，易知|U| = C(n + r − nm − 1, n − 1)。

接著求n_k (1 ≤ k ≤ n)的值，即|S_x ∩ ... S_z| (這裡x ... z是從1至n中任意抽k個出來的數字)的值。由於S_x ∩ ... S_z違反了第x至第z個條件，這等同於a_x ≥ M − m + 1 ... a_z ≥ M − m + 1，即有至少M − m + 1個A_x類物件以及...M − m + 1個A_z類物件。如果k(M − m + 1) ≤ r − nm，這意味著已確定了r − nm個要被抽出來的物件中的k(M − m + 1)個，我們只需確定餘下的r − nm − k(M − m + 1)個物件，因此n_k = C(n + r − nm − k(M − m + 1) − 1, n − 1)。如果k(M − m + 1) > r − nm，上式也能給出正確的答案：n_k = 0。

最後，運用「容斥原理公式」(4)，求得以下較簡單的解答公式：

例題2：如規定1 ≤ x, y, z ≤ 5，那麼方程x + y + z = 10有多少種不同的整數解？

答2：解答「組合數學」的問題，最重要是要能看出當前問題與某些已有解答的問題的聯繫。我們可以把本題看成從x、y、z這3類物件中可重覆地抽取10個出來的問題。舉例說，上述方程的其中一種整數解x = 4, y = 4, z = 2便相當於抽取4個x、4個y和2個z出來，其總數恰好是10個。由於抽取4個x、4個y和2個z出來的次序不影響x、y和z的值，本題是一種「組合」問題。而且由於x、y和z的值有相同的上、限，本題是「帶上、下限的組合」問題，並且可以應用上面的公式(6)，其中n = 3，r = 10，m = 1，M = 5。

為方便計算，首先把公式(6)中的C(n + r − nm − k(M − m + 1) − 1, n − 1)簡化為C(3 + 10 − 3 − k(5 − 1 + 1) − 1, 3 − 1) = C(9 − 5k, 2)。接著便可以運用該公式求得答案為

解決了「帶上、下限的組合」問題後，一個很自然的想法是，能否把上述結果推廣到「帶上、下限的排列」問題？但十分遺憾的是，答案是否定的。「容斥原理」只能應用於上、下限較為簡單的「排列」問題，請看以下例題。

例題3：現從A、B、C這3個字母中可重覆地抽4個出來排序。若其中規定包含最多3個A和最少1個B，問有多少種排法？

答3：設U為從A、B、C中可重覆地抽4個出來排序且不受任何限制的各種方法組成的集合，S_A和S_A分別為違反第一和第二個限制條件的各種排法組成的集合，那麼本題是要求|S_A' ∩ S_B'|。我們運用上面的公式(2)求解。

先求|U|。根據「無限重覆部分排列」公式，|U| = 3⁴。

其次求|S_A|的值。這個集合中的元素違反第一個條件，即A的數目超過3個，這只有一個可能，就是4個被抽出來的字母全是A，所以|S_A| = 1。

再次求|S_B|的值。這個集合中的元素違反第二個條件，即B的數目少於1個，即完全沒有B而只有A、C這兩種字母，因此|S_B| = 2⁴。

接著求|S_A ∩ S_B|的值。這個集合中的元素同時違反第一和第二個條件，即有7個A和沒有B，這只有一個可能，所以|S_A ∩ S_B| = 1。

最後，運用公式(2)，求得答案為

但是對於一般的「帶上、下限的排列」，上述方法卻並不有效，原因是在「可重覆的組合」問題與「可重覆的排列」問題之間一般沒有簡單的對應關係。舉例說，假如我們要從A、B、C這3個字母中可重覆地抽7個出來排列，並規定其中包含最少1個B和2個C。儘管這兩個「下限」告訴我們共有C(3 + 4 − 1, 4) = C(6, 4) = 15種抽法，但由於這15種組合的排列數各不相同，我們只能逐一對這15種組合應用「有限重覆全排列」公式，例如B,C,C,C,C,C,C和A,A,A,B,B,C,C同為上述15種組合的其中兩種，但它們的排列數卻各不相同，前者為7! / (0! × 1! × 6!) = 7，後者則為7! / (3! × 2! × 2!) = 210。

一般地，設我們要從n類物件A₁ ... A_n中可重覆地抽取r個出來排序，其中每類物件的數目須符合某些限制條件。假如硬要寫出以上這種「帶上、下限的排列」問題的公式，恐怕只能寫成以下的樣子：

上式中的r₁! ... r_n!分別代表A₁ ... A_n類物件的數目，它們必須符合上述限制條件並且相加後其總和等於r，Σ求和符號表示對所有符合上述規定的物件組合求和。換句話說，「帶上、下限的排列」問題並無一般通用的計算公式，但我們可以把這類問題的解題過程分為兩步，在第一步中我們首先找出所有符合給定限制條件的「組合」，在第二步中我們逐一對這些「組合」應用「有限重覆全排列」公式，找出對應於這些「組合」的排列總數，然後把這些排列總數加起來。

返回數學專題