組合數(shù)學 緒論

緒

論緒

論組合數(shù)學也稱為組合分析或組合學，按研究的對象歸于離散數(shù)學家族。早在中國古代的洛書、河圖中就有組合數(shù)學的基

本思想。洛書、河圖是以不同形狀、個數(shù)的黑白點排列的圖案，并有許多種神秘的解釋，譯為現(xiàn)代的記法如圖1的（a）與（b）所示。其中，前者稱為幻方，后者稱為幻圓，它們都具有許多

組合學性質(zhì)。以圖1（a）所示幻方為例，其每行、每列及每條對角線的元素之和都是15。數(shù)字15常稱為幻和。緒

論圖1洛書與河圖緒

論推廣到n階幻方,即把1,2,…,n2這n2個數(shù)字填入n×n的方格圖中，幻和為從而,關(guān)于幻方的問題可歸結(jié)為:對任意的正整數(shù)n，n階幻方存在嗎？對某個正整數(shù)n，如果n階幻方存在，有多少不同的形式？構(gòu)造存在的n階幻方。緒

論組合數(shù)學研究的核心問題是“把有限個離散對象按一定規(guī)則或模式進行安排”，這種安排被考究地稱為組態(tài)（Configuration）。關(guān)于幻方的幾個問題也正是組合數(shù)學要解決的問題，即組態(tài)的存在性問題、組態(tài)的計數(shù)問題和組態(tài)的構(gòu)造問題。此外，還涉及組態(tài)的優(yōu)化問題。緒

論1.組態(tài)的存在性組合數(shù)學中解決組態(tài)存在性的方法很巧妙，其構(gòu)思過程往

往出人意料，讓人拍案叫絕。其中，著名的例子就是眾所周知的哥尼斯堡七橋問題。

1736年，年輕的大數(shù)學家Euler將人們在娛樂中提出的一個數(shù)學難題抽象為點線構(gòu)成的圖及尋找走邊的一筆畫問題，并給出了精巧的解答，即七橋問題無解。由此

引出了一門新型數(shù)學學科——圖論。Euler也被后人譽為圖論之父。緒

論例1容易證明，不存在2階幻方。但對其余的正整數(shù)n，n階幻方都可以構(gòu)造出來。這就證明了n(正整數(shù)n≠2)階幻方的存在性組合數(shù)學認為，如果給出了構(gòu)造組態(tài)的有效算法，即可算作證明了組態(tài)的存在性。但還需要給出構(gòu)造算法的有效性證明。緒

論例2若用1×2格的骨牌鋪砌去掉了兩個對角處格子的8×8殘缺棋盤，問能否用31枚骨牌恰將其砌滿？解答案是否定的。證明方法很巧妙，可以先將8×8棋盤黑白間隔染色，去掉的兩個對角處格子不是同白，就是同黑。因此，8×8殘缺棋盤剩余的64-2=62個格子中黑格數(shù)與白格數(shù)相差為2。反之，若設(shè)能用31枚1×2格的骨牌，每枚覆蓋相鄰的2個方格，恰將殘缺棋盤砌滿，則黑格數(shù)與白格數(shù)應該相等。這就產(chǎn)生了矛盾。因此，存在要求的覆蓋。如果對不去掉對角處格子的64格8×8完好棋盤，則存在用32枚1×2格的骨牌恰將其砌滿的許多方法。這時要討論的就是確定有多少種不同覆蓋方法的計數(shù)問題。緒

論2.組態(tài)的枚舉、分類和計數(shù)如果所要求的組態(tài)存在，則可能有不止一種的方案。問題是究竟有多少種可能的不同方案,如何對組態(tài)的不同方案進行分類、枚舉。例3對正三角形的三個頂點u,v,w染以紅、藍兩種顏色，求不同的染色方案。解事實上，染色方案可自然地分為如下四類：三點全染紅色，只有1種方案：rrr；三點全染藍色，只有1種方案：bbb；兩點染紅，一點染藍，因藍色可分別染于u,v,w三個頂點之一，故有3種方案：brr,rbr,rrb;緒

論（4）由對稱性可知，兩點染藍，一點染紅的方案也有3種方案：rbb,brb,bbr。從而，總的方案數(shù)為23=8種。例3所述問題也可轉(zhuǎn)化為求集合X={u,v,w}到Y(jié)={r,b}的函數(shù)的數(shù)目，由離散數(shù)學知，該數(shù)目為：|YX|=|Y||X|=23=8。又若設(shè)三角形的三個頂點無區(qū)別，即將旋轉(zhuǎn)重合的方案視為同一方案，則（3）、（4）兩類中的3種方案都將歸為1種。從而共有4種不同的方案。緒

論例4

n元集上有多少個不同的自反關(guān)系，有多少個不同的對稱關(guān)系？解

設(shè)A={a1,

a2,

…,

an}，A上的自反關(guān)系R

A×A及對稱關(guān)系S

A×A分別定義為及考察關(guān)系矩陣的特征，若R為自反關(guān)系，則其關(guān)系陣MR=(mij)的主對角元全為1，其余上三角、下三角部分的n2-n=n(n-1)個元素或為0或為1。若S為對稱關(guān)系，則其關(guān)系矩陣緒

論從而，不難求得A上不同的自反關(guān)系的數(shù)目為類似地進行分析可知，A上不同的對稱關(guān)系的數(shù)目為對n=5，5元集上自反關(guān)系的數(shù)目為25×(5-1)=220=10242；5元集上對稱關(guān)系的數(shù)目為25×(5+1)/2=215=32×1024。緒

論3.組態(tài)的構(gòu)造例5例1中已指出，可對不等于2的正整數(shù)n構(gòu)造n階幻方，構(gòu)造奇數(shù)階構(gòu)造n階幻方的方法很多，如下僅給出de

la

loubère幻方的算法：№1首先將1置于第一行中間的位置上；№2若i已填入適當位置，則對i+1執(zhí)行如下特殊條款：№2.1若i在第一行，則將i+1填入i右邊一列的最底行位置；№2.2若i在最后一列，則將i+1填入i的上一行的第一列；№2.3若i在第一行最后一列或i+1該填的位置已被填入值，則將i+1填入i所在位置的下方；№3若i不在№2中特殊條款之列，則將i+1填入i緊右邊一列的上一行。緒

論例6正交拉丁方源于Euler提出的“36軍官問題”。設(shè)有6個不同軍銜和來自6個不同團隊的36名軍官，問能否將他們排成6×6方陣，使得每行每列恰有不同軍銜的軍官各一名，且每個團隊的軍官各一名？解以9名軍官為例，設(shè)i=1,2,3表示軍官的軍銜，j=1,2,3表示軍官的團隊，則每個軍官對應一個序偶(i,j)。從而可以排出：緒

論左端方陣即為所求9名軍官的一個解。又顯見若將左端方陣的第一個分量與第二個分量拆開存放，則可得右端兩個方陣。其中，前者表示9名軍官的軍銜，后者表示9名軍官的團隊。對于n×n矩陣A，若其每行每列均為{1,2,…,n}中的一個不同的數(shù)，則稱A為拉丁方?？勺C對

n∈Z+，n階拉丁方恒存在，如上面給出的右端的2個方陣。設(shè)A=(aij)n×n，B=(bij)n×n為兩個拉丁方。若n階序偶(aij,bij)≤i,j≤n)均不相同，則稱A與B互為正交的拉丁方。緒

論n=2時，不存在2階正交拉丁方，因為2階拉丁方共有2個,即但二者彼此不正交。已經(jīng)證明，也不存在6階正交拉丁方。設(shè)p為奇素數(shù)，α為正整數(shù)，如下僅以n=pα構(gòu)造正交拉丁方組。設(shè)A={0,1,2,…,n-1}，就用這n個元素構(gòu)造正交拉丁方。令緒

論則當n=pα時，A1,A2,…,An-1為正交拉丁方組。對n=5，A={0,1,2,3,4}，利用公式可算得4個兩兩正交的拉丁方組如下：緒

論緒

論4.組態(tài)的優(yōu)化優(yōu)化問題是在一定的條件下找出一個(或幾個)最優(yōu)或較優(yōu)的安排方案。有些組合問題求精確解是很困難的，所求結(jié)果有時只能給出一種接近的解。例7把一個3×3×3的立方體木塊切割成27個1×1×1的小立方塊。如果切割過程中允許重新排列已切割木塊的位置，求完成整個切割的最少次數(shù)。緒

論解這里的最優(yōu)即指具有最少切割次數(shù)的方案，采用窮舉方案并比較切割次數(shù)的方法一般不可取。本例的解法是先指出6次即可完成全部切割，即水平切2次，豎直、交叉各切2次。其次，可以證明少于6次不能完成題目要求的切割。事實上，對中心位置產(chǎn)生的小立方體而言，因其也具有6個面，且每個面都須被獨立地切割一次才能出現(xiàn)。故至少需要6次才能切割完。緒

論例8設(shè)產(chǎn)地A1,A2,…,Am生產(chǎn)某種產(chǎn)品的產(chǎn)量分別為a1,a2,…,am，銷地B1,B2,…,Bn對該產(chǎn)品的需求量分別為b1,b2,…,

bn。假設(shè)從產(chǎn)地Ai銷到銷地Bj的單位運費為cij，產(chǎn)和銷保持平衡，即求合理安排