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