組合數(shù)學(xué)漫談

組合數(shù)學(xué)漫談要點(diǎn)組合數(shù)學(xué)的問(wèn)題組合數(shù)學(xué)的內(nèi)容組合數(shù)學(xué)的應(yīng)用中國(guó)的組合數(shù)學(xué)組合數(shù)學(xué)的問(wèn)題組合數(shù)學(xué)概述組合數(shù)學(xué)（CombinatorialMathematics)

也稱組合學(xué)(Combinatorics)

或離散數(shù)學(xué)(DiscreteMathematics)現(xiàn)代數(shù)學(xué)根據(jù)所研究的對(duì)象可分為兩類：連續(xù)數(shù)學(xué)：以微積分為基礎(chǔ)，傳統(tǒng)主流離散數(shù)學(xué)：伴隨計(jì)算機(jī)科學(xué)，方興未艾1666年Leibniz著《Dissertatiodeartecombinatoria》,首次使用了組合一詞。離散數(shù)學(xué)(Discretemathematics)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支。它在各學(xué)科領(lǐng)域，特別在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)也是計(jì)算機(jī)專業(yè)的許多專業(yè)課程，如程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯技術(shù)、人工智能、數(shù)據(jù)庫(kù)、算法設(shè)計(jì)與分析、理論計(jì)算機(jī)科學(xué)基礎(chǔ)等必不可少的先行課程。通過(guò)離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，為將來(lái)參與創(chuàng)新性的研究和開(kāi)發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。

隨著信息時(shí)代的到來(lái)，工業(yè)革命時(shí)代以微積分為代表的連續(xù)數(shù)學(xué)占主流的地位已經(jīng)發(fā)生了變化，離散數(shù)學(xué)的重要性逐漸被人們認(rèn)識(shí)。離散數(shù)學(xué)課程所傳授的思想和方法，廣泛地體現(xiàn)在計(jì)算機(jī)科學(xué)技術(shù)及相關(guān)專業(yè)的諸領(lǐng)域，從科學(xué)計(jì)算到信息處理，從理論計(jì)算機(jī)科學(xué)到計(jì)算機(jī)應(yīng)用技術(shù)，從計(jì)算機(jī)軟件到計(jì)算機(jī)硬件，從人工智能到認(rèn)知系統(tǒng)，無(wú)不與離散數(shù)學(xué)密切相關(guān)。

〈胃痛〉（TheStomachion）

左上圖為一份用希臘文寫(xiě)在羊皮紙上的Archimedes手稿“Stomachion”的副本,它考慮的是現(xiàn)在名為“tiling”的組合問(wèn)題Stomachion阿基米德(287?-212B.C.)在計(jì)算把14條不規(guī)則的紙帶拼成正方形有多少種不同的拼法.〈胃痛〉（TheStomachion）

阿基米德以惡作劇、謎題及走捷徑而聞名。從《阿基米德寶典》裡，已發(fā)掘出一個(gè)會(huì)讓人玩到胃痛的14巧板遊戲，如右圖。我們可以拿這14片，拼成各種圖案，譬如大象、鳥(niǎo)、魚(yú)等等，但是這並不稀奇！真正稀奇的是，把這14片「拼成同樣大小的一個(gè)正方形」。

BillCutler（2003）：答案是17152=536x32K?nigsberg七橋問(wèn)題Pregel河橫穿K?nigsberg城，河上建有七座橋，能否設(shè)計(jì)散步路線，走過(guò)所有七座橋，每座橋恰好經(jīng)過(guò)一次而回到同一地點(diǎn)？Euler環(huán)游（一筆畫(huà)）Euler于1736年給以否定：圖有這樣的路線當(dāng)且僅當(dāng)每個(gè)點(diǎn)連接偶數(shù)條邊。圖論的起源后來(lái)的數(shù)學(xué)新分支——拓?fù)鋵W(xué)的建立奠定了基礎(chǔ)

三十六軍官問(wèn)題普魯士腓特烈大帝在一次檢閱中要求：從不同的6個(gè)軍團(tuán)各選6種不同軍銜的6名軍官共36人，排成一個(gè)6行6列的方隊(duì)，使得各行各列的6名軍官恰好來(lái)自不同的軍團(tuán)而且軍銜各不相同。Euler（1779）：辦不到!

但末能給出嚴(yán)格的證明。

拉丁方陣與正交拉丁方陣每名軍官對(duì)應(yīng)一個(gè)有序?qū)Γㄜ妶F(tuán)，軍銜）以9名軍官為例：

軍團(tuán)陣列軍銜陣列

并置陣列

（拉丁方陣）（拉丁方陣）

（正交拉丁方陣）Euler猜想Euler(1779)：不存在4t+2階正交拉丁方？Tarry(1900)：不存在6階正交拉丁方！存在10階正交拉丁方！Bose,Shrikhande和Parker(1960)：

當(dāng)t>2時(shí)，存在4t+2階正交拉丁方！首次數(shù)學(xué)上了TheNewYorkTimes的頭版！四色猜想英國(guó)大學(xué)生Guthrie（1852）：一張地圖，只需要四種顏色就能保證每?jī)蓚€(gè)相鄰的地區(qū)顏色不同？四色定理Kemple（1879）：給出“證明”。Heawood（1890）：指出漏洞。五色定理。Appel-Haken(1976)：給出計(jì)算機(jī)證明（1200小時(shí)100億個(gè)判斷）。（右圖為Appel

）Kirkman女生問(wèn)題Kirkman

（1806～1895）1850年：有15個(gè)女生，她們每天要做三人行的散步，要使每個(gè)女生在一周內(nèi)的每天做三人行散步時(shí)，與其她同學(xué)在組成三人小組同行時(shí)，彼此只有一次相遇在同一小組，應(yīng)怎樣安排？組合設(shè)計(jì)的起源Kirkman女生問(wèn)題的一個(gè)解SunABCDEFGHIJKLMNOMonADHBEKCIOFLNGJMTueAEMBHNCGKDILFJOWedAFIBLOCHJDKMEGNThuAGLBDJCFMEHOIKNFriAJNBIMCELDOGFHKSatAKOBFGCDNEIJHLMKirkman三元系Kirkman三元系：把v個(gè)女學(xué)生分成v/3組，使得在每(v－1)/2天內(nèi)任意兩個(gè)女生在同一組內(nèi)只相遇一次。Ray-Chaudhuri

和Wilson（1971）：Kirkman三元系存在的充要條件是v=6k+3相識(shí)問(wèn)題任何六人中必有三人彼此相識(shí)或互不相識(shí)。以點(diǎn)表人，連紅線表相識(shí)，藍(lán)線表不相識(shí)。那么六個(gè)點(diǎn)的完全圖里或有紅三角形或有藍(lán)三角形。五個(gè)點(diǎn)的則不然。Ramsey定理Ramsey(1903-1930)：給定任意正整數(shù)p和q，總存在一個(gè)最小正整數(shù)R(p,q)，使得R(p,q)個(gè)人中或者有p個(gè)人互相認(rèn)識(shí)，或者有q個(gè)人互不相識(shí)。R(p,q)稱為Ramsey數(shù)。只要人數(shù)足夠多，則互相認(rèn)識(shí)的人會(huì)越來(lái)越多，或互不相識(shí)的人會(huì)越來(lái)越多。Ramsey數(shù)R(p,q)p,q345678936914182328364182535–4149–6156–8469–115543–4958–8780–143101–216121–3166102–165111–298127–495169–7807205–540216–1031232–17138282–1870317–35839565–6588Ramsey數(shù)的計(jì)算Ramsey數(shù)的計(jì)算是對(duì)人類智力的挑戰(zhàn)！例如R(4,5)=25(1993年計(jì)算機(jī)11年的計(jì)算量)Erd?s用如下比喻說(shuō)明其困難程度：一伙外星人入侵地球，要求一年內(nèi)求得R(5,5)，否則將滅絕人類！那么也許人類能集中所有計(jì)算機(jī)和專家來(lái)求出它以自保；但如果外星人問(wèn)的是R(6,6)，那么人類將別無(wú)選擇，只能拼死一戰(zhàn)了。最精美的組合定理Rota：如果要求在組合學(xué)中僅舉出一個(gè)精美的定理，那么大多數(shù)組合學(xué)家會(huì)提名Ramsey定理。1984年Wolf獎(jiǎng)得主Erd?s1997年Fulkerson獎(jiǎng)得主Kim1998年Fields獎(jiǎng)得主Gowers1999年Wolf獎(jiǎng)得主Lovasz2003年Steele獎(jiǎng)得主Graham2005年G?del獎(jiǎng)得主Alon2006年Fields獎(jiǎng)得主Tao

均對(duì)Ramsey理論有杰出貢獻(xiàn)Ramsey理論的哲理意義完全的無(wú)序是不可能的(Completedisorderisimpossible)。任一足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)。無(wú)序無(wú)意的行為產(chǎn)生了有規(guī)律的后果，發(fā)人深思耐人尋味。古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。但根據(jù)Ramsey定理，只要隨機(jī)分布的星星數(shù)目足夠多，就可以描繪出各種圖形的輪廓。1994年StatisticalScience的一篇論文利用統(tǒng)計(jì)方法證明：圣經(jīng)隱藏了許多訊息，而這些訊息是有意安排的，絕非文字排列偶然造成的。1997年Michael

Drosnin的《TheBibleCode》通過(guò)計(jì)算機(jī)掃讀圣經(jīng)中的304805個(gè)字母，發(fā)現(xiàn)圣經(jīng)密碼當(dāng)中傳達(dá)的訊息除了拉賓被刺殺外，還包括美國(guó)肯尼迪和林肯兩位總統(tǒng)，以及印度總理甘地遇刺的事件，日本神戶、美國(guó)舊金山的大地震、世界末日與廣島原子彈轟炸等，種種過(guò)去與未來(lái)發(fā)生的大事件。組合數(shù)學(xué)的內(nèi)容組合數(shù)學(xué)的研究?jī)?nèi)容組合數(shù)學(xué)研究的中心問(wèn)題是按照一定的規(guī)劃來(lái)安排一些與物件有關(guān)的問(wèn)題。1.存在問(wèn)題——當(dāng)符合要求的安排并非顯然存在或不存在時(shí)，首要的問(wèn)題是證明或否定它的存在.2.計(jì)算問(wèn)題或分類問(wèn)題——當(dāng)符合要求的安排顯然存在，或者已證明它存在時(shí)，求出這類安排的各抒己見(jiàn)，或者把它分類.

3.構(gòu)造問(wèn)題（組合設(shè)計(jì)）——把滿足某種條件的安排構(gòu)造出來(lái).

4.優(yōu)化問(wèn)題——給出最優(yōu)標(biāo)準(zhǔn)，找出滿足給定條件的最優(yōu)安排.組合數(shù)學(xué)的分支組合分析代數(shù)組合極值集論圖論組合設(shè)計(jì)組合優(yōu)化組合算法組合數(shù)學(xué)的應(yīng)用應(yīng)用促進(jìn)理論發(fā)展36個(gè)軍官問(wèn)題這個(gè)純粹來(lái)自智力游戲的題目孕育著艱深的數(shù)學(xué)問(wèn)題。Euler猜想直到二十世紀(jì)中葉才獲得解決，有兩個(gè)原因：一是理論上的準(zhǔn)備。這類問(wèn)題用初等方法很難解決，二十世紀(jì)代數(shù)和幾何的發(fā)展為解決問(wèn)題提供了必要工具（如Galois域上的射影幾何即有限幾何等）；二是生產(chǎn)實(shí)際的推動(dòng)。數(shù)理統(tǒng)計(jì)學(xué)家Fisher將正交拉丁方用于試驗(yàn)設(shè)計(jì)，例如，用二種原料合成某染料，每種原料有3個(gè)水平，怎樣安排試驗(yàn)?zāi)苁姑糠N原料的各種水平各碰一次？這正好是3階的正交拉丁方陣問(wèn)題。Fisher的試驗(yàn)設(shè)計(jì)是一股巨大的推動(dòng)力量，把一種數(shù)學(xué)游戲變成了節(jié)約人力物力的具有重大價(jià)值的科學(xué)方法。源出于游戲受惠于數(shù)學(xué)落腳于應(yīng)用“Kirkman女生問(wèn)題”引出組合數(shù)學(xué)的一個(gè)重要分支—組合設(shè)計(jì)。對(duì)這些數(shù)學(xué)游戲，一旦當(dāng)人們認(rèn)識(shí)到它們?cè)跀?shù)學(xué)和其他科學(xué)上的深刻含義后，便又促使人們對(duì)它進(jìn)行更深入的研究，從而豐富了數(shù)學(xué)學(xué)科的內(nèi)容和知識(shí)。該問(wèn)題就是最典型的組合設(shè)計(jì)問(wèn)題。其本質(zhì)就是如何將一個(gè)集合中的元素組合成一定的子集系以滿足一定的要求。表面上看來(lái)，Kirkman女生問(wèn)題是純粹的數(shù)學(xué)游戲，然而它的解卻在醫(yī)藥試驗(yàn)設(shè)計(jì)上有很廣泛的運(yùn)用。德國(guó)組合數(shù)學(xué)家利用組合設(shè)計(jì)的方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用。在美國(guó)也有專門(mén)的公司用組合設(shè)計(jì)的方法開(kāi)發(fā)軟件，來(lái)解決工業(yè)界中的試驗(yàn)設(shè)計(jì)問(wèn)題。中國(guó)的組合數(shù)學(xué)河圖洛書(shū)九宮圖易曰：河出圖，洛出書(shū)，圣人則之。河圖洛書(shū)是最早的幻方?！岸⒕?、四；七、五、三；六、一、八”----《大戴禮記·明堂》《黃帝內(nèi)經(jīng)·靈樞》的《九宮八風(fēng)》篇?！熬艑m者，即二四為肩，六八為足，左三右七，戴九履一，五居中央”

----(漢)徐岳撰(北周)甄鸞注楊輝《續(xù)古摘奇算法》(1275)進(jìn)一步給出了四階幻方構(gòu)造方法。此外，他還構(gòu)造出了五階、六階、七階、八階、九階和十階幻方(百子圖)。四九二三五七八一六幻方的轉(zhuǎn)播12世紀(jì)的阿拉伯文獻(xiàn)里有六階幻方的記載印度12-13世紀(jì)時(shí)的Jaina幻方（右下）15世紀(jì)幻方傳往歐洲西方最早的幻方出現(xiàn)在德國(guó)Dürer1514年的名畫(huà)”憂郁者”中。1977年美國(guó)旅行者1號(hào)和2號(hào)宇宙飛船帶去Jaina幻方。楊輝三角楊輝（南宋）著《詳解九章算法》(1261年)中曾引賈憲（北宋）的“開(kāi)方作法本源”圖。楊輝在承上啟下、數(shù)學(xué)教育方面有突出貢獻(xiàn)。Pascal三角(1654年)可上溯至1537年朱世杰恒等式（元）朱世杰是中國(guó)傳統(tǒng)數(shù)學(xué)中水平最高者之一。他在《四元玉鑒》（1303）得到：Zeilberger:Chu's1303IdentityImpliesBombieri's1990Norm-Inequality,1994數(shù)學(xué)家朱世杰著《四元玉鑒》成書(shū)，世杰字漢卿，號(hào)松庭，另著有《算學(xué)啟蒙》。在求解多元高次方程組、高階等差級(jí)數(shù)、高次招差法方面，公元1303年成書(shū)。比西方早四百年左右。李善蘭恒等式（清）李善蘭（1811-1882）是開(kāi)展現(xiàn)代數(shù)學(xué)研究的第一位中國(guó)數(shù)學(xué)家。他從研究中國(guó)傳統(tǒng)的垛積問(wèn)題入手，獲得了一些相當(dāng)于現(xiàn)代組合數(shù)學(xué)中的成果。如在《垛積比類》中提出Erd?s-Ko-Rado定理Frankl-Graham：Erd?s-柯召-Rado定理是組合數(shù)學(xué)中的一個(gè)主要結(jié)果，開(kāi)辟了極值集合論迅速發(fā)展的道路。柯召(1910-2002)：1935-1938在英國(guó)Manchester大學(xué)期間與Erd?s相識(shí)，該結(jié)果在1938年得到，于1961年發(fā)表。Erd?s（1913-1996）是數(shù)學(xué)史上著作數(shù)僅次于Euler的傳奇人物（約1500篇），他曾說(shuō)在他所有著作中，含有上述結(jié)果的論文是被同行們引用次數(shù)最多的。Gould-Hsu反演公式1973年DukeMath.J.上發(fā)表了Gould與徐利治的論文“Somenewinverseseriesrelations”，這是中美關(guān)系正?；_(kāi)始后兩國(guó)學(xué)者合作發(fā)表的第一篇論文。Gould-Hsu反演公式可用于證明和發(fā)現(xiàn)恒等式，也可以應(yīng)用于算法分析和插值方法中。徐利治（1920-），原名徐泉涌。教授。江蘇常熟人。1945年畢業(yè)于西南聯(lián)合大學(xué)數(shù)學(xué)系。次年加入中國(guó)共產(chǎn)黨。1949年、1950年先后在英國(guó)亞貝丁大學(xué)、劍橋大學(xué)學(xué)習(xí)。1951年回國(guó)。歷任清華大學(xué)副教授，吉林大學(xué)教授、教務(wù)長(zhǎng)，大連工學(xué)院教授、應(yīng)用數(shù)學(xué)研究所所長(zhǎng)。在漸進(jìn)分析、逼近論方面取得重要成果，在國(guó)際上被譽(yù)為“徐氏漸進(jìn)公式”、“徐氏逼近”，1985年獲國(guó)家教委科技進(jìn)步獎(jiǎng)二等獎(jiǎng)。著有《漸近積分和積分逼近》、《高維的數(shù)值積分》、《數(shù)學(xué)方法論選講》，合著《函數(shù)逼近的理論與方法》。

開(kāi)拓多維漸近積分研究

提出一般無(wú)界函數(shù)逼近的擴(kuò)展乘數(shù)法

創(chuàng)立了某些計(jì)算方法的新途徑

倡導(dǎo)并發(fā)展數(shù)學(xué)方法論研究

中國(guó)郵遞員問(wèn)題管梅谷（1960）：郵遞員從郵局出發(fā)送信，要求對(duì)轄區(qū)內(nèi)每條街都至少通過(guò)一次再回郵局，怎