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