離散篇
　　離散數(shù)學是數(shù)學當中最美、最妙、最有人緣也最有難度的數(shù)學樂園和數(shù)學天堂。
　　1.1神龜龍馬，洛書河圖
　　公元前2200年，我國商周時代的《易經(jīng)》中載：大禹治伏水患之后，洛河上浮出一只巨型神龜，背馱如圖1 1所示的“洛書”獻給大禹，作為蒼天對他治水有功造福百姓的獎勵。這幅天書橫看、豎看和斜看，每一組由黑點子與白點子合成，總點數(shù)皆為15。后來人們把此洛書翻譯成如圖1-2所示的一個所謂幻方。
　　所謂幻方，是由1，2，3， ，n2 -1，n2組成的一個數(shù)字方陣，每數(shù)恰在此陣中出現(xiàn)一次，且每行之和，每列之和和兩條對角線上的數(shù)字之和皆相等。
　　1275年，我國宋代著名數(shù)學家楊輝把洛書形象地描寫為：“九子斜排，上下對易，左右相更，四維挺進，戴九履一，左三右七，二四為肩，六八為足�！逼谱g了洛書的玄機，見圖1 3。
　　“九子斜排”是按箭頭方向分別把1，2，3；4，5，6和7，8，9排成具有右下方走向的一排，三個斜排組成一個傾斜45。角的正方形陣。
　　“上下對易”，指1與9對換，1移入最下空格，9移入最上空格，使得正中的頭部戴了一個9的帽子，正中最低處穿了一雙l字鞋，即“戴九履一”。
　　“左右相更”，指最右邊的3與最左邊的7對調，3移至左側空格，7移至右側空格。
　　至此造成一個四方陣，即“四維挺進”，又2與4分別在右上角（肩）與左上角，6與8分別在右下角（足）與左下角，即“二四為肩”“六八為足”。
　　楊輝的這種口訣中的關鍵詞是“訂2子斜排”“上下對易”和“左右相更”三句。圖1 4和圖1 5分別給出按楊輝口訣構作的5階幻方和7階幻方，任意奇數(shù)（大于3）階的幻方皆可照此制作，但同階幻方不是唯一的，高階幻方的個數(shù)非常之巨大，例如五階幻方就有一千多萬個！另外，楊輝口訣不適用于偶階幻方，偶階幻方的構作十分困難。
　　“對易“和“相更”時，移動的步數(shù)恰為幻方的階數(shù)，例如圖1 501
　　離散篇④
　　(a)中頂上的1下降7步至33的上方鄰格內(nèi)，圖1-5 (a)中的9下降7步至33的下方鄰格內(nèi)，圖1-5 (a)中的7左移7步至25的左側鄰格，等等。
　　洛書對應的幻方史稱“神農(nóng)幻方”。
　　《易經(jīng)》上又云，為獎勵大禹功績，一匹龍馬從黃河躍出，把如圖1 6所示的一張“河圖”贈予大禹。
　　圖1- 6(b)是相應位置上“點子”的個數(shù)，不過4個10的意思是被虛線聯(lián)絡的10個黑點子視為分布在它們形成的正方形的四個頂處。這樣，河圖的數(shù)學含量就大了：
　　從中心5向右加上4等于最有端的9；
　　從中心5向左加上3等于最左端的8；
　　從中心5向上加上2等于最上端的7；
　　從中心5向下加上l等于最下端的6。
　　斜著看，7J-9—2J-IO J-4 =16，8+6—3+lO+1—14，9+6—4+10+1=15，8+7—2_--IO+3=15.
　　洛書和河圖出自四千多年前中華民族之手，是世界組合數(shù)學的最早成果，值得我們白豪；可惜它被后人神化，未能發(fā)展成系統(tǒng)的理論；中國幾千年的封建君主統(tǒng)治，鼓勵乃至強迫知識分子為皇帝歌功頌德，使大多數(shù)知識分子成為什么科學知識也沒有，只會呼喊×××皇帝萬歲的奴才，在這種社會背景之下，中國的許多本應領先的數(shù)學分支和組合數(shù)學一樣，并沒有發(fā)展起來。事實上，組合數(shù)學不僅是數(shù)學科學的重要分支，而且是信息產(chǎn)業(yè)和計算機科學的數(shù)學基礎之一，現(xiàn)代數(shù)學教育和數(shù)學科研當中，必須給以足夠的重視。
　　1.2 三只鴿子兩個窩
　　三只鴿子出去覓食，晚上歸巢柄息，它們共有兩個窩，顯然必有一個窩里至少住有兩只鴿子，不然，即使每巢一只鴿子，還有一只鴿子不能回巢。一般而言，對于自然數(shù)n，n+1只鴿子佳在”個巢中，至少有一巢里不少于兩只鴿子。
　　這一結論稱為鴿籠原理或抽屜原理。
　　把m本書放入門個抽屜，m>粗，至少一個抽屜里放了多于本書，其中表示的整數(shù)部分。當m=n+1時，即n+l本書放入門個抽屜，至少一個抽屜里放不少于兩本書。
　　事實上，若每個抽屜里放的書都不超過m本，則總的本數(shù)不超過m-l，與共有m本書矛盾。所以一定是有的抽屜里放了多于m-1本書。就是這么一個幾乎不證白明的道理卻能解千種難題，有萬般應用。下面是一些應用鴿籠原理的生動實例。
　�、倌耻姀椝帋烀刻煨枰粋�班保衛(wèi)，保衛(wèi)排有六個班，一周內(nèi)至少有一個班出勤兩天。
　�、�13人中必有兩人同一個月份Ll生。
　�、凵痰昀镉�10雙皮鞋放在貨架上，有11位顧客同時來購鞋，售貨員給每位顧客拿出一只鞋試穿，則顧客們手中必有兩只鞋恰是一雙。
　�、軓膡1，2， ，2000）中選1001個數(shù)，其中必有兩個，一個是另一個的整數(shù)倍。
　　事實上，取出的每個數(shù)可表成2”“，粗是非負整數(shù)，“是奇數(shù)，故對1到2000的每個數(shù)，“是1000個奇數(shù)1，3，5． ．1999中的數(shù)，可見在所選的1001個數(shù)中，有兩個數(shù)的奇數(shù)因數(shù)“是一樣的，它們是2”-“和2”z“，不妨設粗2>粗l，則2”-a÷21“一2”z-nl，即后者能被前者除盡。
　　⑤茌正六邊形內(nèi)任放七個點，則至少有兩點之間的距離小于或等于該正六邊形外接網(wǎng)的半徑。連接正六邊形的三條對角線如圖1 7，由鴿籠原理，在圖1 7的六個三角形的某個上面必然有放置的七個點中的兩個，它們的距離不大于正六邊形外接網(wǎng)的半徑。
　�、薨裮1+m2十 十m，，-州+1個球放人n個盒子，其中m，m， ，7。皆正整數(shù)，則下面”件事至少發(fā)生一件：第一個盒子中至少有m，個球，第二個盒子中至少有m球， ，第""個盒子中至少有m。值大于r-l時，mi，m：，事實上，如果m， 事實上，若這n件事都不發(fā)生，則總球數(shù)不會超過(mi -l)+（m。-l）+ +（m。-l）一7T/l+7T/2+ +m。一n，而原來有球7T/l+7T/2+ +m。-n+1，矛盾。
　　⑦”（r-l）J-I個鴿子進入粗個窩，r是自然數(shù)，則至少一個窩里的鴿子不會少于r只。
　　⑧姐個自然數(shù)mi，m。， ，m。的平均 ，m。中至少有一個不小于r，r是自然數(shù)。i=l，2， ，加，則71+7T/2+ +m。<加r，與mi，m。， ，m，，的平均值大于r-l矛盾。
　�、崛谓o定粗2+1個不等的實數(shù)組成的數(shù)列 “l(fā)，“2， ，“7 72+1
　　則此數(shù)列中至少存在由n+1個實數(shù)組成的單調遞增或單調遞減的子數(shù)列。
　　事實上，記m。是從“，開始最長的單調遞增子數(shù)列的長度，若存在某個m�！輓+1，則命題⑨已成立。否則，m，a。。> >∞。+．，若不然，例如a，．<“：：，而由a。開始的遞增子列的長度m。-m，再把a，，接到此子列前面，則知m，，≥m，+1一m+1，與m，，一m矛盾。至此找到由n+1個數(shù)組成的遞增子序列“，，，“22， 。
　　例如17個數(shù)組成的數(shù)列9，8，18，20.7.5.4.6.11. 15．10. 13. 12. 19. 17. 3， 14，由命題⑨，上述數(shù)列中有4J-1=5個數(shù)組成的單調子數(shù)列，事實上，5，6，11，15，19就是一個。20，7，5，4，3是另一個。