多組組合

摘要：首先，本文指出一般的排列組合是多組組合計數模式的特例；其次，在強調組合是有編號的分組模式的基礎上，給出了利用多組組合模式計算部分無編號分組方式的公式。

關鍵詞：排列組合；多組組合；順序

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2018）38-0218-02

一、引言

排列和組合是兩種最基本的計數模式，在初等數學和高等數學中均有涉及。一方面由于排列組合與現實生活聯系緊密，成為了現代公民的重要基礎知識；另一方面由于問題本身的抽象性和具體類型的繁雜性而提高了學習和掌握的門檻。本文在分析組合模式的基礎上，試圖以多組組合模式統一描述一些常見的排列組合計數模式，為繁雜的排列組合問題提供一個簡化模式。首先指出一般的排列組合是多組組合計數模式的特例，其次在強調組合是有編號的分組模式的基礎上，給出了利用多組組合模式計算部分無編號分組方式的公式。

二、組合和多組組合模式

首先需要指出的是，在按組合模式分組時，組內元素之間是不考慮順序的，是不可辨識的，但在組與組之間卻有著順序。因此，在運用組合模式計數時包含了各組之間的順序。

例1：A、B、C、D四人進行撲克牌雙扣比賽，有多少種不同的分組方式？

也許有人認為：從4人中選兩人成一對，剩下的兩人為另一對即可，于是共有C =6種分組方式。但事實上一共只有如下3對分組方式：（1）AB，CD；（2）AC，BD；（3）AD，BC。出現這個錯誤的原因是組合計數模式考慮了組的編號，將“取出AB，留下CD”和“取出CD，留下AB”看作兩種不同的分組方式，而這里不能計較組的編號，正確的計算方法應該是 × =3.有了關于組合的這個認識，我們就可以將組合模式推廣到多個組的情形。

設要把n個不同元素分成m個不同組，使各組依次有n ，n ，…，n 個元素，其中n +n +…+n =n，則其分組的種數是C ？堞 （1）

公式（1）稱為多組組合模式（multinomial combination）。

當m=2時，多項組合就是通常的組合模式。一般的多組組合也可以由通常的組合和分步計數的乘法原理得到：C =C ·C ·…·C （2）

例2：將6人分成3組，每組2人，分別從事3項不同的工作，求分配方式數。

解：先取出2人從事第一項工作，有C 種方式；再取出2人從事第二項工作，有C 種方式；剩下的2人從事第三項工作。按照乘法原理，一共有C C = · = =90種分配方式。

本例中三項工作是不同的，在它們之間存在著“順序”或者叫做“編號”，所以適用于組合模式。在例1中，兩個組之間沒有順序，故應消除組合模式中重復計算的分組數。

多組組合的一個典型應用就是由熟知的二項式定理類比得到多項式定理：（x +x +…+x ） = x x …x （3）

當m=2時，公式（3）就是二項式定理。

多項組合是一種相當廣泛的計數模式，通常的排列和組合都可以看作其特例。

三、排列是特殊的多組組合

事實上，“從n個不同元素中任取r（≤n）個元素的排列”問題，可以看作將n個不同元素分為r+1個組，使得前r個組各有一個元素，而最后一個組有n-r個元素，于是套用多項組合模式，共有 = =P 種分法，即排列方式。這里r個元素之間的順序變為組與組之間的順序。

不盡相異元素的全排列問題：有n個元素，屬于m個不同的類，同類元素之間不可辨識，各類元素分別有n ，n ，…，n 個，其中n +n +…+n =n，現在要把它們排成一列，則一共有 種不同排法。

例3：設有n個球，屬于m個不同的類，同類球之間不可辨識，各類球分別有n ，n ，…，n 個，n +n +…+n =n，現要將這n個球裝入N（n≤N）個不同的盒子，每個盒子中至多容放一球，則共有 種不同裝法。

分析：由于每盒至多容放一球，總有N-n個盒子為空。設想有m+1類球，各類球分別有n ，n ，…，n ，N-n個，n +n +…+n +（N-n）=N，問題轉換為N個不盡相異元素的全排列問題，故得結果。

四、多組組合模式的推廣

一般而言，當分組個數多于2時，就可以考慮用多組組合模式來解決相應的計數問題。我們再次強調，多組組合計數中組內元素不可辨識，但各組是可以辨識的，相當于組有編號。如果問題中不計較組間的辨識性（如例1），就要消除多組組合模式中重復計數的分組數。

例4：把7個人分成3組，完成相同工作，其中一組3個人，另兩組各2人，求分組方式數。

分析：各組完成同樣的工作，這是一個不考慮編號的分組問題.但是因為3人組有別于其他兩組，該組自帶編號，另兩組不可辨識.所以在按多組組合模式算出分組方式數之后，應除以2！，故共有 × =70種分組方式。

一般地，設有n個不同元素，要把它們分成m個無編號的組，使得其中的m 個組中的元素個數都是n 個，m 個組中的元素個數都是n 個，……，m 個組中的元素個數都是n 個，其中m +m +…+m =m，m n +m n +…+

m n =n

n ，n ，…，n 各不相同，則一共有 × （4）種不同分法。

當m =m =…=m =1時，m=k，此時公式（4）就是多組組合公式（1）.

參考文獻：

[1]李凡長，康宇，童海峰，等.組合理論及其應用[M].北京：清華大學出版社，2005.

[2]魏立力，馬江洪，顏榮芳.概率統計引論[M].北京：科學出版社，2012.