又稱組合學，是數學的一個分支。它是研究“安排”的一門學科。當把已給的有限個或可數無限個物體按一定規則來安排時，自然會產生以下四個問題：①符合要求的安排是否存在？②這些安排有多少種？③怎樣作出這些安排？④當有衡量這些安排優劣的標準時，怎樣求出最優安排？這四個問題依次稱之為存在性問題、計數問題、構造問題和優化問題。

　　據傳，早在西元前2200年左右，大禹治水時就發現一個“神龜”，背上有花紋，如

洛書 所示。用阿拉伯數字寫出是一個由1～9的九個數組成的方形陣列，具有三行三列，其中每行、每列以及每條對角線上的三個數之和都等於15。這表明早在中國古代就能構造出這種組合結構。宋代 楊輝造出過表明二項式系數間的基本而重要的關系，即 的楊輝三角形。 朱世傑得出瞭組合恒等式 1≤ p≤6。清代 李善蘭則證明此恒等式對一切正整數 p成立。德國數學傢和哲學傢 G.W.萊佈尼茨於1666年首次在近代數學的意義下使用“組合”一詞，這是在他的著作《論組合的藝術》中出現的。

　　自17世紀至20世紀30年代，組合數學受到娛樂、數論、概率論和化學等的推動而迅速發展，得到瞭一般的存在性定理和計數原理，諸如抽屜原理及其推廣──拉姆齊定理、母函數、遞歸關系的解法、容斥原理、波利亞計數定理等，還解決瞭一系列著名的組合學課題，諸如更列問題、傢政問題、36軍官問題等。

　　自20世紀以來，許多理論學科和應用學科，諸如物理學、化學、信息論、計算機科學、運籌學、管理科學、概率統計、編碼理論等，向組合數學提出瞭大量的具有理論和實際意義的課題，促使它產生許多新理論，如區組設計、組合優化、組合算法等，解決瞭一系列理論上的以及與經濟發展密切相關的課題。

　　建立組合模型的實例　用組合學方法去解決實際問題，首先是建立適當的組合模型。

　　設有n位人員A1，A2，…，An和n項工作B1，B2，…，Bn。若欲合理分派這n位人員以工作，而一項工作最多由一人承擔，且一人最多承擔一項工作。何謂“合理”，則視具體情況而定。①設人員Ai（1≤i≤n）有能力承擔的工作是

若能使盡可能多的人員分派到他們能承擔的工作，則認為是合理的，且稱為妥善分派。②設人員 A i擔任工作 B j的效益（例如經濟效益）為 α ij(1≤ i， j≤ n)，則能使全部效益的總和達到最大的分派被認為是合理的，且稱為最佳分派。③若人員 A i(1≤ i≤ n)對諸工作的選擇次序為 則說人員 A i對工作 B 的評級為 k。註意，評級的數值愈小的工作，被選擇的次序愈前。工作 B j(1≤ j≤ n)對諸人員的選擇次序為

，則說工作 B j對人員 A 的評級為 k。對諸人員的一個工作分派叫做不穩定的，如果根據這一分派有二位人員 A p、 A q分別承擔工作 B t、 B u，但是人員 A q對 B t的評級小於對 B u的評級，且工作 B t對人員 A q的評級小於對 A p的評級。一個不穩定的分派，不能認為是合理的；不是不穩定的分派才認為是合理的，叫做穩定分派。④如果一個分派使得每位人員承擔的工作的評級，都不大於任一穩定分派中該人員承擔的工作評級，那麼這樣的分派稱為對人員的最優分派。類似的有對工作的最優分派。最優分派被認為是合理的。對應於上述的①、②、③、④情形，有以下四類組合模型：

　　Ⅰ型分派模型　作n階矩陣A＝（αij），這裡αij＝1，當Ai能勝任工作Bj時；αij＝0，對於其他情形。於是一個合理分派對應於矩陣A的、積和式不為零的一個最大階子方陣。一個n階矩陣B＝(b)ij)的積和式定義為

這裡和式遍及｛1，2，…， n｝的全部排列 。全部妥善分派的個數，就是 A的、積和式非零且階數最大的子方陣的積和式之和。

　　Ⅱ型分派模型　 作n階矩陣C＝（сij），сij是一個實數，表征人員Ai工作Bj的效益。最佳分派是使

當 過{1，2，…， n}的一切排列達最大值的排列 所對應的分派：人員 A i承擔工作 。

　　Ⅲ型分派模型　作n階評級矩陣

其中 e ij是人員 A i對工作 B j的評級， f ij是工作 B j對人員 A i的評級。於是，一個分派是穩定分派的充要條件是，假定按此分派人員 A i承擔工作 ，那麼，絕不存在一對整數 i、 j(1≤ i≠ j≤ n)合於 和

　　Ⅳ型分派模型　稱工作Bj對人員Ai是可行的，如果存在一個穩定分派，按此分派人員Ai承擔工作Bj。最優分派是具有下述性質的分派：按此分派每一人員承擔的工作的評級都不大於該人員的諸可行工作的評級。

　　存在性定理　有關存在性的一個重要結果是抽屜原理及其推廣──拉姆齊定理：設S是一個N元集，Tr(S)是S的全部r元子集所組成的集，而

，是 T r( S)的任一分解且 p、 q≥ r≥1，那麼存在最小正整數 n( p， q， r)，隻與 p， q， r有關，與 S及分解法 T r( S)=α∪ β無關。具有以下性質：當 N≥ n( p， q， r)時或有 S的 p元子集 S 1合 ，或有 S的 q元子集 S 2合 。應用該定理及其略為普遍的變形可得：①對已給正整數 p 1， p 2，…， p t≥2，存在最小正整數 n( p 1， p 2，…， p t，2)使得 時，任一 t色完全圖 K n都有單色完全子圖 K pj，這裡 i為1與 m之間某一整數；②對任給的正整數 m≥3，存在正整數 n= n( m)，使得在平面上無三點共線的 n個點中，有 m個點為凸 m邊形的頂點。

　　一些不存在定理與區組設計有關。區組設計的理論源於農業試驗和其他科學試驗。設，

是 S的一個子集系， S i叫做區組。如果｜ S i｜= k，1≤ i≤ b; S的每一個二元子集都恰為λ個 S i的子集； S的每一元 x i都恰在 r個區組裡，則稱 是一個( b， v， r， k，λ)平衡不完全區組設計，簡稱為( b， v， r， k，λ)設計。合於條件 v＝ b)， r＝ k的( v， b， r， k，λ)設計，又叫做( v， k，λ)對稱設計，簡稱為（ v， k，λ）設計。易知，存在( b， v， r， k，λ)設計的必要條件有 r( k-1)=λ( v-1)， b k= v r；存在( v， k，λ)設計的必要條件有：若2| v，則 k-λ是個平方數，如果2刅 v，那麼不定方程

有不完全為零的整數解。如果這些條件不滿足，那麼具有相應參數的設計不存在。

　　組合計數理論　最簡單的計數原則有三個。①積則：若某物θ1有m種方法選出，用其中任一方法選出θ1後都有n種方法選出另一物θ2，則依次選出物θ1、θ2的方法數是m·n。②和則：把一些東西分成若幹類，任二類都沒有公共元，那麼全部東西的個數等於各類東西的個數之和。③補則：一堆東西中滿足某性質的東西的件數等於這堆東西的總數減去不滿足該性質的東西的件數。

　　利用這些簡單的原則可得：①n個不同物件的r無重排列數是(n)r＝n(n－1)…(n－r＋1)；②n個不同的物件的r可重排列數是nr；③n個不同物件的r無重組合數是

；④ n個不同物件的 r可重組合數是 。

　　母函數　由數列u0，u1，u2，…產生的形式冪級數u0＋u1x＋u2x2+…叫做該數列的母函數。若定義

1， 則數列 的母函數是(1+ x) n，代 x=1，得 ；代 x=-1，得

。由此兩式可得 。還可推得一系列恒等式，如

；

，

等等。母函數是解決許多組合問題諸如分配、分拆、限位排列等的有力工具。

　　遞歸關系　若一個數列u0，u1，u2，…自某項後的任一項均能由它前面的諸項按某一關系式來確定，則該關系式叫做遞歸關系。最簡單的是常系數線性遞歸關系：

這裡諸 α i是常數。不失一般性，可設 α r≠0，且稱這種線性遞歸關系是 r階的，稱 為該線性遞歸關系的特征多項式。在復數域上分解

。以 g( x)表數列 u 0， u 1， u 2，…的母函數，而 = ，這裡，諸с i(0≤ i≤ r-1)隻依賴於 u 0， u 1，…， u r-1。展 g( x)為部分分式

，於是可以解得

。由此立得滿足線性遞歸關系 ，和初始值 u 0= u 1=1的斐波那契數

。

　　下面是非線性關系例子。設已給n個字母α1，α2，…，αn，依此次序把每一αi（n≥i≥2）放在αj-1的右上角，並且在它們之間加括號以形成完全確定的方冪。記這樣得到的全部方冪的個數為

。當 n＝3時這樣的方冪隻有 和 ，故 u 3＝2。易知

，因而 u n為 的泰勒展式中 x n的系數，即 。

　　容斥原理　已給元素的集A和性質的集p。把滿足p中k個性質

的 A中元的個數記為

，

把一切可能的 之和記為 N k。那麼，恰滿足 p中 r個性質的 A中元的個數 。這就是容斥原理。在許多情形， N( r)很難直接計算，而 N k則較易直接計算。用此原理可解決更列問題：前 n個自然數的無重排列中每一數皆不在其本位上，這樣的排列的個數是 。著名的傢政問題： n對夫妻，圍坐圓桌，男女相隔，夫妻不鄰，問坐法若幹？由容斥原理得坐法數為

。

　　(0，1)矩陣　這類矩陣是研究很多組合問題的重要工具。設S是一個m元集，

是它的一個子集系。若有元素組 合於 x i∈ S i， x i≠ x j(1≤ i≠ j≤ n)，則稱該元素組為子集系｛ S i｝的一個相異代表組。全體相異代表組的個數記為 N( S 1， S 2，…， S n)。當 α j∈ S i時，令 α ij=1；在其他情形，令 α ij＝0；則稱矩陣 A＝{ α ij}為集 S同其子集系｛ S i｝之間的關聯矩陣。對任一 n× m矩陣 B＝( b) ij)，所有無二在同行或同列的 k個元之積之和，稱為 B的 k積和式，記為 per k B。易知 。雖有公式計算 per k B，但不理想，人們仍在尋求更為滿意的結果。

　　波伊亞定理　這一定理提供一個公式來計算某些元素在置換群下的等價類的個數。設D和R是兩個有限集，記

為從 D到 R內的全體映射所組成的集。設 G是 D上的一個置換群。若對 f 1， f 2∈ 存在 g∈ G使得 f 1( g d)= f 2( d)對一切 d∈ D成立，則說 f 1與 f 2等價，記為 f 1～ f 2或 f 1 g＝ f 2。“～”是一個等價關系，據此可把 分為若幹個等價類之並。諸等價類所組成的集記為F。記 n次對稱群中全體 置換所組成的集為 。波伊亞定理斷言｜F｜= p G(｜ R｜，｜ R｜，…)，這裡　 是 G的輪換示式。設 C是一個立方體， G′是 C的群亦即使 C變為其自身的旋轉的全體所成的群。記群 G′中的旋轉所產生的 C的六個面之間的置換所成的群為 G，則有 。 C的六個面所組成的集記為 D。令 R＝{紅，藍}，那麼 就是把 C的各面著以紅色或藍色的所有可能的著色法的全體。對 C的諸面的兩種著色法叫做本質上不同的，如果經群 G′中的任一旋轉，不能使旋轉前後的立方體之間的一切對應面有相同的顏色。由波伊亞定理，本質上不同的著色法的個數是

。具有 i個紅面，6- i個藍面的等價類的個數 n i是

中 y i的系數。

　　構造問題　一些重要的存在性問題往往通過構造而獲得解決。此外，在解決實際問題中，往往需要造出特定的組合構形。解決構造問題的主要方法如下：

　　遞歸法　通過具有小參數的某種構形來造出具有大參數的這種構形的方法叫做遞歸法。應用這一方法的最簡單的例子是構造2n階的H矩陣。所謂n階H矩陣，是指以1，－1為元的n階矩陣H，滿足HHT＝nIn，這裡HT表H的轉置，In表n階單位陣。易證n1階H矩陣H1和n2階H矩陣H2的克羅內克乘積H1×H2是一個n1n2階H矩陣。由此和

是 H矩陣即可造出 2 n階 H矩陣 。關於 H矩陣有一非常著名的猜想：存在任意 4 n階 H矩陣，至今尚未獲證。遞歸法在( b， v， r， k，λ)設計的研究中作用很大。( b， v， r，3，1)設計(又稱 v階施泰納三連系)理論中的大集問題就是要確定存在大集的 v值。若把 S上兩兩無公共區組的 v階施泰納三連系的個數的最大者記為 D( v)，則當 v＞1時， D( v)≤ v-2。若 D( v)= v-2，則把 S上任意 v-2個兩兩無公共區組的 v階施泰納三連系所組成的簇叫做 S上施泰納三連系的大集。陸傢羲證明瞭，對於使 v階施泰納三連系存在的 v(即 v＞1， v≡1或3(mod6))，當 v＞7時，除6個可能的例外，都有 D( v)= v-2，從而使大集問題得到解決。

　　數論法　構造某些類型的差集是說明數論法的最好例子之一。設

是互不同餘( mod v)的 k個整數所組成的集。若每一整數 α扝0（ mod v）都恰有λ種方式表為 D中二元之差： ，則稱 D是一個（ v， k，λ）差集。設 p＝ 4 t-1是一個大於3的素數， d 1， d 2，…， d 2t-1為全部非零二次剩餘( mod p)，則

就是一個( 4 t-1， 2 t-1， t-1)差集。

　　代數法　可以應用有限域的知識來構造正交拉丁方。n元集A＝{α1，α2，…，αn}上的一個拉丁方是一個n階方陣，其中每行每列都是集A的無重排列。兩個n階拉丁方（αij）和（bij）叫做正交的，如果n陣矩陣((αij，bij))中無二元相同。對任給的n，至多存在n－1個兩兩正交的n階拉丁方。設p是素數，m是正整數，n＝pm，記有限域GF(pm)的n個元為α0=0，α1=1，α2，…，αn-1，再記

。於是可以構造出 n-1個兩兩正交的拉丁方 。大於1的整數 n有標準分解式 ，記

。於是可以構造出兩兩正交的 v（ n）個 n階拉丁方。很長時期以來，直到二十多年前， v( n)一直被設想為兩兩正交的 n階拉丁方的個數的最大可能值。由於 v( 4 t＋2)=1，1782年歐拉猜想，當 n= 4 t+2時，無一對 n階正交拉丁方存在。1900年這一猜想僅就 t＝1的情形得證。1959年一對10階拉丁方被構造出來。此後不久，又證明瞭對任意 n= 4 t+2>6，都存在一對正交拉丁方。這就是說，歐拉猜想僅對 n=6成立。 n=6時的歐拉猜想就是人所共知的“36軍官問題”：有36名軍官來自6個不同的團，每個團6名且分屬於不同的6種軍階；能否把他們排成一個方形陣列，使得每行每列的6名軍官正好來自不同的團，且屬於不同的軍階。

　　幾何法　域F上的n維射影幾何pG（n，F）是全體向量

的集合。一點 p是全體向量 （ 是一個固定的向量， b≠0）的集合，其維數為零。如果 y 0， y 1，…， y k是 k+1個無關的向量，則稱全體非零向量 b) 0 y 0+ b 1 y 1+…+ b k y k( b j∈ F)是一個 k維子空間。 n－1維子空間又叫做超平面。構造區組設計的下述方法是1938年得到的。以 q＝ p m（ p是素數）個元的有限域 F q上的 n維射影幾何 p G( n， F q)的所有超平面作為區組，全體點作為元素組成一個

對稱設計。

　　組合優化和組合算法　Ⅰ型分派可化為積和式問題。對Ⅱ型分派有下述定理：設C＝(Cij)是一個n階實矩陣，則　

；且這個共同值當 時達到。由此可得最佳分派。對Ⅲ和Ⅳ型分派，下面的算法同時提供一個穩定分派和對人員的最優分派。第一步，每一人員選擇他最喜愛的工作；第二步，至少被一位人員選中的工作從選擇它的全體人員中挑出它最喜愛的人員，讓他等待而拒絕其他；第三步，每一位被拒絕的人員在未拒絕他的工作中選擇它最喜愛的工作；第四步，每一個被選中的工作從第三步選擇它的人員和前一步等待它的人員的全體中挑選它最喜愛的人員，讓他等待而拒絕其他。不斷重復第三步和第四步直至沒有被拒絕的人員存在為止。此時每一工作恰好有一人員等待。於是分配這一工作與該人員。例如當評級矩陣為

時，經上述各步依次得出（“√”表示選中，“×”表示拒絕）：最後一步表明，分派人員1承擔工作2，人員2承擔工作3，人員3承擔工作1，人員4承擔工作4，這一分派既是穩定的，又是對人員最優的。

　　

參考書目

　柯召、魏萬迪同著：《組合論》，上冊，科學出版社，北京，1981。

　魏萬迪著：《組合論-組合設計》，下冊，科學出版社，北京，1987。

　M.Jr.Hall，Combinatorial Theory，Blaisdell Pub.Co.，Waltham，Mass.，1967.

C.L.Liu，Introduction to Combinatorial Mathematics，McGraw-Hill，New York，1968.

H.J.賴瑟著，李喬譯：《組合數學》，科學出版社，北京，1983。(H.J.Ryser，Combinatoricl MatheMatias，John Wiley &Sons，New York，1963.)