尤卡坦半島

[拼音]：zuhe shuxue

[英文]：combinatorial mathematics

又稱組合學，是數學的一個分支。它是研究“安排”的一門學科。當把已給的有限個或可數無限個物體按一定規則來安排時，自然會產生以下四個問題：

（1）符合要求的安排是否存在？②這些安排有多少種？③怎樣作出這些安排？④當有衡量這些安排優劣的標準時，怎樣求出最優安排？這四個問題依次稱之為存在性問題、計數問題、構造問題和優化問題。

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

所示。用阿拉伯數字寫出是一個由1～9的九個陣列成的方形陣列，具有三行三列，其中每行、每列以及每條對角線上的三個數之和都等於15。這表明早在中國古代就能構造出這種組合結構。宋代楊輝造出過表明二項式係數間的基本而重要的關係，即

的楊輝三角形。朱世傑得出了組合恆等式

1≤p≤6。清代李善蘭則證明此恆等式對一切正整數 p成立。德國數學家和哲學家G.W.萊布尼茨於1666年首次在近代數學的意義下使用“組合”一詞，這是在他的著作《論組合的藝術》中出現的。

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

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

建立組合模型的例項

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

設有n位人員 A1，A2，…，An和n項工作

B

1，

B

2，…，

B

n。若欲合理分派這 n位人員以工作，而一項工作最多由一人承擔，且一人最多承擔一項工作。何謂“合理”，則視具體情況而定。

（1）設人員Ai（1≤i≤n）有能力承擔的工作是

若能使盡可能多的人員分派到他們能承擔的工作，則認為是合理的，且稱為妥善分派。

（2）設人員Ai擔任工作

B

j的效益（例如經濟效益）為αij(1≤i，j≤n)，則能使全部效益的總和達到最大的分派被認為是合理的，且稱為最佳分派。

（3）若人員 Ai(1≤i≤n)對諸工作的選擇次序為

則說人員Ai對工作

B

的評級為k。注意，評級的數值愈小的工作，被選擇的次序愈前。工作 Bj(1≤j≤n)對諸人員的選擇次序為

，則說工作

B

j對人員A

的評級為k。對諸人員的一個工作分派叫做不穩定的，如果根據這一分派有二位人員Ap、Aq分別承擔工作

B

t、

B

u，但是人員Aq對

B

t的評級小於對

B

u的評級，且工作

B

t對人員Aq的評級小於對Ap的評級。一個不穩定的分派，不能認為是合理的；不是不穩定的分派才認為是合理的，叫做穩定分派。

（4）如果一個分派使得每位人員承擔的工作的評級，都不大於任一穩定分派中該人員承擔的工作評級，那麼這樣的分派稱為對人員的最優分派。類似的有對工作的最優分派。最優分派被認為是合理的。對應於上述的①、②、③、④情形，有以下四類組合模型：

Ⅰ型分派模型作n 階矩陣A＝（αij），這裡αij＝1，當Ai 能勝任工作

B

j時；αij＝0，對於其他情形。於是一個合理分派對應於矩陣 A的、積和式不為零的一個最大階子方陣。一個n階矩陣

B

＝(b)ij)的積和式定義為

這裡和式遍及｛1，2，…，n｝的全部排列

。全部妥善分派的個數，就是A的、積和式非零且階數最大的子方陣的積和式之和。

Ⅱ型分派模型作 n 階矩陣 C ＝（сij），сij是一個實數，表徵人員Ai工作

B

j的效益。最佳分派是使

當

過{1，2，…，n}的一切排列達最大值的排列

所對應的分派：人員Ai承擔工作

。

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

其中eij是人員Ai對工作

B

j的評級，ƒij是工作

B

j對人員Ai的評級。於是，一個分派是穩定分派的充要條件是，假定按此分派人員Ai承擔工作

，那麼，絕不存在一對整數i、j(1≤i≠j≤n)合於

和

Ⅳ型分派模型稱工作

B

j對人員Ai是可行的，如果存在一個穩定分派，按此分派人員Ai承擔工作

B

j。最優分派是具有下述性質的分派：按此分派每一人員承擔的工作的評級都不大於該人員的諸可行工作的評級。

存在性定理

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

，是Tr(S)的任一分解且p、q≥r≥1，那麼存在最小正整數n(p，q，r)，只與p，q，r有關，與S及分解法Tr(S)=α∪β無關。具有以下性質:當N≥n(p，q，r)時或有S的p元子集S1合

，或有S 的 q元子集 S2合

。應用該定理及其略為普遍的變形可得：

（1）對已給正整數p1，p2，…，pt≥2，存在最小正整數 n(p1，p2，…，pt，2)使得

時，任一t色完全圖Kn都有單色完全子圖Kpj，這裡i為1與m之間某一整數；

（2）對任給的正整數m≥3，存在正整數n=n(m)，使得在平面上無三點共線的n個點中，有m個點為凸m邊形的頂點。

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

是S的一個子集系，Si叫做區組。如果｜Si｜=k，1≤i≤b;S的每一個二元子集都恰為λ個Si的子集；S的每一元 xi都恰在 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)，bk=vr；存在(v，k，λ)設計的必要條件有:若2|v，則k-λ是個平方數，如果2凲v，那麼不定方程

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

組合計數理論

最簡單的計數原則有三個。

（1）積則：若某物θ1有m種方法選出，用其中任一方法選出θ1後都有n種方法選出另一物θ2，則依次選出物θ1、θ2的方法數是m·n。

（2）和則：把一些東西分成若干類，任二類都沒有公共元，那麼全部東西的個數等於各類東西的個數之和。

（3）補則：一堆東西中滿足某性質的東西的件數等於這堆東西的總數減去不滿足該性質的東西的件數。

利用這些簡單的原則可得：

（1）n個不同物件的 r無重排列數是(n)r＝n(n－1)…(n－r＋1)；

（2）n個不同的物件的r可重排列數是 nr；

（3）n個不同物件的 r無重組合數是

；

（4）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)表數列u0，u1，u2，…的母函式，而

，這裡，諸сi(0≤i≤r-1)只依賴於u0，u1，…，ur-1。展 g(x)為部分分式

，於是可以解得

。由此立得滿足線性遞迴關係

，和初始值 u0=u1=1的斐波那契數

。

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

。當 n＝3時這樣的方冪只有

和

，故u3＝2。易知

，因而 un為

的泰勒展式中xn的係數，即

。

容斥原理

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

的A中元的個數記為

，

把一切可能的

之和記為Nk。那麼，恰滿足p中r個性質的A中元的個數

。這就是容斥原理。在許多情形，N(r)很難直接計算，而Nk則較易直接計算。用此原理可解決更列問題:前n個自然數的無重排列中每一數皆不在其本位上，這樣的排列的個數是

。著名的家政問題：n對夫妻，圍坐圓桌，男女相隔，夫妻不鄰，問坐法若干？由容斥原理得坐法數為

。

(0，1)矩陣

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

是它的一個子集系。若有元素組

合於xi∈Si，xi≠xj(1≤i≠j≤n)，則稱該元素組為子集系｛Si｝的一個相異代表組。全體相異代表組的個數記為N(S1，S2，…，Sn)。當αj∈Si時，令αij=1；在其他情形，令αij＝0；則稱矩陣A＝{αij}為集S同其子集系｛Si｝之間的關聯矩陣。對任一n×m矩陣

B

＝(b)ij)，所有無二在同行或同列的k個元之積之和，稱為

B

的k積和式，記為perk

B

。易知

。雖有公式計算perk

B

，但不理想，人們仍在尋求更為滿意的結果。

波伊亞定理

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

為從D到R內的全體對映所組成的集。設G是D上的一個置換群。若對ƒ1，ƒ2∈

存在g∈G使得ƒ1(gd)=ƒ2(d)對一切d ∈D 成立，則說ƒ1與ƒ2等價，記為ƒ1～ƒ2或ƒ1g＝ƒ2。“～”是一個等價關係，據此可把

分為若干個等價類之並。諸等價類所組成的集記為F。記 n次對稱群中全體

置換所組成的集為

。波伊亞定理斷言｜F｜=pG(｜R｜，｜R｜，…)，這裡

是G 的輪換示式。設C是一個立方體，G┡是C 的群亦即使C 變為其自身的旋轉的全體所成的群。記群 G┡中的旋轉所產生的C的六個面之間的置換所成的群為G，則有

。C 的六個面所組成的集記為D。令R＝{紅，藍}，那麼

就是把C 的各面著以紅色或藍色的所有可能的著色法的全體。對C 的諸面的兩種著色法叫做本質上不同的，如果經群G┡中的任一旋轉，不能使旋轉前後的立方體之間的一切對應面有相同的顏色。由波伊亞定理，本質上不同的著色法的個數是

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

中

yi的係數。

構造問題

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

遞迴法

通過具有小引數的某種構形來造出具有大引數的這種構形的方法叫做遞迴法。應用這一方法的最簡單的例子是構造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 矩陣即可造出2n階H 矩陣

。關於H 矩陣有一非常著名的猜想：存在任意4n階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(mod 6))，當v>7時，除6個可能的例外，都有D(v)=v-2，從而使大集問題得到解決。

數論法

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

是互不同餘(mod v)的k個整數所組成的集。若每一整數α扝0（mod v）都恰有λ種方式表為D 中二元之差：

，則稱D是一個（v，k，λ）差集。設p＝4t-1是一個大於3的素數，d1，d2，…，d2t-1為全部非零二次剩餘(mod p)，則

就是一個(4t-1，2t-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(4t＋2)=1，1782年尤拉猜想，當n=4t+2時，無一對n階正交拉丁方存在。1900年這一猜想僅就t＝1的情形得證。1959年一對10階拉丁方被構造出來。此後不久，又證明了對任意n=4t+2>6，都存在一對正交拉丁方。這就是說，尤拉猜想僅對n=6成立。n=6時的尤拉猜想就是人所共知的“36軍官問題”:有36名軍官來自6個不同的團，每個團6名且分屬於不同的6種軍階；能否把他們排成一個方形陣列，使得每行每列的6名軍官正好來自不同的團，且屬於不同的軍階。

幾何法

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

的集合。一點p是全體向量

（

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

對稱設計。

組合優化和組合演算法

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

；且這個共同值當

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