集合划分问题（转）

 

一個集合的「劃分」(Partition)就是把該集合的素劃歸一些子集，使得這些子集兩兩不相交(Disjoint)(亦稱「互斥」Mutually Exclusive)，而且這些子集合起來包羅所有素(即「窮盡」Completely Exhaustive)。 一个集合的「划分」(Partition)就是把该集合的素划归一些子集，使得这些子集两两不相交(Disjoint)(亦称「互斥」Mutually Exclusive)，而且这些子集合起来包罗所有素(即「穷尽」Completely Exhaustive)。 用數學語言來表達，一個集合A的「劃分」就是由這個集合的子集A ₁ 、A ₂ ... A _n 組成的集合{A ₁ , A ₂ ... A _n }，其中A ₁ ∪ A ₂ ∪ ... A _n = A，並且A _i ∩ A _j = Φ (i, j = 1、2 ... n，i ≠ j)(這裡Φ代表「空集」)。 用数学语言来表达，一个集合A的「划分」就是由这个集合的子集A ₁ 、A ₂ ... A _n 组成的集合{A ₁ , A ₂ ... A _n }，其中A ₁ ∪ A ₂ ∪ ... A _n = A，并且A _i ∩ A _j = Φ (i, j = 1、2 ... n，i ≠ j)(这里Φ代表「空集」)。

「集合劃分」問題就是以下的問題，設某個集合A共有r個素，現要把A劃分為n個子集A ₁ ... A _n ，共有多少種不同劃分法？ 「集合划分」问题就是以下的问题，设某个集合A共有r个素，现要把A划分为n个子集A ₁ ... A _n ，共有多少种不同划分法？ 按照是否容許在A ₁ ... A _n 中存在空集，「集合劃分」問題可分為「不容許空集的集合劃分」問題和「容許空集的集合劃分」問題這兩大類。 按照是否容许在A ₁ ... A _n 中存在空集，「集合划分」问题可分为「不容许空集的集合划分」问题和「容许空集的集合划分」问题这两大类。 舉例說，設A共有3個素(不妨稱它們命名為1、2和3)，現要把它們劃分為2個非空子集，那麼應共有以下3種劃分法(請注意以下用「集合的集合」Set of Sets，或稱「集合族」Family of Sets來代表集合的「劃分」)： 举例说，设A共有3个素(不妨称它们命名为1、2和3)，现要把它们划分为2个非空子集，那么应共有以下3种划分法(请注意以下用「集合的集合」Set of Sets，或称「集合族」Family of Sets来代表集合的「划分」)：

{ {1,2},{3}}; { {1,3},{2}}; { {1},{2,3}} { {1,2},{3}}; { {1,3},{2}}; { {1},{2,3}}

如果容許空集存在，那麼集合A便有4種劃分法： 如果容许空集存在，那么集合A便有4种划分法：

{Φ,{1,2,3}}; { {1,2},{3}}; { {1,3},{2}}; { {1},{2,3}} {Φ,{1,2,3}}; { {1,2},{3}}; { {1,3},{2}}; { {1},{2,3}}

根據「集合論」的約定，一個集合內的素一般是沒有次序之分的，但「點算組合學」提出「有序劃分」 (Division)的概念。 根据「集合论」的约定，一个集合内的素一般是没有次序之分的，但「点算组合学」提出「有序划分」 (Division)的概念。 如果在劃分後所得「集合族」內的集合有次序之分，而集合內的素卻無次序之分，我們便把這種集合劃分稱為「有序劃分」。 如果在划分后所得「集合族」内的集合有次序之分，而集合内的素却无次序之分，我们便把这种集合划分称为「有序划分」。 舉例說，若仍以1、2和3作為集合A的素，並考慮對A進行「有序劃分」 ，那麼{1,2}-{3}與{3}-{1,2}便應是兩種不同的「有序劃分」，而{1,2}-{3}與{2,1}-{3}卻是同一種「有序劃分」(註1)。 举例说，若仍以1、2和3作为集合A的素，并考虑对A进行「有序划分」 ，那么{1,2}-{3}与{3}-{1,2}便应是两种不同的「有序划分」，而{1,2}-{3}与{2,1}-{3}却是同一种「有序划分」(注1)。 這樣，集合A便應有以下6種「不容許空集的集合有序劃分」： 这样，集合A便应有以下6种「不容许空集的集合有序划分」：

{1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2} {1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2}

以及以下8種「容許空集的集合有序劃分」： 以及以下8种「容许空集的集合有序划分」：

Φ-{1,2,3}; {1,2,3}-Φ; {1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2} Φ-{1,2,3}; {1,2,3}-Φ; {1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2}

現在筆者運用「廣義容斥原理」推導「不容許空集的集合有序劃分」 問題的計算公式，我們把所求答案稱為D ₁ (r, n)(這裡D的下標1代表每個子集素個數的「下限」，即每個子集須有至少1個素) 。 现在笔者运用「广义容斥原理」推导「不容许空集的集合有序划分」 问题的计算公式，我们把所求答案称为D ₁ (r, n)(这里D的下标1代表每个子集素个数的「下限」，即每个子集须有至少1个素) 。 首先我們定義論域U為把含有r個素的集合A劃分為n個有序子集A ₁ ... A _n 的各種「有序劃分」組成的集合。 首先我们定义论域U为把含有r个素的集合A划分为n个有序子集A ₁ ... A _n 的各种「有序划分」组成的集合。 S ₁ 為以A ₁ 為空集的那些「有序劃分」組成的集合。 S ₁ 为以A ₁ 为空集的那些「有序划分」组成的集合。 其餘S ₂ ... S _n 的定義均類此。 其余S ₂ ... S _n 的定义均类此。 因此我們所要求的答案就是|S ₁ ' ∪ ... ∪ S _n '|，亦即《點算的奧秘：廣義容斥原理》 中的N(n, 0)。 因此我们所要求的答案就是|S ₁ ' ∪ ... ∪ S _n '|，亦即《点算的奥秘：广义容斥原理》 中的N(n, 0)。 由於S ₁ ... S _n 顯然是「可交換集合」，我們可以應用上述網頁的公式(5)求解(以下重新編號為公式(1)，並把求和變項改為k)： 由于S ₁ ... S _n 显然是「可交换集合」，我们可以应用上述网页的公式(5)求解(以下重新编号为公式(1)，并把求和变项改为k)：

N(n, 0) = Σ _{0 ≤ k ≤ n} (−1) ^k C(n, k) n _k (1) N(n, 0) = Σ _{0 ≤ k ≤ n} (−1) ^k C(n, k) n _k (1)

但在應用上式前，我們須先求n _k 的值。 但在应用上式前，我们须先求n _k 的值。 這個值就是從S ₁ ... S _n 任意抽k個出來構成的交集的素個數，而這個交集就是以A ₁ ... A _n 中k個集合為空集的那些「有序劃分」組成的集合。 这个值就是从S ₁ ... S _n 任意抽k个出来构成的交集的素个数，而这个交集就是以A ₁ ... A _n 中k个集合为空集的那些「有序划分」组成的集合。 由於在A ₁ ... A _n 中已確定了k個為空集，我們只需考慮餘下n − k個集合的情況。 由于在A ₁ ... A _n 中已确定了k个为空集，我们只需考虑余下n − k个集合的情况。 這個問題實際等同於把r個素分配入n − k個集合的問題。 这个问题实际等同于把r个素分配入n − k个集合的问题。 由於對每一個素而言，都有n − k個選擇，因此應共有(n − k) ^r 種分配法，亦即n _k = (n − k) ^r 。 由于对每一个素而言，都有n − k个选择，因此应共有(n − k) ^r 种分配法，亦即n _k = (n − k) ^r 。 把這個值代入上面公式(1)，便得 把这个值代入上面公式(1)，便得

D ₁ (r, n) = Σ _{0 ≤ k ≤ n} (−1) ^k C(n, k) (n − k) ^r (2) D ₁ (r, n) = Σ _{0 ≤ k ≤ n} (−1) ^k C(n, k) (n − k) ^r (2)

上式就是「不容許空集的集合有序劃分」問題的計算公式。 上式就是「不容许空集的集合有序划分」问题的计算公式。 現在讓我們來驗證一下當r = 3，n = 2時，上式的輸出值。 现在让我们来验证一下当r = 3，n = 2时，上式的输出值。 代入上述「參數」，得 代入上述「参数」，得

D 1 (3, 2) D 1 (3, 2)	= Σ 0 ≤ k ≤ 2 (−1) k C(2, k) (2 − k) 3 = Σ 0 ≤ k ≤ 2 (−1) k C(2, k) (2 − k) 3
	= 1 × 8 − 2 × 1 + 1 × 0 = 1 × 8 − 2 × 1 + 1 × 0
	= 6 = 6

所得結果與前面的結果相同。 所得结果与前面的结果相同。

接著讓我們利用公式(2)推導「不容許空集的集合(無序)劃分」 問題的公式，我們把所求答案稱為P ₁ (r, n)。 接着让我们利用公式(2)推导「不容许空集的集合(无序)划分」 问题的公式，我们把所求答案称为P ₁ (r, n)。 現在讓我們看看P ₁ (r, n)與D ₁ (r, n)之間存在甚麼關係。 现在让我们看看P ₁ (r, n)与D ₁ (r, n)之间存在什么关系。 根據以前介紹過的「全排列」公式，給定一種包含n個子集的「(無序)劃分」，我們可以把這n個子集排次序，從而得到n!種「有序劃分」。 根据以前介绍过的「全排列」公式，给定一种包含n个子集的「(无序)划分」，我们可以把这n个子集排次序，从而得到n!种「有序划分」。 由於共有P ₁ (r, n)種「(無序)劃分」，故有以下關係式： 由于共有P ₁ (r, n)种「(无序)划分」，故有以下关系式：

D ₁ (r, n) = n! × P ₁ (r, n)    (3) D ₁ (r, n) = n! × P ₁ (r, n) (3)

利用上式以及公式(2)，我們便得到 利用上式以及公式(2)，我们便得到

P ₁ (r, n) = [Σ _{0 ≤ k ≤ n} (−1) ^k C(n, k) (n − k) ^r ] / n!    (4) P ₁ (r, n) = [Σ _{0 ≤ k ≤ n} (−1) ^k C(n, k) (n − k) ^r ] / n! (4)

在「點算組合學」中，上式代表的數有特殊的名稱，稱為「第二類斯特林數」 (Stirling Number of the Second Kind)。 在「点算组合学」中，上式代表的数有特殊的名称，称为「第二类斯特林数」 (Stirling Number of the Second Kind)。

現在讓我們來驗證一下當r = 3，n = 2時，上式的輸出值。 现在让我们来验证一下当r = 3，n = 2时，上式的输出值。 把上文計算所得D ₁ (3, 2)的值除以2! = 2，得P ₁ (3, 2) = 6 / 2 = 3，即把3件物件劃歸2個非空(無序)子集，應共有3種劃分法，這與前面的結果一致。 把上文计算所得D ₁ (3, 2)的值除以2! = 2，得P ₁ (3, 2) = 6 / 2 = 3，即把3件物件划归2个非空(无序)子集，应共有3种划分法，这与前面的结果一致。

以上討論了「不容許空集」的情況，現在讓我們研究「容許空集」的情況。 以上讨论了「不容许空集」的情况，现在让我们研究「容许空集」的情况。 首先考慮「容許空集的集合有序劃分」 問題，我們把所求答案稱為D ₀ (r, n)。 首先考虑「容许空集的集合有序划分」 问题，我们把所求答案称为D ₀ (r, n)。 我們可以這樣來看這個問題。 我们可以这样来看这个问题。 每個素都可歸入n個子集中的一個，即每個素都有n種選擇作為這個素的「歸宿」。 每个素都可归入n个子集中的一个，即每个素都有n种选择作为这个素的「归宿」。 由於共有r個素，故共有n ^r 種把r個素歸入n個「有序」子集的方法，即 由于共有r个素，故共有n ^r 种把r个素归入n个「有序」子集的方法，即

D ₀ (r, n) = n ^r D ₀ (r, n) = n ^r

當r = 3，n = 2時，上式的輸出值是2 ³ = 8，與前文的結果一致。 当r = 3，n = 2时，上式的输出值是2 ³ = 8，与前文的结果一致。

接著考慮「容許空集的集合(無序)劃分」 問題，我們把所求答案稱為P ₀ (r, n)。 接着考虑「容许空集的集合(无序)划分」 问题，我们把所求答案称为P ₀ (r, n)。 看到這裡，有些讀者可能認為，也許我們可以利用像公式(3)那樣的公式來推導P ₀ (r, n)。 看到这里，有些读者可能认为，也许我们可以利用像公式(3)那样的公式来推导P ₀ (r, n)。 但問題是，究竟是否 但问题是，究竟是否

D ₀ (r, n) = n! × P ₀ (r, n)? D ₀ (r, n) = n! × P ₀ (r, n)?

不幸的是，上式是不成立的，原因是當n > 2時，n個子集中可能包含多於一個空集。 不幸的是，上式是不成立的，原因是当n > 2时，n个子集中可能包含多于一个空集。 但是根據「集合論」的約定，所有空集均視為相同。 但是根据「集合论」的约定，所有空集均视为相同。 因此對應於(無序)劃分{Φ, Φ, {1,2}}，只有以下3種而非3! = 6種「有序劃分」：Φ-Φ-{1,2}; Φ-{1,2}-Φ; {1,2}-Φ-Φ。 因此对应于(无序)划分{Φ, Φ, {1,2}}，只有以下3种而非3! = 6种「有序划分」：Φ-Φ-{1,2}; Φ-{ 1,2}-Φ; {1,2}-Φ-Φ。

既然以上關係式不成立，我們只好另闢蹊徑。 既然以上关系式不成立，我们只好另辟蹊径。 我們可以這樣來看這個問題。 我们可以这样来看这个问题。 由於現在容許空集存在，那麼在n個子集中，可能有i個是非空(無序)子集(1 ≤ i ≤ n)。 由于现在容许空集存在，那么在n个子集中，可能有i个是非空(无序)子集(1 ≤ i ≤ n)。 這i個非空(無序)子集的存在，使現在的問題變成把r個素劃歸i個(無序)子集的「不容許空集的集合(無序)劃分」問題，其(無序)劃分總數就是前面求得的P ₁ (r, i)。 这i个非空(无序)子集的存在，使现在的问题变成把r个素划归i个(无序)子集的「不容许空集的集合(无序)划分」问题，其(无序)划分总数就是前面求得的P ₁ (r, i)。 由於i可取1至n之間的任何整數，根據「加法原理」，我們得 由于i可取1至n之间的任何整数，根据「加法原理」，我们得

P 0 (r, n) P 0 (r, n)	= Σ 1 ≤ i ≤ n P 1 (r, i) = Σ 1 ≤ i ≤ n P 1 (r, i)
	= Σ 1 ≤ i ≤ n Σ 0 ≤ k ≤ i (−1) k C(i, k) (i − k) r / i!    (5) = Σ 1 ≤ i ≤ n Σ 0 ≤ k ≤ i (−1) k C(i, k) (i − k) r / i! (5)

在「點算組合學」中，上式代表的數亦有特殊的名稱，稱為「貝爾數」 (Bell Number)。 在「点算组合学」中，上式代表的数亦有特殊的名称，称为「贝尔数」 (Bell Number)。

現在讓我們來驗證一下當r = 3，n = 2時，上式的輸出值。 现在让我们来验证一下当r = 3，n = 2时，上式的输出值。 由於我們在前面已計算了P ₁ (3, 2)的值，我們只需再求P ₁ (3, 1)的值便足夠。 由于我们在前面已计算了P ₁ (3, 2)的值，我们只需再求P ₁ (3, 1)的值便足够。 利用公式(4)， 利用公式(4)，

P 1 (3, 1) P 1 (3, 1)	= [Σ 0 ≤ k ≤ n (−1) k C(1, k) (1 − k) 3 ] / 1! = [Σ 0 ≤ k ≤ n (−1) k C(1, k) (1 − k) 3 ] / 1!
	= 1 × 1 − 1 × 0 = 1 × 1 − 1 × 0
	= 1 = 1

因此P ₀ (3, 2) = P ₁ (3, 1) + P ₁ (3, 2) = 1 + 3 = 4，與前面的結果一致。 因此P ₀ (3, 2) = P ₁ (3, 1) + P ₁ (3, 2) = 1 + 3 = 4，与前面的结果一致。

例題1 ：4名學生每天乘校車上學，他們被安排在3個車站候車。 例题1 ：4名学生每天乘校车上学，他们被安排在3个车站候车。 假如每個車站都必須有學生候車，問可作出多少種不同安排？ 假如每个车站都必须有学生候车，问可作出多少种不同安排？

答1 ：我們可以把這個問題解釋成「集合劃分」問題：4名學生相當於4個素，3個車站相當於3個子集，把4名學生安排在3個車站候車就相當於把4個素劃歸3個子集，每個車站都必須有學生候車就相當於每個子集都必須有素，即沒有空集存在。 答1 ：我们可以把这个问题解释成「集合划分」问题：4名学生相当于4个素，3个车站相当于3个子集，把4名学生安排在3个车站候车就相当于把4个素划归3个子集，每个车站都必须有学生候车就相当于每个子集都必须有素，即没有空集存在。 由於同一個學生在不同車站候車被視為不同的安排，這些子集是「有序子集」。 由于同一个学生在不同车站候车被视为不同的安排，这些子集是「有序子集」。 綜合以上討論，本題就是一個「不容許空集的集合有序劃分」問題，可利用公式(2)求解。 综合以上讨论，本题就是一个「不容许空集的集合有序划分」问题，可利用公式(2)求解。 把r = 4， n = 3代入公式(2)，便得 把r = 4， n = 3代入公式(2)，便得

D 1 (4, 3) D 1 (4, 3)	= Σ 0 ≤ k ≤ 3 (−1) k C(3, k) (3 − k) 4 = Σ 0 ≤ k ≤ 3 (−1) k C(3, k) (3 − k) 4
	= 1 × 81 − 3 × 16 + 3 × 1 − 1 × 0 = 1 × 81 − 3 × 16 + 3 × 1 − 1 × 0
	= 36 □ = 36 □

某些應用問題會規定各個子集的素個數，這類問題也可分為「有序劃分」和「(無序)劃分」兩種。 某些应用问题会规定各个子集的素个数，这类问题也可分为「有序划分」和「(无序)划分」两种。 現在首先考慮「規定子集素個數的集合有序劃分」 問題。 现在首先考虑「规定子集素个数的集合有序划分」 问题。 設某個集合A共有r個素，並假定把這r個素命名為1、2 ... r。 设某个集合A共有r个素，并假定把这r个素命名为1、2 ... r。 現要把A劃分為n個有序子集A ₁ ... A _n 。 现要把A划分为n个有序子集A ₁ ... A _n 。 如果規定A ₁ 有r ₁ 個素... A _n 有r _n 個素，r ₁ > 0 ... r _n > 0 (註2)；r ₁ + ... r _n = r，問有多少種劃分法？ 如果规定A ₁ 有r ₁ 个素... A _n 有r _n 个素，r ₁ > 0 ... r _n > 0 (注2)；r ₁ + ... r _n = r，问有多少种划分法？ 我們把所求答案稱為D(r ₁ , ... r _n )。 我们把所求答案称为D(r ₁ , ... r _n )。

解決上述問題的關鍵是要能看出上述問題與「有限重覆全排列」問題的對應關係，即上述問題對應於以下問題：設有n類共r個物件，並假定把這n類物件命名為O ₁ ... O _n ，其中第1類物件有r ₁ 個... 第n類物件有r _n 個。 解决上述问题的关键是要能看出上述问题与「有限重覆全排列」问题的对应关系，即上述问题对应于以下问题：设有n类共r个物件，并假定把这n类物件命名为O ₁ ... O _n ，其中第1类物件有r ₁ 个...第n类物件有r _n 个。 現要把這些物件排序，問有多少種不同排法？ 现要把这些物件排序，问有多少种不同排法？

上述兩種問題的對應關係如下：n個子集合共r個素對應於n類合共r個物件；素的名稱1、2 ... r對應於排列的次序；子集的序號對應於物件類別的序號；規定的素個數(r ₁ ... r _n )對應於各類物件的數目。 上述两种问题的对应关系如下：n个子集合共r个素对应于n类合共r个物件；素的名称1、2 ... r对应于排列的次序；子集的序号对应于物件类别的序号；规定的素个数(r ₁ ... r _n )对应于各类物件的数目。 舉例說，當n = 3，r = 4，並且規定r ₁ = 1，r ₂ = 2，r ₃ = 1時，「有序劃分」{3}-{1,4}-{2}便對應著排列O ₂ -O ₃ -O ₁ -O ₂ 。 举例说，当n = 3，r = 4，并且规定r ₁ = 1，r ₂ = 2，r ₃ = 1时，「有序划分」{3}-{1,4}-{2}便对应着排列O ₂ -O ₃ -O ₁ -O ₂ 。 由於上述對應關係是「一一對應」關係，所以D(r ₁ , ... r _n )應等於「有限重覆全排列」的排列總數。 由于上述对应关系是「一一对应」关系，所以D(r ₁ , ... r _n )应等于「有限重覆全排列」的排列总数。 這樣，根據《點算的奧秘：有限重覆的排列組合問題》 ，我們有 这样，根据《点算的奥秘：有限重覆的排列组合问题》 ，我们有

D(r 1 , ... r n ) D(r 1 , ... r n )	= M(r 1 , ... r n ) = M(r 1 , ... r n )
	= r! / [(r 1 )! × ... (r n )!]    (6) = r! / [(r 1 )! × ... (r n )!] (6)

最後考慮「規定子集素個數的集合(無序)劃分」 問題。 最后考虑「规定子集素个数的集合(无序)划分」 问题。 這類問題可表述如下：設某個集合A共有r個素，現要把A劃分為n個(無序)子集。 这类问题可表述如下：设某个集合A共有r个素，现要把A划分为n个(无序)子集。 如果規定其中k ₁ 個子集有1個素，k ₂ 個子集有2個素... k _r 個子集有r個素(註3)，k ₁ ≥ 0，k ₂ ≥ 0 ... k _r ≥ 0；k ₁ + 2k ₂ + ... rk _r = r；k ₁ + k ₂ + ... k _r = n，問有多少種劃分法？ 如果规定其中k ₁ 个子集有1个素，k ₂ 个子集有2个素... k _r 个子集有r个素(注3)，k ₁ ≥ 0，k ₂ ≥ 0 ... k _r ≥ 0；k ₁ + 2k ₂ + ... rk _r = r；k ₁ + k ₂ + ... k _r = n，问有多少种划分法？ 我們把所求答案稱為P(k ₁ , ... k _r )(註4)。 我们把所求答案称为P(k ₁ , ... k _r )(注4)。

我們可以透過建立P(k ₁ , ... k _r )與D(r ₁ , ... r _n )之間的關係來求P(k ₁ , ... k _r )。 我们可以透过建立P(k ₁ , ... k _r )与D(r ₁ , ... r _n )之间的关系来求P(k ₁ , ... k _r )。 給定一種包含k ₁ 個一子集、k ₂ 個二子集... k _r 個r子集的「(無序)劃分」，我們可以把這些子集排序，從而得到一個「有序劃分」。 给定一种包含k ₁ 个一子集、k ₂ 个二子集... k _r 个r子集的「(无序)划分」，我们可以把这些子集排序，从而得到一个「有序划分」。 由於我們想運用公式(6)，我們所得的「有序劃分」不是一般的「有序劃分」，而是「規定子集素個數的集合有序劃分」。 由于我们想运用公式(6)，我们所得的「有序划分」不是一般的「有序划分」，而是「规定子集素个数的集合有序划分」。 因此我們不妨規定在把子集排序後，首k ₁ 個子集的每一個都有1個素，接下來的k ₂ 個子集的每一個都有2個素... 最後k _r 個子集的每一個都有r個素。 因此我们不妨规定在把子集排序后，首k ₁ 个子集的每一个都有1个素，接下来的k ₂ 个子集的每一个都有2个素...最后k _r 个子集的每一个都有r个素。 現在我們要問，共有多少種排序法？ 现在我们要问，共有多少种排序法？ 由於規定了所有一子集都必須排在最前，所有二子集必須排在所有一子集之後... 所有r子集必須排在最後，各種子集只能在其「限定」範圍內選擇位置。 由于规定了所有一子集都必须排在最前，所有二子集必须排在所有一子集之后...所有r子集必须排在最后，各种子集只能在其「限定」范围内选择位置。 根據「全排列」公式，全部k ₁ 個一子集在其「限定」範圍內應共有k ₁ !種排序法，全部k ₂ 個二子集在其「限定」範圍內應共有k ₂ !種排序法... 全部k _r 個r子集在其「限定」範圍內應共有k _r !種排序法。 根据「全排列」公式，全部k ₁ 个一子集在其「限定」范围内应共有k ₁ !种排序法，全部k ₂ 个二子集在其「限定」范围内应共有k ₂ !种排序法...全部k _r 个r子集在其「限定」范围内应共有k _r !种排序法。 應用「乘法原理」，全部n個子集應共有k ₁ ! × k ₂ ! × ... k _r !種排序法。 应用「乘法原理」，全部n个子集应共有k ₁ ! × k ₂ ! × ... k _r !种排序法。 由此我們得到以下關係式： 由此我们得到以下关系式：

D(r ₁ , ... r _n ) = k ₁ ! × k ₂ ! × ... k _r ! × P(k ₁ , ... k _r )    (7) D(r ₁ , ... r _n ) = k ₁ ! × k ₂ ! × ... k _r ! × P(k ₁ , ... k _r ) (7)

接下來便要運用公式(6)，但先須搞清楚r ₁ 、r ₂ ... r _n 是甚麼？ 接下来便要运用公式(6)，但先须搞清楚r ₁ 、r ₂ ... r _n 是什么？ 由於規定了首k ₁ 個子集是一集，接下來的k ₂ 個子集是二集... 最後k _r 個子集是r集，這裡的r ₁ 、r ₂ ... r _n 就是1 ... 1, 2 ... 2, ... r ... r，其中包括k ₁ 個1、k ₂ 個2 ... k _r 個r。 由于规定了首k ₁ 个子集是一集，接下来的k ₂ 个子集是二集...最后k _r 个子集是r集，这里的r ₁ 、r ₂ ... r _n 就是1 ... 1, 2 ... 2, ... r ... r，其中包括k ₁ 个1、k ₂ 个2 ... k _r 个r。 因此，應用公式(6)， 因此，应用公式(6)，

D(1 ... 1, 2 ... 2, ... r ... r) = r! / [(1!) ^{k ₁} (2!) ^{k ₂} ... (r!) ^{k _r} ]    (8) D(1 ... 1, 2 ... 2, ... r ... r) = r! / [(1!) ^{k ₁} (2!) ^{k ₂} ... (r!) ^{k _r} ] (8)

最後，綜合運用上面(7)和(8)，我們得到 最后，综合运用上面(7)和(8)，我们得到

P(k ₁ , ... k _r ) = r! / [(k ₁ )! (1!) ^{k ₁} (k ₂ )! (2!) ^{k ₂} ... (k _r )! (r!) ^{k _r} ]     (9) P(k ₁ , ... k _r ) = r! / [(k ₁ )! (1!) ^{k ₁} (k ₂ )! (2!) ^{k ₂} ... (k _r )! (r!) ^{k _r} ] (9)

例題2 ：承接例題1，假如規定第一個車站須有2名學生候車，第二個車站無人候車(該車站臨時取消了)，第三個車站須有2名學生候車，問可作出多少種不同安排？ 例题2 ：承接例题1，假如规定第一个车站须有2名学生候车，第二个车站无人候车(该车站临时取消了)，第三个车站须有2名学生候车，问可作出多少种不同安排？

答2 ：例題1的解答已顯示該題相當於一個「集合有序劃分」問題，現在加上各個車站的規定，本題成為一個「規定子集素個數的集合有序劃分」問題，可以應用公式(6)求解。 答2 ：例题1的解答已显示该题相当于一个「集合有序划分」问题，现在加上各个车站的规定，本题成为一个「规定子集素个数的集合有序划分」问题，可以应用公式(6)求解。 由於第二個車站無人候車，我們只需考慮其餘兩個車站，即把本題視作只有兩個子集處理。 由于第二个车站无人候车，我们只需考虑其余两个车站，即把本题视作只有两个子集处理。 把r = 4，r ₁ = 2，r ₂ = 2代入公式(6)，便得 把r = 4，r ₁ = 2，r ₂ = 2代入公式(6)，便得

D(2, 2) D(2, 2)	= 4! / (2! × 2!) = 4! / (2! × 2!)
	= 6 □ = 6 □

註1：這裡用「-」來表示集合族內各集合的排序，即應把AB與BA視為兩種不同的「對象」。 注1：这里用「-」来表示集合族内各集合的排序，即应把AB与BA视为两种不同的「对象」。 但如用花括號{} ，則括號內的素無次序之分，即應把{A,B}與{B,A}視為相同的「對象」。 但如用花括号{} ，则括号内的素无次序之分，即应把{A,B}与{B,A}视为相同的「对象」。

註2：為簡化以下討論，這裡規定劃分後的子集不為空集。 注2：为简化以下讨论，这里规定划分后的子集不为空集。 以下討論的「(無序)劃分」問題也是如此。 以下讨论的「(无序)划分」问题也是如此。 假如在實際問題中有空集存在，只需撇除哪些空集不予考慮便行了。 假如在实际问题中有空集存在，只需撇除哪些空集不予考虑便行了。

註3：有些讀者可能感到奇怪，既然集合A有r個素，何以能有k _r 個子集，其中每個都有r個素？ 注3：有些读者可能感到奇怪，既然集合A有r个素，何以能有k _r 个子集，其中每个都有r个素？ 請注意這裡所表達的是最一般的情況，能涵蓋所有可能性。 请注意这里所表达的是最一般的情况，能涵盖所有可能性。 事實上，k _r 只可能取兩個值：0或1。 事实上，k _r 只可能取两个值：0或1。 當k _r = 1時，k ₁ 、k ₂ ... k _r−1 統統必須等於0。 当k _r = 1时，k ₁ 、k ₂ ... k _r−1 统统必须等于0。

註4：請注意這個「(無序)劃分」問題的表述法與前面的「有序劃分」問題的表述法是很不同的。 注4：请注意这个「(无序)划分」问题的表述法与前面的「有序划分」问题的表述法是很不同的。 在前面的「有序劃分」問題中，r ₁ ... r _n 是素的個數，而在這個「(無序)劃分」問題中， k ₁ ... k _r 卻是子集的個數。 在前面的「有序划分」问题中，r ₁ ... r _n 是素的个数，而在这个「(无序)划分」问题中， k ₁ ... k _r 却是子集的个数。 這是因為在「有序劃分」問題中，各個子集有明確的序號，我們可以規定哪一個子集含有多少素；但在「(無序)劃分」問題中，各個子集沒有明確的識別標記，所以只能規定多少個子集含有1個素，多少個子集含有2個素等等。 这是因为在「有序划分」问题中，各个子集有明确的序号，我们可以规定哪一个子集含有多少素；但在「(无序)划分」问题中，各个子集没有明确的识别标记，所以只能规定多少个子集含有1个素，多少个子集含有2个素等等。

 

今天的文章 集合划分问题（转）分享到此就结束了，感谢您的阅读。