《組合數(shù)學(xué)》教案1章(排列組合基礎(chǔ)).doc

第1章 組合數(shù)學(xué)基礎(chǔ)1. 排列組合的基本計數(shù)問題2. 多項式系數(shù)的計算及其組合意義3. 排列組合算法1.1 緒 論（一） 背景起源：數(shù)學(xué)游戲幻方問題：給定自然數(shù)1, 2, , n2，將其排列成n階方陣，要求每行、每列和每條對角線上n個數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。每一行（或列、或?qū)蔷€）之和稱為幻方的和（簡稱幻和）。例：3階幻方，幻和(1239)/315。關(guān)心的問題（1） 存在性問題：即n階幻方是否存在？（2） 計數(shù)問題：如果存在，對某個確定的n，這樣的幻方有多少種？（3） 構(gòu)造問題：即枚舉問題，亦即如何構(gòu)造n階幻方。816276357951492438圖1.1.1 3階幻方奇數(shù)階幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，右上有數(shù)往下填，右上出格往下填。例：將2，4，6，8，10，12，14，16，18填入下列幻方：【例1.1.1】（拉丁方）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【例1.1.2】（計數(shù)圖形染色）用3種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個頂點，若某種染色方案在正方形旋轉(zhuǎn)某個角度后，與另一個方案重合，則認(rèn)為這兩個方案是相同的。求本質(zhì)上不同的染色方案。舉例：ryybbbrb（a）（b）形式總數(shù)：81種。實際總數(shù)（見第6章）：L24【例1.1.3】（存在性）不同身高的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ī)方法（利用容斥原理、二項式定理、Plya 定理解計數(shù)問題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。第二類：通常與問題所涉及的組合學(xué)概念無關(guān)，而對多種問題均可使用。例如：（1） 數(shù)學(xué)歸納法：前提是已知問題的結(jié)果。（2） 迭代法【例】如已知數(shù)列滿足關(guān)系，求的解析表達(dá)式。（解）直接迭代即得：1（3） 一一對應(yīng)技術(shù)原理：建立兩類事物之間的一一對應(yīng)關(guān)系，把一個較復(fù)雜的組合計數(shù)問題A轉(zhuǎn)化成另一個容易計數(shù)的問題B，從而利用對B的計數(shù)運算達(dá)到對A的各種不同方案的計數(shù)。思路：將未解決問題的模式轉(zhuǎn)化為一種已經(jīng)解決的問題模式。（4） 殊途同歸方法原理：從不同角度討論計數(shù)問題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進(jìn)行分析推理的方法。組合數(shù)學(xué)用的較多的是方法（3）與（4）?！纠?.1.4】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進(jìn)行多少場比賽？（解）常規(guī)思路：502512632199場10000名選手：5000250012506253121采用一一對應(yīng)方法：每場比賽產(chǎn)生一個失敗者，且每個失敗者只能失敗一次。反之，要淘汰一個選手，必須恰好經(jīng)過一場比賽。結(jié)論：失敗者與比賽場次之間一一對應(yīng)，故應(yīng)該比賽99場。一般情況：單循環(huán)淘汰制的比賽，若有n個選手參考比賽，則須經(jīng)過n1場比賽，方可產(chǎn)生冠軍?！纠?.1.5】設(shè)某地的街道將城市分割成矩形方格，某人在其住處A(0，0)的向東7個街道、向北5個街道的大廈B(7，5)處工作（見圖1.1.3），按照最短路徑（即只能向東或向北走），他每次上班必須經(jīng)過某12個街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長的。 B(7, 5) A(0, 0)圖1.1.2 最短路徑（2）對應(yīng)為（元素可重復(fù)的）排列問題：路徑（藍(lán)色）排列排列路徑（紅色）結(jié)論：最短路徑與7個x5個y的排列（3）求解：再對應(yīng)為（元素不重復(fù)的）排列問題N792（4）一般情形：從（0，0）點到達(dá)（m，n）點的不同的最短路徑數(shù)為 N1.2 兩個基本法則1.2.1 加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個方案，而第一個方案有m種方法，第二個方案有n種方法可以實現(xiàn)。只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同。則完成這件事情共有mn種方法。l 集合描述：設(shè)有限集合A有m個元素，B有n個元素，且A與B不相交，則A與B的并共有mn個元素。l 概率角度描述：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件“A或B”有mn種產(chǎn)生方式。當(dāng)然A與B各自所含的基本事件是互相不同的。（二） 應(yīng)用【例1.2.1】某班又男生18人，女生12人，從中選出一名代表參加會議，問共有多少種選法？（解）（1）兩個選擇方案：選男生（18種選法）或女生（12種選法）。由加法法則，全班共有181230選法。（2）設(shè)集合：A男生，B女生。該班中的學(xué)生要么屬于A，要么屬于B，且AB，故181230。（3）事件A選男生（18種可能），事件B選女生（12種可能）。事件“A或B” 選男生或女生，由加法法則，有181230種可能?！纠?.2.2】用一個小寫英文字母或一個阿拉伯?dāng)?shù)字給一批機器編號，問總共可能編出多少種號碼？（解）261036個。其中英文字母共有26個，數(shù)字09共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)用【例1.2.3】仍設(shè)某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問共有多少種選法？（解）（1）分兩步挑選，先選女生（12種選法），再選男生（18種選法）。由乘法法則，全班共有1218216種選法。（2）設(shè)集合：A男生，B女生。由乘法法則，AB1812216。（3）變量X男生（18種取值），變量Y女生（12種取值）。由乘法法則，隨機向量（X，Y），有1812216種可能的值?！纠?.2.4】給程序模塊命名，需要用3個字符，其中首字符要求用字母AG或UZ，后兩個要求用數(shù)字19，問最多可以給多少種程序命名？（解）先由加法法則，首字符有7613種選法。其次，再由乘法法則，最多可以產(chǎn)生13991053個不同的名稱（數(shù)字可重復(fù)使用）?！纠?.2.5】從A地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經(jīng)B或C到達(dá)目的地D共有多少種不同的走法? （解）首先，由乘法法則，從A地經(jīng)B到達(dá)D地共有種走法, 由A經(jīng)C到達(dá)D共有種走法,再由加法法則知, 從A地經(jīng)B或C到達(dá)D地共有種不同的走法。例2334181.3 排列與組合1.3.1 相異元素不允許重復(fù)的排列數(shù)和組合數(shù)（一） 計算公式從n個相異元素中不重復(fù)地取r個元素的排列數(shù)和組合數(shù)：排列： 組合： 例：n5，r3，即元素為1，2，3，4，5 排列：134，143，314，341，413，431；254，425，組合：134，245，特點：排列考慮順序，組合不然。（二） 數(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組合11 3 4組合22 4 51.3.2 相異元素允許重復(fù)的排列（一） 問題從n個不同元素中允許重復(fù)地選r個元素的排列，簡稱r元重復(fù)排列，排列數(shù)記為RP(，r)。（二） 模型將r個不相同的球放入n個有區(qū)別的盒子，每個盒子中的球數(shù)不加限制而且同盒的球不分次序。對應(yīng)關(guān)系元素盒子位置球元素和位置編號12345A B C排列1ABC1 1 4排列2C BA4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5（三） 計算公式RP(，r) 。（四） 集合描述方式設(shè)無窮集合，從S中取r個元素的排列數(shù)即為RP(，r)。不重復(fù)排列：S。1.3.3 不盡相異元素的全排列（一） 問題有限重復(fù)排列（或部分排列）：設(shè)（），從S中任取r個元素，求其排列數(shù)RP(n，r)。（二） 模型將r個有區(qū)別的球放入t個不同的盒子，每個盒子的容量有限的，其中第i個盒子最多只能放入個球，求分配方案數(shù)。例： S21，42，13，34，251，1，2，2，2，2，3，4，4，4，5，5對應(yīng)關(guān)系元素盒子位置球元素和位置編號12345A B C排列1ABC1 1 4排列2B C A4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5說明：（1）極端情形：相異元素不重復(fù)的排列強調(diào)的是不重復(fù)，即盒子的容量為1；（2）極端情形：相異元素允許重復(fù)的排列強調(diào)的是無限重復(fù)，即盒子的容量無限；（3）一般情形：不盡相異元素的排列強調(diào)的是有限重復(fù)，即盒子的容量有限，介于兩者之間。（三） 特例（1） 1：RP(n, 1)t（2） n（全排列）先視為n個不同元素的全排列，共有n!種。但每個排列實際重復(fù)統(tǒng)計了次。例 ， ，（3） t2，（4） 1，即不重復(fù)的排列（5） ，即重復(fù)排列1.3.4 相異元素不允許重復(fù)的圓排列（一） 圓排列【例1.3.1】把n個有標(biāo)號的珠子排成一個圓圈，共有多少種不同的排法？（解）稱為圓排列（相對于線排列）。條件：元素同時按同一方向旋轉(zhuǎn)，絕對位置變化，相對位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。解法：將線排列首尾相接圍成一圓，當(dāng)圓轉(zhuǎn)動一個角度時，對應(yīng)另一個線排列，當(dāng)每個元素又轉(zhuǎn)回到原始位置時，相當(dāng)于n個不同的線排列，故圓排列數(shù)為CP(n，n)(n1)!32541 25413 54132 41325 13254【例1.3.2】從n個相異元素中不重復(fù)地取r個圍成圓排列，求不同的排列總數(shù)CP(n，r)。（解） CP(n，r) （二） 項鏈排列【例1.3.3】將5個標(biāo)有不同序號的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱為項鏈排列。條件：可以翻轉(zhuǎn)的圓排列。即同一項鏈不用剪斷重穿，翻過來仍是原項鏈。解法：兩個圓排列對應(yīng)一個項鏈排列，故有24/212種。（a） （b）圖1.3.1 項鏈排列一般情形，從n個相異珠子中取r個的項鏈排列數(shù)為： 允許重復(fù)的圓排列：情況復(fù)雜，參見反演公式（第四章）。1.3.5 相異元素允許重復(fù)的組合（一） 問題設(shè)，從S中允許重復(fù)地取r個元素構(gòu)成組合，稱為r可重組合，其組合數(shù)記為RC(，r)。（二） 抽象將S的n個不同元素分別用數(shù)字1，2，n來表示。例：n5，r4 1111，1122，1345，5555（三） 計算公式所取出的r個元素從小到大設(shè)為a1，a2， ar，則ai滿足：1a1a2arn令 biai(i1)， i1，2，r則 1b1b 2brn(r1)反之 aibi(i1)結(jié)論：與從nr1個相異元素中不重復(fù)地取r個元素的組合方案一一對應(yīng)。例：n5，r4分類重復(fù)組合不重復(fù)組合元素1，2，3，4，51，2，3，5，6，7，811111234112212452245236855555678（四） 模型將r個無區(qū)別的球放入n個不同的盒子，每個盒子的球數(shù)不受限制。（五） 應(yīng)用【例1.3.4】不同的5個字母通過通信線路被傳送，每兩個相鄰字母之間至少插入3個空格，但要求空格的總數(shù)必須等于15，問共有多少種不同的傳送方式？（解）將問題分為三步求解：（1）先排列5個字母，排列數(shù)為 P(5，5)5!。（2）兩個字母間各插入3個空格，將12個空格均勻地放入4個間隔內(nèi)，有1種方案。（3）將余下的3個空格插入4個間隔：分析：將3個相同的球放入4個不同的盒子，盒子的容量不限。歸納問題：從4個相異元素中可重復(fù)地取3個元素的組合數(shù)。 b d e a方案1 方案2 （4）總方案數(shù) L5！12024001.3.6 不盡相異元素任取r個的組合問題（一） 問題設(shè)集合（），從S中任取r個，求其組合數(shù)RC(n，r)。（二） 組合數(shù)構(gòu)造多項式RC(n，r)（三） 應(yīng)用【例1.3.5】整數(shù)360有幾個正約數(shù)？（解）（1）標(biāo)準(zhǔn)素因數(shù)分解：36023325（2）正約數(shù)及其條件1203050，223050，320350，520305，22223050，6235032，902325，18022325，36023325結(jié)論：正整數(shù)d是360的正約數(shù)d且0a3，0b2，0c1。故14不是約數(shù)，16也不是約數(shù)。（3）問題轉(zhuǎn)化：即從集合的6個元素中任取0個、1個、6個的組合數(shù)之和。（4）求解：構(gòu)造多項式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6求各項系數(shù)之和： L135653124方法化簡：求P6(1)，即P6(1)43224（5）一般規(guī)律：設(shè)正整數(shù)n分解為n，L（四） 習(xí)題：18，211.4 組合等式及其組合意義組合等式的證明方法：（一） 歸納法（二） 組合意義法：借助于闡明等號兩端的不同表達(dá)式實質(zhì)上是同一個組合問題的方案數(shù)（即殊途同歸法），或者雖是兩個不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。對于恒等式的實質(zhì)揭露得更為深刻。（三） 母函數(shù)法：利用無窮級數(shù)（包括有限時的多項式）證明有關(guān)組合等式。是產(chǎn)生和證明組合恒等式的普遍方法?！镜仁?】對稱關(guān)系式 組合意義 從n個元素中取走r 個，必然余下nr個，故從n取r的組合與從n取nr的組合一一對應(yīng)。【等式2】加法公式 （一）組合意義：從n個元素中取r 個組合，以某個元素a1為準(zhǔn)，全體組合分類：（1） 每次取出的r 個元素中都含有a1：視為從剩下的n1個元素中任取r1個元素，然后再加上a1而構(gòu)成的組合，其組合數(shù)為。（2） 不含元素a1，視為從其余n1個元素中任取r個元素的組合，其數(shù)目為。兩類情況互不重復(fù)，由加法法則，總數(shù)為。（二）例：從1，2，3，4，5中取3個的組合情況為：第一類（包含元素“1”）： 123，124，125，134，135，145第二類（不包含元素“1”）： 234，235，245，345（三）路徑問題：等價形式組合意義：從（0，0）點到（m，n）點的路徑數(shù)等于從（0，0）點分別到（m，n1）點和（m1，n）點的路徑數(shù)之和。 B(m, n) A(0, 0)【等式3】乘法公式 組合意義 考慮等式左端：“將n個元素分為3堆，要求第一堆有nk個元素，第二堆有kr個，那么，第三堆就只有r個元素”的組合方案數(shù)。右端：“將n個元素分為3堆，要求第三堆有r個元素，第二堆有nk個，第一堆有kr個元素”的組合方案數(shù)。兩個組合問題等價，故其方案數(shù)亦相等。舉例：n20578，推廣：n個元素分為t堆，允許若干堆個數(shù)相等【等式4】C(nr1，r) C(nr，r)C(nr1，r1)C(nr2，r2)C(nr3，r3)C(n，0) （1.4.6）或 C(nr1，r) C(nr，n)C(nr1，n)C(nr2，n)C(n，n)（一）組合意義：從nr1個元素中取r 個的組合情況，分類統(tǒng)計：（1） 將所有組合針對分為兩類：含或不含。不含的組合數(shù)為，含的組合數(shù)為（加法公式）；（2） 仿照（1），再將含的所有組合針對分為兩類：含或不含。不含的組合數(shù)為；（3） 同法，含、，但不含的組合數(shù)為； 含、，但不含的組合數(shù)為； 含、的組合數(shù)為。（二）說明：等式3是等式2的推廣。（三）相應(yīng)的路徑問題： （r, n1） （0, 0）【等式5】Vandermonde（范德蒙）恒等式, rmin(m，n) （1.4.8）組合意義 n個相異的紅球，m個相異的藍(lán)球，選r個的組合。分類統(tǒng)計：有i個紅球，ri個藍(lán)球的選法有（i0, 1, , r）。特例：mr rn 【等式6】和式公式：組合意義 n個相異元素選i個的組合兩類元素可重復(fù)地選n個的排列例組合排列不不不不不不000000取不取不不取101001取取取取取取111111【等式7】組合意義：等式變形奇組合數(shù)偶組合數(shù)。構(gòu)造一一對應(yīng)關(guān)系：選某一元素a，設(shè)r為奇數(shù)（r1），在r組合中去掉a或加上a，可得其r1或r1（均為偶數(shù)）組合。反之亦然。例：n4r為奇數(shù)的組合aabcabdacdbcdbcdr為偶數(shù)的組合bcbdcdabacadabcd【等式8】 （1.4.12）組合意義：從n名先生、n名太太中選出n人，這n人中有一人擔(dān)任主席，并且必須為太太，考慮有多少種選法。選法1：先選一名太太任主席，再從其余2n1人中選n1人，選法總數(shù)為。選法2：先從n名太太中選k人，并從k人中選一人任主席，再從n名先生中選nk人（1kn），方法數(shù)選法總數(shù)【等式9】設(shè)r，M都是自然數(shù)，Mr則有 組合意義（概率問題）：設(shè)袋中有M個大小相同的球，其中白球r個，其余為黑球。每次摸出一個球，不放回，直至摸到白球為止。是必然事件（遲早會摸到白球），概率為1。另法：第一次摸到白球的概率為。第一次未摸到白球，第二次摸到白球的概率為，第k次才摸到白球的概率為而k2, 3, , Mr1。 【等式10】當(dāng)nm時，組合意義：從n人中選出m名正式代表及若干名列席代表的選法（列席代表人數(shù)不限）。統(tǒng)計方法一：先選正式代表，再從人中選列席代表，總的選法為。統(tǒng)計方法二：先選mk人（k0, 1, , nm） ，再從中選出m名正式代表，其余的k人為列席代表，有種選法?？倲?shù)1.5 多項式系數(shù)（一） Newton二項式（1） 二項展開式當(dāng)n是正整數(shù)時，Newton二項式定理 （1.5.1）的右端稱為二項式(ab)n的展開式，而組合數(shù)C(n，r)叫做二項式系數(shù)。（2） 組合意義將n個相異的球放入兩個盒子，a盒放入r個，b盒放入nr個，同盒的球不分次序，方案數(shù)為即項的系數(shù)為組合數(shù)。例 (ab)(ab)aaabbabb(ab)(ab)(ab)(aaabbabb)(ab)aaaaababaabbbaababbbabbb產(chǎn)生系數(shù)的根源：同一單項式中有順序，即排列問題（球不同的分配問題）。（二） 一般分配問題問題：將n個相異的球放入t個盒子，要求第1個盒子放入個，第2個盒子放入個，第t個盒子放入個，且盒中的球無次序，求不同的分配方案數(shù)。問題轉(zhuǎn)化：第i個盒中的個球是無序的，視為個相同的元素。問題：求重集（n1n2ntn）的全排列數(shù)RP(n，n)：仿照二項式系數(shù)，記為。（三） 多項式系數(shù)一般多項式系數(shù)與的關(guān)系：(xyz)3x3y3z33x2y3xy23x2z3y2z3xz23yz26xyzx3 y3 z3x2y xy2x2zy2zxz2yz2xyz x3 y3 z3x2yxy2x2z y2zxz2yz2xyz 【定理1.5.1】設(shè)n與t均為正整數(shù)，則有其中求和是在使的所有非負(fù)整數(shù)數(shù)列（n1, n2, , nt）上進(jìn)行。（證）（1）所有項都具形式，且（2）一般項的系數(shù)：在n個因式中先選出個因式且這個因式中都取，然后再在其余的n個因式中選出個因式且這個因式中都取，最后在剩下的個因式中都取。得項，其系數(shù)為稱為多項式系數(shù)。（四） 多項式展開的項數(shù)【定理1.5.2】展開式的項數(shù)等于，而這些項的系數(shù)之和為 .（證）展開式的項與從t個元素中取n個的n可重組合一一對應(yīng)。在定理1.5.1中令1得(111)n（五） 例【例1.5.1】求(abcd)3的展開式。 （解）n3，t4，有RC(，3)C(431，3) 20（項）(abcd)33333333333336abc6abd6acd6bcd【例1.5.2】的展開式中，項的系數(shù)420【例1.5.3】在的展開式中，項的系數(shù)是什么？（解）令a12x1，a23x2，a35x3。的展開式中的系數(shù)為，即(2x13x25x3)6中的系數(shù)。的系數(shù)：36000【例1.5.4】求證， n1（證）在二項式定理中取ax，b1x1【例1.5.5】今天是星期日，再過天是星期幾？（解）等價問題：除以7的余數(shù)除以7的余數(shù)4（mod 7）答：再過天是星期四。另法：34（mod 7）【例1.5.6】求證 0， n為自然數(shù) （1.5.4）（證）0.（六） 問題請給出多項式的展開式中和兩項的系數(shù)。答：22680，189/21.6 排列的生成算法1.6.1 序數(shù)法（一） 數(shù)的位權(quán)表示（1）十進(jìn)制數(shù)：小于的正整數(shù)n的位權(quán)形式：n， 0910例 315（r3）（2）推廣（p進(jìn)制數(shù)）n， 0p（3）特點： 固定進(jìn)制； 逢p進(jìn)一；十進(jìn)制r位數(shù)最小為0，最大為99991；將十進(jìn)制換算為p進(jìn)制數(shù)方法：除p取余法。（二） 變進(jìn)制表示（1）依據(jù)： n! (n1)(n1)!(n1)!遞歸：n!(n1)(n1)! (n2)(n2)! (n2)!(n1)(n1)! (n2)(n2)! (n3)(n3)! (n3)!(n1)(n1)! (n2)(n2)! 22！11！1！n!1n!1(n1)(n1)!(n2)(n2)!22!11!類似 199910 19結(jié)論：從0到n!1的任何整數(shù)m都可唯一地表示為man1(n1)!an2(n2)!a22!a11!其中 0ai（1，2，n1）結(jié)論： m將十進(jìn)制轉(zhuǎn)換為變進(jìn)制：203*3!1*2!0*1!（310）!301*4!1*3!0*2!0*1!（1100）1004*4!0*3!2*2!0*1!（4020）200（13110），8005（143201）（2）ai的計算man1(n1)!an2(n2)!a22!a11!記 n1man1an2a3a2m2!同理，a4(m)3!算法：其中表示不大于x的最大整數(shù)。 （3）特點： 變進(jìn)制； 從右向左，第位逢1進(jìn)一；n位數(shù)最小為0，最大為：(n1)(n1)!(n2)(n2)!22!11!n!1n!； 將十進(jìn)制換算為變進(jìn)制數(shù)方法。（三） 序數(shù)法（1）規(guī)則設(shè)n 個元素為1，2，n。對應(yīng)規(guī)則：設(shè)序列對應(yīng)排列（p），其中ai可以看作排列（p）中數(shù)i1所在位置后面比i1小的數(shù)的個數(shù)，即排列（p）中從數(shù)i1開始向右統(tǒng)計不大于i的數(shù)的個數(shù)。（2）實例1）排列數(shù)：n4 （p）（3124）(020)2）數(shù)排列 (111) （p）（2341）3）數(shù) 7 3 5 2 3 3 2 2 0 排列 3 5 A 8 6 4 9 7 1 2 數(shù)987654321 排列A 9 8 7 6 5 4 3 2 14）排列 3,5,7,9,10,8,6,4,2,1 數(shù) 5 5 4 4 3 3 2 2 1（3）4元排列的生成ma3 a2 a1p1 p2 p3 p4ma3 a2 a1p1 p2 p3 p4012345678910110000010100110200211001011101111201211234213413242314312432141243214313422341314232411213141516171819202122232002012102112202213003013103113203211423241314322431341234214123421341324231431243211.6.2 字典序法（一） 算法將所有n元排列按“字典順序”排成隊。初始排列：12n設(shè)當(dāng)前排列（p）（1） 求滿足關(guān)系式的k的最大值，設(shè)為i，即（2） 求滿足關(guān)系式的k的最大值，設(shè)為j，即（3） 與互換位置得 （q）（4） （q）中部分的順序逆轉(zhuǎn)，得新排列（二） 例（1）設(shè)3421：i2，j2，p1與p2交換得q1 q2 q3 q4 4321，321逆轉(zhuǎn)得下一排列4123 。n4的全部排列：1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321（2）85376421 i4，j6 q1 q2 q3q8 85476321 8541236785412367 i8，j8 q1 q2 q3q8 85412376 85412376 i7，j8 q1 q2 q3q8 85412673 8541263785413726 i8，j8 q1 q2 q3q8 8541376285413762 i6，j7 q1 q2 q3q8 85416732 854167231.6.3 鄰位互換生成算法初始排列：（當(dāng)一個數(shù)上方箭頭所指的一側(cè)相鄰的數(shù)比該數(shù)小時，稱該數(shù)處于活動狀態(tài)）設(shè)當(dāng)前排列（p）（1）若排列（p）（p1p2pn）中無一數(shù)處于活動狀態(tài)，則停止，否則轉(zhuǎn)（2）；（2）求所有處于活動狀態(tài)的數(shù)中的最大者，設(shè)為k，k和它的箭頭所指的一側(cè)的相鄰數(shù)互換位置，轉(zhuǎn)（3）；（3）令比k大的所有數(shù)的箭頭改變方向，轉(zhuǎn)（1）。舉例（n4）： 規(guī)律：4從一端移到另一端，共進(jìn)行了3次換位，然后暫停一次，3開始活動。3和4不能動時換2，依次類推。1.7 組合的生成算法【例】從6個元素1, 2, 3, 4, 5, 6中取3個的組合：123 124 125 126 134 135 136 145 146 156 234 235 236 245 246 256 345 346 356 456規(guī)律：（1）最后一位數(shù)最大可達(dá)n，倒數(shù)第二位數(shù)最大可達(dá)n1，依此類推，倒數(shù)第k位最大可達(dá)nk1（kr）。設(shè)組合c1c2cr滿足 c1< c2<< cr則 crn，cr1n1，c1nr1即 cinri，i1, 2, , r（2）當(dāng)存在cjnrj時，令imax，并令就可得到新的組合d1d2dr 。若每個cj nrj，則已經(jīng)達(dá)到最后一個組合，生成完畢。算法：初始組合： 當(dāng)前組合：c1c2cr（1）若imax存在，轉(zhuǎn)（2），否則，停止；（2）cici1;（3）cjcj11，ji1，i2，r . 輸出，轉(zhuǎn)（1）。例：n10，r514678 14679 1467A 14689 1468A 1469A 147891.8 應(yīng)用舉例【例1.8.1】試確定由1，2，3，4，5這五個數(shù)字能組成多少個大于43500的五位數(shù)？（解）有限制條件的RP(，5)的問題。下列情況之一發(fā)生便可導(dǎo)致“大于43500”：（1） 萬位上數(shù)字是5，其余四位上的數(shù)字從 1，2，3，4，5 中允許重復(fù)選取，共有15 4個符合要求的數(shù)；（2） 萬位上數(shù)字為4，千位上數(shù)字從4，5中選一個，其余三位上數(shù)字可從五個數(shù)字中重復(fù)選取，共有1253個；（3） 萬位、千位、百位上數(shù)字分別為4、3、5，其余二位上的數(shù)字可在1間重復(fù)選取，共有11152個。由加法法則，這樣的數(shù)總計為5425352900 （個）【例1.8.2】從2，1，0，1，2，3共6個數(shù)中不重復(fù)地選3個數(shù)作為二次函數(shù)的系數(shù)，使得拋物線的開口方向向下，共可作出多少個二次函數(shù)？（解）拋物線的開口方向向下，必有a<0。第一步：a從2、1中選一個，有種方法；第二步：在余下的五個數(shù)中選出兩個進(jìn)行排列，作為b和c，有種方法。根據(jù)乘法法則，共可作出二次函數(shù)40（個）【例1.8.3】滿足的正整數(shù)解有多少組？（解）方法思路：長度為100的線段被分為4段，每段的長度均為正整數(shù)，叫做，。例：10，35，40，15，10354015100。 問題轉(zhuǎn)化：在99個空的位置上放3個“”號，未放“”號的線段合成一條線段，求放法總數(shù)。首尾和兩“”之間至少一段。模型：將3個相同的球放入99個相異的盒子，每盒最多放一個球。排列組合問題：從99個相異元素中不重復(fù)地選3個。156849（組）方法：模型：將100個相同的“1”放入4個不同的盒子，每個盒子至少放一個。求不同的放法數(shù)。排列組合問題：從4種相異元素中可重復(fù)地選100個，每種元素至少選一個。第一步：每個盒子先放一個，共有一種放法。第二步：將余下的96個1放入，有變異一：求非負(fù)整數(shù)解（即）。用方法求解： 答：176851用方法求解：將100個相同的球放入4個不同的盒子，每個盒子的容量無限。求不同的放法數(shù)。答：176851變異二：求解。，。思想：將問題轉(zhuǎn)化為變異一。原方程 故令 ，得 （）答：解數(shù)為 166650問題：將原題用變異二的思路求解?！纠?.8.4】把r個相異物體放入n不同的盒子里,每個盒子允許放任意個物體,而且要考慮放入同一盒中的物體的次序,求這種分配方案有多少?（解）特點：既不是相異元素的不重復(fù)排列，也不是簡單的重復(fù)排列。思路：第一個物體的放法有n種，放入某盒子后，視為該盒子的隔板，將盒子分成了兩部分。第二個物體的放法有n1種，第三個物體的放法有n2種，第r個物體的放法有nr1種。由乘法原理，方案數(shù)為n(n1)(n2)(nr1)12345n1n說明：不考慮放入同一盒中相異物體的次序，分配方案數(shù)應(yīng)為應(yīng)用：A、B、C、D、E共5位同學(xué)由兩個門排隊進(jìn)入教室，每個門每次只能同時進(jìn)一人，問有多少種進(jìn)法？答：23456720種前門人數(shù)后門人數(shù)方法備注0515!1200!5!1414!1201!4!232!3!120323!2!120414!1!120505!0!120若不考慮次序，總數(shù)為32。問題1：設(shè)前門寬大，可以同時進(jìn)2人，那么又有多少種不同的進(jìn)法？答：有 345672520種。問題2：火車站外有100名乘客，欲從4個門排隊進(jìn)入候車室，問有多少種進(jìn)門的排隊方式？問題3：大樓共有19層，今有12人從一樓進(jìn)入電梯上樓，每層都可能有人出電梯，且電梯的門同時只能容許一個人出入，問有多少種方式出電梯？【例1.8.5】把元集S劃分成個無序非空子集（n4），共有多少種分法？ （解）模型：分配問題：將n個不同的球放入n3個相同的盒子，每個盒子最少一個球求解：分三類情況： (1) 一個子集為4元集，其余子集為一元集，等于n元集的不重復(fù)的4組合數(shù)；(2) 一個子集3元，一個子集2元，其余子集1元：n元集S的5組合數(shù)為，把5元集劃分成一個3元子集和一個2元子集的方法有10種，由乘法法則，此類劃分方法有10種；(3) 3個子集2元，其余子集1元：n元集的6組合數(shù)為，把6元子集劃分成3個2元子集的方法有 屬于此類的劃分方法有種。三類情況，互不重復(fù)，故由加法法則得L【例1.8.6】設(shè)是能夠從集合中選出兩兩之差均大于r的k元子集的方案數(shù)，試求。（解）集合A中取k個兩兩之差超過r的數(shù)構(gòu)成組合，設(shè)r1， 1ijk令 ， 則 1， 1ijk且 1n(k1)r結(jié)論：從A中選k個元素的方案從集合B不重復(fù)地選取k個元素的方案（B） 說明：r0，不重復(fù)組合-1，重復(fù)組合1，間隔選【例1.8.7】有7位科學(xué)家從事一項機密工作，他們的工作室裝有電子鎖，每位科學(xué)家都有打開電子鎖的“鑰匙”。為了安全起見，必須同時有4人在場時才能打開大門。試問該電子鎖至少應(yīng)具備多少個特征？每位科學(xué)家的“鑰匙”至少應(yīng)有多少種特征？（解）分析：任意3個人在一起，至少缺一種特征，不能打開電子鎖。結(jié)論1：電子鎖最少特征數(shù)C(7，3)35原因：每一組合所形成的3人小組缺少的特征必須不一樣的。1ABC8ACF15AFG22BDG29CEF2ABD9ACG16BCD23BEF30CEG3ABE10ADE17BCE24BEG31CFG4ABF11ADF18BCF25BFG32DEF5ABG12ADG19BCG26CDE33DEG6ACD13AEF20BDE27CDF34DFG7ACE14AEG21BDF28CDG35EFG結(jié)論2：某位科學(xué)家A的“鑰匙”的特征個數(shù)至少為C(6，3)20原因：A須有其余6人缺的鑰匙。例：A1635；B615，2635；C25，1015，2025，3235；【例1.8.8】從（0，0）點到達(dá)（m，n）點（m<n），要求中間所經(jīng)過的每一個格子點（a，b）恒滿足b>a，問有多少條最短路徑？（解）分析：第一步必須從（0，0）到（0，1）。等價于求滿足條件的從（0，1）點到（m，n）點的路徑數(shù)。從（1，0）到（m，n）的路徑從（0，1）到（m，n）點但經(jīng)過yx線上的格子點的路徑間 （m,n） （0，0）對應(yīng)規(guī)則：最后一次離開對角線之前對稱，之后重合。結(jié)論：所求路徑數(shù)(0，1)點到（m，n）點的所有路徑數(shù)（1，0）點到（m，n）點的所有路徑數(shù) N (mn1)! (mn1)! （nm） 【例1.8.9】n, h, r都是非負(fù)整數(shù)，并且。證明 （1.8.1） 等號何時成立？（解） 在中取kr個元，有種取法。一種特殊取法：先取前k個元素；再從其余的個元素中取r個，有種。結(jié)論：后一種取法是前者的部分情況。等號成立的條件：nkr（否則總有不全含的kr元子集）。反過來，當(dāng)nkr時，確實有【例1.8.10】（一） 二進(jìn)制串的漢明距離n位二進(jìn)制碼， 的個數(shù)為k，記為，稱為a、b碼的Hamming距離。例 (0000, 0000)0，(0000, 1001)2，(0101, 1010)4（二） 性質(zhì)三角不等式 （證）設(shè)，d(a，c)k。若，分別討論：（1），；（2），。應(yīng)有位滿足條件（1），位滿足條件（2），且。由Hamming距離的定義， 例：a（三） 檢錯碼與糾錯碼檢錯碼：奇偶校驗碼、漢明碼、BCH碼等。糾錯碼：漢明碼、BCH碼、郭帕碼等。（四） 漢明碼（1） 思想：如若與碼a的距離r，則認(rèn)為是a的錯誤碼而予以糾正。（2） 編碼的距離要求：任意兩個碼字a、b，滿足2r1否則可構(gòu)造c，使之滿足r而無法糾錯。反之，設(shè)任何2r1。若r，則由三角不等式知對其它碼字b，有(2r1)rr1r（3） 例：r1，n8字母碼字相近碼a0000000010000000，01000000，00000001b1110000001100000，10100000，11100001c0001110010011100，01011100，00011101（五） 編碼量編碼集：（n位二進(jìn)制碼）條件：與的距離小于等于r的數(shù)有個令Uia|d(a，ai)r，每個數(shù)最多只能屬于U1，U2，UM中的一個M 例n8，r1，M28n8，r2，M6n10，r2，M18n12，r2，M51習(xí)題1（1）基本題：19，14，16，19，2223，29，31（2）加強題：1112，17，18，21，28（3）提高題：13，15，20，2426，30，32（4）關(guān)聯(lián)題：10，271-1 在1到9999之間，有多少個每位上數(shù)字全不相同而且由奇數(shù)構(gòu)成的整數(shù)？（解）問題相當(dāng)于求在相異元素中不重復(fù)地取1個、2個、4個元素的所有排列數(shù)，答案為520601202051-2 比5400小并具有下列性質(zhì)的正整數(shù)有多少個？（1） 每位的數(shù)字全不同； （2） 每位數(shù)字不同且不出現(xiàn)數(shù)字2與7。（解）（1）分類統(tǒng)計：一位正整數(shù)有個；兩位正整數(shù)有81個；三位正整數(shù)有998648個；千位數(shù)小于5的四位數(shù)有49872016個；千位數(shù)等于5，百位數(shù)小于4的數(shù)有487224個。由乘法法則，滿足條件的數(shù)的總個數(shù)為98164820162242978（2）仿（1），總個數(shù)為74929463015011301-3 一教室有兩排，每排8個坐位，今有14名學(xué)生，問按下列不同的方式入座，各有多少種坐法？（1） 規(guī)定某5人總坐在前排，某4人總在后排，但每人具體坐位不指定；（2） 要求前排至少坐5人，后排至少坐4人。（解）（1）5人在前排就座，其坐法數(shù)為 ，4人在后排就座，其坐法數(shù)為 ，還空7個坐位，讓剩下的個人入坐，就座方式為 種，由乘法法則，就座方式總數(shù)為28 449 792 000（2）因前排至少需坐6人，