【正文】 《組合數(shù)學(xué)》 第一章 組合數(shù)學(xué)基礎(chǔ)第1章 組合數(shù)學(xué)基礎(chǔ)1. 排列組合的基本計數(shù)問題2. 多項式系數(shù)的計算及其組合意義3. 排列組合算法 緒 論（一） 背景起源：數(shù)學(xué)游戲幻方問題：給定自然數(shù)1, 2, …, n2，將其排列成n階方陣，要求每行、每列和每條對角線上n個數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。每一行（或列、或?qū)蔷€）之和稱為幻方的和（簡稱幻和）。例：3階幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。關(guān)心的問題 （1） 存在性問題：即n階幻方是否存在？ （2） 計數(shù)問題：如果存在，對某個確定的n，這樣的幻方有多少種？ （3） 構(gòu)造問題：即枚舉問題，亦即如何構(gòu)造n階幻方。816276357951492438奇數(shù)階幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，右上有數(shù)往下填，右上出格往下填。例：將2，4，6，8，10，12，14，16，18填入下列幻方：【】（拉丁方）36名軍官問題：有1，2，3，4，5，6共六個團隊，從每個團隊中分別選出具有A、B、C、D、E、F六種軍銜的軍官各一名，共36名軍官。問能否把這些軍官排成66的方陣，使每行及每列的6名軍官均來自不同的團隊且具有不同軍銜？本問題的答案是否定的。A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3F6 A1 B2 C3 D4 E5 F6【】（計數(shù)——圖形染色）用3種顏色紅（r）、黃（y）、藍（b）涂染平面正方形的四個頂點，若某種染色方案在正方形旋轉(zhuǎn)某個角度后，與另一個方案重合，則認為這兩個方案是相同的。求本質(zhì)上不同的染色方案。舉例：ryybbbrb（a）（b）58/58 姜建國形式總數(shù)：＝81種。實際總數(shù)（見第6章）：L＝＝24【】（存在性）不同身高的26個人隨意排成一行，那么，總能從中挑出6個人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見第5章）。注意：不改變原來的相對順序。（二） 研究內(nèi)容算法分類：l 第一類：數(shù)值算法。主要解決數(shù)值計算問題，如方程求根、解方程組、求積分等，其數(shù)學(xué)基礎(chǔ)是《高等數(shù)學(xué)》與《線性代數(shù)》（解決建模問題，《數(shù)值分析》或稱《計算方法》解決離散化問題，即在計算機上的求解方法問題）。l 第二類：組合算法。解決搜索、排序、組合優(yōu)化等問題，其數(shù)學(xué)基礎(chǔ)為《組合數(shù)學(xué)》。按所研究問題的類型，研究內(nèi)容：l 組合計數(shù)理論l 組合設(shè)計l 組合矩陣論l 組合優(yōu)化本課程重點：以組合計數(shù)理論為主，部分涉及其它內(nèi)容。（三） 研究方法分類：第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項式定理、P243。lya 定理解計數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對多種問題均可使用。例如：（1） 數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（2） 迭代法【例】已知數(shù)列滿足關(guān)系，求的解析表達式。（解）直接迭代即得：＝＋1＝＝＝＝＝（3） 一一對應(yīng)技術(shù)原理：建立兩類事物之間的一一對應(yīng)關(guān)系，把一個較復(fù)雜的組合計數(shù)問題A轉(zhuǎn)化成另一個容易計數(shù)的問題B，從而利用對B的計數(shù)運算達到對A的各種不同方案的計數(shù)。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（4） 殊途同歸方法原理：從不同角度討論計數(shù)問題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進行分析推理的方法。組合數(shù)學(xué)用的較多的方法：（3）與（4）。【】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進行多少場比賽？（解）常規(guī)思路：50＋25＋12＋6＋3＋2＋1＝99場10000名選手：5000＋2500＋1250＋625＋312＋…＋1采用一一對應(yīng)方法：每場比賽產(chǎn)生一個失敗者，且每個失敗者只能失敗一次（場次→失敗者）。反之，要淘汰一個選手，必須恰好經(jīng)過一場比賽（失敗者→場次）。結(jié)論：失敗者比賽場次。應(yīng)該比賽99場。一般情況：單循環(huán)淘汰制，n個選手，比賽n－1場?！尽吭O(shè)某地的街道將城市分割成矩形方格，某人在其住處的向東7個街道、向北5個街道的大廈處工作（），按照最短路徑（即只能向東或向北走），他每次上班必須經(jīng)過某12個街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長的。 （2）對應(yīng)為（元素可重復(fù)的）排列問題：路徑（藍色）→ 排列ｘｙｙｘｘｙｙｘｘｘｘｙ排列ｙｘｘｙｙｙｙｘｘｘｘｘ → 路徑（紅色）結(jié)論：最短路徑7個x和5個y的排列（3）求解：再對應(yīng)為（元素不重復(fù)的）排列問題＝＝＝792（4）一般情形：從（0，0）點到達（m，n）點的不同的最短路徑數(shù)為 兩個基本法則1. 2. 1 加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個方案，而第一個方案有m種方法，第二個方案有n種方法可以實現(xiàn)。只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同。則完成這件事情共有m＋n種方法。l 集合描述：設(shè)有限集合A有m個元素，B有n個元素，且A與B不相交，則A與B的并共有m＋n個元素。l 概率角度描述：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件“A或B”有m＋n種產(chǎn)生方式。當然A與B各自所含的基本事件是互相不同的。（二） 應(yīng)用【】某班又男生18人，女生12人，從中選出一名代表參加會議，問共有多少種選法？（解）（1）兩個選擇方案：男生（18種選法）或女生（12種選法）。由加法法則，有18＋12＝30選法。（2）設(shè)集合：A——男生，B——女生。該班中的學(xué)生要么屬于A，要么屬于B，且AB＝，故＝18＋12＝30。（3）事件A——選男生（18種可能），事件B——選女生（12種可能）。事件“A或B”——選男生或女生，由加法法則，有18＋12＝30種可能。【】用一個小寫英文字母或一個阿拉伯數(shù)字給一批機器編號，問總共可能編出多少種號碼？（解）26＋10＝36個。其中英文字母共有26個，數(shù)字0～9共10個。1. 2. 2 乘法法則（一） 乘法法則l 常規(guī)描述：如果完成一件事情需要兩個步驟，而第一步有m種方法、第二步有n種方法去實現(xiàn)。則完成該件事情共有mn種方法。l 集合描述：設(shè)有限集合A有m個元素，B有n個元素，且A與B不相交，記為一有序?qū)?。所有有序?qū)?gòu)成的集合稱為A和B的積集（或笛卡兒乘積），記作。那么，共有個元素。l 概率角度描述：設(shè)離散型隨機變量X有m個取值，Y有n個取值，則離散型隨機向量（X，Y）有種可能的取值。（二） 應(yīng)用【】仍設(shè)某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問共有多少種選法？（解）（1）分兩步挑選，先選女生（12種選法），再選男生（18種選法）。由乘法法則，有1218＝216種選法。（2）設(shè)集合：A——男生，B——女生。由乘法法則，AB＝1812＝216。（3）變量X——男生（18種取值），變量Y——女生（12種取值）。由乘法法則，隨機向量（X，Y）有1812＝216種可能的值?！尽拷o程序模塊命名，需要用3個字符，其中首字符要求用字母A～G或U～Z，后兩個要求用數(shù)字1~9，問最多可以給多少種程序命名？（解）首字符選法：7＋6＝13種（加法法則）?？倲?shù)： 1399＝1053種（數(shù)字可重復(fù)使用）（乘法法則）?！尽繌腁地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經(jīng)B或C到達目的地D共有多少種不同的走法? （解）路線ABD：種走法（乘法法則） 路線ACD：種走法（乘法法則）總數(shù)：＋種走法（加法法則）23＋34＝18 排列與組合1. 3. 1 相異元素不允許重復(fù)的排列數(shù)和組合數(shù)（一） 計算公式從n個相異元素中不重復(fù)地取r個元素的排列數(shù)和組合數(shù)：（1）排列： 推導(dǎo)：反復(fù)利用加法法則與乘法法則（2）組合： 推導(dǎo)：利用組合與排列的異同（3）例：n＝5，r＝3，即元素為1，2，3，4，5 排列：134，143，314，341，413，431；254，425，……組合：134，245，……（4）特點：排列考慮順序，組合不然。（二） 數(shù)學(xué)模型（1）排列問題：將r個有區(qū)別的球放入n個不同的盒子，每盒不超過一個，則總的放法數(shù)為P(n，r)。（2）組合問題：將r個無區(qū)別的球放入n個不同的盒子，每盒不超過一個，則總的放法數(shù)為C(n，r)。對應(yīng)關(guān)系元素盒子位置球元素和位置編號12345A B C排列1ABC1 3 4排列2CBA4 3 1排列3ACB1 4 3排列4ACB2 5 4排列5BAC4 2 5組合1●●●1 3 4組合2●●●2 4 51. 3. 2 相異元素允許重復(fù)的排列（一） 問題從n個不同元素中允許重復(fù)地選r個元素的排列，簡稱r元重復(fù)排列，排列數(shù)記為RP(∞，r)。（二） 模型將r個不相同的球放入n個有區(qū)別的盒子，每個盒子中的球數(shù)不加限制而且同盒的球不分