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

1、組合數(shù)學(xué)漫談組合數(shù)學(xué)漫談要點要點組合數(shù)學(xué)的問題組合數(shù)學(xué)的問題組合數(shù)學(xué)的內(nèi)容組合數(shù)學(xué)的內(nèi)容組合數(shù)學(xué)的應(yīng)用組合數(shù)學(xué)的應(yīng)用中國的組合數(shù)學(xué)中國的組合數(shù)學(xué)組合數(shù)學(xué)的問題組合數(shù)學(xué)概述組合數(shù)學(xué)（Combinatorial Mathematics) 也稱組合學(xué)(Combinatorics) 或離散數(shù)學(xué)(Discrete Mathematics)現(xiàn)代數(shù)學(xué)根據(jù)所研究的對象可分為兩類： 連續(xù)數(shù)學(xué)：以微積分為基礎(chǔ)，傳統(tǒng)主流 離散數(shù)學(xué)：伴隨計算機科學(xué)，方興未艾1666年Leibniz著Dissertatio de arte combinatoria,首次使用了組合一詞。阿基米德寶盒 左上圖為一份用希臘文寫在羊皮紙上的A

2、rchimedes手稿“Stomachion”的副本, 它考慮的是現(xiàn)在名為“tiling”的組合問題 StomachionArchimedes(287? -212 B.C.)在計算把14條不規(guī)則的紙帶拼成正方形有多少種不同的拼法。Bill Cutler （2003）：答案是17152=536x32Knigsberg七橋問題七橋問題Pregel河橫穿Knigsberg城，河上建有七座橋 ，能否設(shè)計散步路線，走過所有七座橋，每座橋恰好經(jīng)過一次而回到同一地點？Euler環(huán)游（一筆畫）Euler于1736年給以否定： 圖有這樣的路線當(dāng)且僅當(dāng) 每個點連接偶數(shù)條邊。圖論的起源三十六軍官問題 普魯士腓特烈大

3、帝在一次檢閱中要求： 從不同的6個軍團(tuán)各選6種不同軍銜的6名軍官共36人，排成一個6行6列的方隊，使得各行各列的6名軍官恰好來自不同的軍團(tuán)而且軍銜各不相同。 Euler（1779）：辦不到! 但末能給出嚴(yán)格的證明 。 拉丁方陣與拉丁方陣與正交拉丁方陣正交拉丁方陣 每名軍官對應(yīng)一個有序?qū)Γㄜ妶F(tuán)，軍銜） 以9名軍官為例： 軍團(tuán)陣列 軍銜陣列 并置陣列 （拉丁方陣）（拉丁方陣） （拉丁方陣）（拉丁方陣） （正交拉丁方陣）正交拉丁方陣）)2 , 1 () 1 , 3()3 , 2() 1 , 2()3 , 1 ()2 , 3()3 , 3()2 , 2() 1 , 1 (213132321132213

4、321Euler猜想Euler(1779)：不存在4t+2階正交拉丁方？Tarry(1900)：不存在6階正交拉丁方！ 存在10階正交拉丁方！Bose, Shrikhande和Parker(1960)： 當(dāng)t2時，存在4t+2階正交拉丁方！ 首次數(shù)學(xué)上了The New York Times的頭版！四色猜想英國大學(xué)生Guthrie（1852）：一張地圖，只需要四種顏色就能保證每兩個相鄰的地區(qū)顏色不同？四色定理Kemple（1879）： 給出“證明”。Heawood（1890）： 指出漏洞。五色定理。Appel-Haken(1976)： 給出計算機證明（1200小時100億個判斷）。 （右圖為Ap

5、pel ）Kirkman女生問題Kirkman （18061895）1850年：有15個女生，她們每天要做三人行的散步，要使每個女生在一周內(nèi)的每天做三人行散步時，與其她同學(xué)在組成三人小組同行時，彼此只有一次相遇在同一小組，應(yīng)怎樣安排？組合設(shè)計的起源Kirkman女生問題的一個解SunABCDEFGHIJKLMNOMonADHBEKCIOFLNGJMTueAEMBHNCGKDILFJOWedAFIBLOCHJDKMEGNThuAGLBDJCFMEHOIKNFriAJNBIMCELDOGFHKSatAKOBFGCDNEIJHLMKirkman三元系Kirkman三元系：把v個女學(xué)生分成v/3組，使

6、得在每(v1)/2天內(nèi)任意兩個女生在同一組內(nèi)只相遇一次。Ray-Chaudhuri 和Wilson （1971）：Kirkman三元系存在的充要條件是v=6k+3相識問題任何六人中必有三人彼此相識或互不相識。以點表人，連紅線表相識，藍(lán)線表不相識。那么六個點的 完全圖里或有紅三角形或有藍(lán)三角形。五個點的則不然。Ramsey定理Ramsey(1903-1930)：給定任意正整數(shù)p和q，總存在一個最小正整數(shù)R(p,q)，使得R(p,q)個人中或者有 p 個人互相認(rèn)識，或者有 q 個人互不相識。R(p,q) 稱為Ramsey數(shù)。只要人數(shù)足夠多，則互相認(rèn)識的人會越來越多，或互不相識的人會越來越多。Ram

7、sey數(shù)R(p,q)p,q34567893 691418232836418 25354149615684691155 4349588780143101216121316610216511129812749516978072055402161031232171382821870317358395656588Ramsey數(shù)的計算Ramsey數(shù)的計算是對人類智力的挑戰(zhàn)！例如R(4,5)=25 (1993年計算機11年的計算量)Erds用如下比喻說明其困難程度：一伙外星人入侵地球，要求一年內(nèi)求得R(5,5)，否則將滅絕人類！那么也許人類能集中所有計算機和專家來求出它以自保；但如果外星人問的是R(6,6

8、) ，那么人類將別無選擇，只能拼死一戰(zhàn)了。最精美的組合定理Rota：如果要求在組合學(xué)中僅舉出一個精美的定理，那么大多數(shù)組合學(xué)家會提名Ramsey定理。1984年Wolf獎得主Erds1997年Fulkerson獎得主Kim1998年Fields獎得主Gowers1999年Wolf獎得主Lovasz2003年Steele獎得主Graham2005年Gdel獎得主Alon2006年Fields獎得主Tao 均對Ramsey理論有杰出貢獻(xiàn)Ramsey理論的哲理意義完全的無序是不可能的(Complete disorder is impossible)。任一足夠大的結(jié)構(gòu)中必定包含一個給定大小的規(guī)則子結(jié)構(gòu)

9、。無序無意的行為產(chǎn)生了有規(guī)律的后果，發(fā)人深思耐人尋味。古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。但根據(jù)Ramsey 定理，只要隨機分布的星星數(shù)目足夠多，就可以描繪出各種圖形的輪廓。1994年Statistical Science的一篇論文利用統(tǒng)計方法證明：圣經(jīng)隱藏了許多訊息，而這些訊息是有意安排的，絕非文字排列偶然造成的。 1997 年Michael Drosnin的The Bible Code 通過計算機掃讀圣經(jīng)中的304805個字母，發(fā)現(xiàn)圣經(jīng)密碼當(dāng)中傳達(dá)的訊息除了拉賓被刺殺外，還包括美國肯尼迪和林肯兩位總統(tǒng)，以及印度總理甘地遇刺的事件，日本神戶、美國舊金山的大地

10、震、世界末日與廣島原子彈轟炸等，種種過去與未來發(fā)生的大事件。組合數(shù)學(xué)的內(nèi)容組合數(shù)學(xué)的研究內(nèi)容組合數(shù)學(xué)研究的中心問題是按照一定的規(guī)劃來安排一些與物件有關(guān)的問題。1.存在問題當(dāng)符合要求的安排并非顯然存在或不存在時，首要的問題是證明或否定它的存在. 2.計算問題或分類問題當(dāng)符合要求的安排顯然存在，或者已證明它存在時，求出這類安排的各抒己見，或者把它分類. 3.構(gòu)造問題（組合設(shè)計）把滿足某種條件的安排構(gòu)造出來. 4.優(yōu)化問題給出最優(yōu)標(biāo)準(zhǔn)，找出滿足給定條件的最優(yōu)安排.組合數(shù)學(xué)的分支組合分析代數(shù)組合極值集論圖 論組合設(shè)計組合優(yōu)化組合算法組合數(shù)學(xué)的應(yīng)用組合數(shù)學(xué)的應(yīng)用應(yīng)用促進(jìn)理論發(fā)展36個軍官問題這個純粹來自

11、智力游戲的題目孕育著艱深的數(shù)學(xué)問題 。Euler猜想直到二十世紀(jì)中葉才獲得解決，有兩個原因：一是理論上的準(zhǔn)備。這類問題用初等方法很難解決，二十世紀(jì)代數(shù)和幾何的發(fā)展為解決問題提供了必要工具（如Galois域上的射影幾何即有限幾何等）；二是生產(chǎn)實際的推動。數(shù)理統(tǒng)計學(xué)家Fisher將正交拉丁方用于試驗設(shè)計，例如，用二種原料合成某染料，每種原料有3個水平，怎樣安排試驗?zāi)苁姑糠N原料的各種水平各碰一次？這正好是3階的正交拉丁方陣問題。 Fisher的試驗設(shè)計是一股巨大的推動力量，把一種數(shù)學(xué)游戲變成了節(jié)約人力物力的具有重大價值的科學(xué)方法。源出于游戲受惠于數(shù)學(xué)落腳于應(yīng)用源出于游戲受惠于數(shù)學(xué)落腳于應(yīng)用“Kirk

12、man女生問題”引出組合數(shù)學(xué)的一個重要分支組合設(shè)計。對這些數(shù)學(xué)游戲，一旦當(dāng)人們認(rèn)識到它們在數(shù)學(xué)和其他科學(xué)上的深刻含義后，便又促使人們對它進(jìn)行更深入的研究，從而豐富了數(shù)學(xué)學(xué)科的內(nèi)容和知識。該問題就是最典型的組合設(shè)計問題。其本質(zhì)就是如何將一個集合中的元素組合成一定的子集系以滿足一定的要求。表面上看來，Kirkman女生問題是純粹的數(shù)學(xué)游戲，然而它的解卻在醫(yī)藥試驗設(shè)計上有很廣泛的運用。德國組合數(shù)學(xué)家利用組合設(shè)計的方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費用。在美國也有專門的公司用組合設(shè)計的方法開發(fā)軟件，來解決工業(yè)界中的試驗設(shè)計問題。中國的組合數(shù)學(xué)河圖洛書九宮圖易曰：河出圖，洛出書，圣人則之。河圖洛書

13、是最早的幻方?！岸⒕?、四；七、五、三；六、一、八” -大戴禮記明堂 黃帝內(nèi)經(jīng)靈樞的九宮八風(fēng)篇。 “九宮者，即二四為肩，六八為足，左三右七，戴九履一，五居中央 ” -(漢)徐岳撰 (北周)甄鸞注 楊輝續(xù)古摘奇算法(1275)進(jìn)一步給出了四階幻方構(gòu)造方法。此外，他還構(gòu)造出了五階、六階、七階、八階、九階和十階幻方(百子圖 )。四 九 二三 五 七八 一 六幻方的轉(zhuǎn)播12世紀(jì)的阿拉伯文獻(xiàn)里有六階幻方的記載印度12-13世紀(jì)時的Jaina幻方（右下）15世紀(jì)幻方傳往歐洲西方最早的幻方出現(xiàn)在德國Drer 1514年的名畫”憂郁者”中。1977年美國旅行者1號和2號宇宙飛船帶去Jaina幻方。楊輝三角楊輝

14、（南宋）著詳解九章算法(1261年)中曾引賈憲（北宋）的“開方作法本源”圖。楊輝在承上啟下、數(shù)學(xué)教育方面有突出貢獻(xiàn)。 Pascal三角(1654年)可上溯至1537年朱世杰恒等式（元）朱世杰是中國傳統(tǒng)數(shù)學(xué)中水平最高者之一。 他在四元玉鑒（1303）得到：Zeilberger: Chus 1303 Identity Implies Bombieris 1990 Norm-Inequality,1994.1121 nmnnmnnnnnnn李善蘭恒等式（清）李善蘭（1811-1882）是開展現(xiàn)代數(shù)學(xué)研究的第一位中國數(shù)學(xué)家。他從研究中國傳統(tǒng)的垛積問題入手，獲得了一些相當(dāng)于現(xiàn)代組合數(shù)學(xué)中的成果。如在垛積

15、比類中提出 .0 llnkknlkjlknjljkjErds-Ko-Rado定理Frankl-Graham：Erds-柯召-Rado定理是組合數(shù)學(xué)中的一個主要結(jié)果，開辟了極值集合論迅速發(fā)展的道路。柯召(1910-2002)：1935-1938在英國Manchester大學(xué)期間與Erds相識，該結(jié)果在1938年得到，于1961年發(fā)表。Erds（1913-1996）是數(shù)學(xué)史上著作數(shù)僅次于Euler的傳奇人物（約1500篇），他曾說在他所有著作中，含有上述結(jié)果的論文是被同行們引用次數(shù)最多的。Gould-Hsu反演公式1973年Duke Math. J.上發(fā)表了Gould與徐利治的論文“Some ne

16、w inverse series relations”，這是中美關(guān)系正常化開始后兩國學(xué)者合作發(fā)表的第一篇論文。Gould-Hsu反演公式可用于證明和發(fā)現(xiàn)恒等式，也可以應(yīng)用于算法分析和插值方法中。中國郵遞員問題管梅谷（1960）： 郵遞員從郵局出發(fā)送信，要求對轄區(qū)內(nèi)每條街都至少通過一次再回郵局，怎樣選擇一條最短路線? 現(xiàn)實生活中很多問題可以轉(zhuǎn)化為中國郵遞員問題。有好算法！論不相交斯坦納三元系大集陸家羲(19351983)，包頭九中物理教師1961年完成論文“冠克滿系列和斯坦納系列的制作方法” ，三次投稿國內(nèi)雜志未中。前者1971年為國外學(xué)者解決發(fā)表，惜哉！1983年和1984年在J. Combi

17、n. Theory Ser. A 上發(fā)表題為 “On large sets of disjoint Steiner triple systems ”的六篇論文。以“論不相交斯坦納三元系大集”系列論文獲1987年國家自然科學(xué)一等獎。 Gilbert-Pollak猜想1990年，堵丁柱和黃光明合作證明了 Gilbert-Pollak猜想(1968)。被列為1989年-1990年度美國離散數(shù)學(xué)界和理論計算機科學(xué)界重大成果。被不列顛百科全書1992年鑒列為6項數(shù)學(xué)成果的第一項。堵丁柱獲得中國科學(xué)院自然科學(xué)一等獎、國家科技進(jìn)步二等獎和中國青年科學(xué)家獎 。3x+1問題3x+1問題：對每一個正整數(shù)，如果它是奇數(shù)，則對它乘3再加1；如果它是偶數(shù)，則對它除以2。如此循環(huán)，最終都能夠得到1。例：7221134175226