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

第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奇數(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）、藍（b）涂染平面正方形的四個頂點，若某種染色方案在正方形旋轉(zhuǎ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)系，求的解析表達式。（解）直接迭代即得：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）?！纠?.1.4】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產(chǎn)生冠軍共需要進行多少場比賽？（解）常規(guī)思路：502512632199場10000名選手：5000250012506253121采用一一對應(yīng)方法：每場比賽產(chǎn)生一個失敗者，且每個失敗者只能失敗一次。反之，要淘汰一個選手，必須恰好經(jīng)過一場比賽。結(jié)論：失敗者比賽場次。應(yīng)該比賽99場。一般情況：單循環(huán)淘汰制，n個選手，比賽n1場?！纠?.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.1 最短路徑（2）對應(yīng)為（元素可重復(fù)的）排列問題：路徑（藍色） 排列排列 路徑（紅色）結(jié)論：最短路徑7個x和5個y的排列（3）求解：再對應(yīng)為（元素不重復(fù)的）排列問題N792（4）一般情形：從（0，0）點到達（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種（加法法則）?？倲?shù)： 13991053種（數(shù)字可重復(fù)使用）（乘法法則）?！纠?.2.5】從A地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經(jīng)B或C到達目的地D共有多少種不同的走法? （解）路線ABD：種走法（乘法法則） 路線ACD：種走法（乘法法則）總數(shù)：種走法（加法法則）2334181.3 排列與組合1. 3. 1 相異元素不允許重復(fù)的排列數(shù)和組合數(shù)（一） 計算公式從n個相異元素中不重復(fù)地取r個元素的排列數(shù)和組合數(shù)：（1）排列： 推導(dǎo)：反復(fù)利用加法法則與乘法法則（2）組合： 推導(dǎo)：利用組合與排列的異同（3）例：n5，r3，即元素為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組合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)系未變，視為同一圓排列。結(jié)論：1個圓排列對應(yīng)n個線排列。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)的圓排列。即同一項鏈不用剪斷重穿，翻過來仍是原項鏈。結(jié)論：兩個圓排列對應(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為。例：n5，r4： 1111，1122，1345，5555（三） 計算公式設(shè)所選r個元素為：1a1a2arn令 ， i1，2，r則 1b1b 2brn(r1)反之 結(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種方案。 b d e a（3）將余下的3個空格插入4個間隔：分析：將3個相同的球放入4個不同的盒子，盒子的容量不限。方案1： b d e a方案2：b d e a歸納：從4個相異元素中可重復(fù)地取3個元素的組合數(shù)。（4）總方案數(shù)： L5！12024001. 3. 6 不盡相異元素任取r個的組合問題（一） 問題設(shè)集合（），從S中任取r個，求其組合數(shù)RC(n，r)。（二） 組合數(shù)中間工具：組合問題的母函數(shù)：答案：RC(n，r)（三） 應(yīng)用【例1.3.5】整數(shù)360有幾個正約數(shù)？（解）（1）標(biāo)準素因數(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)化：求集合的所有組合數(shù)之和。（4）求解：構(gòu)造多項式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系數(shù)求和： L135653124方法化簡：求P6(1)43224（5）一般規(guī)律：設(shè)正整數(shù)n分解為n，則L習(xí)題：18，211.4 組合等式及其組合意義組合等式的證明方法：（一） 歸納法（二） 組合意義法：借助于闡明等號兩端的不同表達式實質(zhì)上是同一個組合問題的方案數(shù)（殊途同歸法），或者雖是兩個不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對應(yīng)關(guān)系，因此等式兩端必須相等，從而達到證明等式成立的目的。對于恒等式的實質(zhì)揭露得更為深刻。（三） 母函數(shù)法：利用無窮級數(shù)（包括有限時的多項式）證明有關(guān)組合等式。是產(chǎn)生和證明組合恒等式的普遍方法。【等式1】對稱關(guān)系式 組合意義 從n個元素中取走r 個，必然余下nr個，故從n取r的組合與從n取nr的組合一一對應(yīng)?！镜仁?】加法公式 （一）組合意義：從n個元素中取r 個組合，以某個元素a1為準，全體組合分類：（1） 取出的元素中含有a1：視為從剩下的n1個元素中任取r1個元素，然后再加上a1而構(gòu)成的組合，其組合數(shù)為。（2） 不含元素a1，視為從其余n1個元素中任取r個元素的組合，其數(shù)目為?？倲?shù)：注意：無第三種情形；兩類情況互不重復(fù)；用加法法則。（二）例：從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】乘法公式 等式變形： 組合意義 （1） 左端：“將n個元素分為3堆：第一堆nk個，第二堆kr個，則第三堆為r個”，求組合方案數(shù)。（2） 右端：“將n個元素分為3堆：第三堆r個，第二堆nk個，第一堆kr個”，求組合方案數(shù)。（3） 兩個組合問題等價，故其方案數(shù)亦相等。舉例：n20578785，推廣：n個元素分為t堆，且可以若干堆個數(shù)相等n2042592945【等式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)（一）組合意義：（二）說明：等式4是等式2的推廣。（三）相應(yīng)的路徑問題： （r, n1） （0, 0）【等式5】Vandermonde（范德蒙）恒等式, rmin(m，n) 組合意義 n個相異的紅球，m個相異的藍球，選r個的組合。分類統(tǒng)計：i個紅球，ri個藍球的選法為（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)任主席，并且必須為太太，求選法數(shù)。選法1：先選一名太太任主席，再選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） 二項展開式n是正整數(shù)，Newton二項式定理 （1.5.1）右端稱為二項式(ab)n的展開式，組合數(shù)C(n，r)叫做二項式系數(shù)。 （2） 組合意義分配問題：將n個相異的球放入兩個盒子，a盒放入個，b盒放入個，同盒的球不分次序，方案數(shù)為即項的系數(shù)為組合數(shù)。例 (ab)(ab)aaabbabb(ab)(ab)(ab)(aaabbabb)(ab)aaaaababaabbbaababbbabbb產(chǎn)生系數(shù)的根源：同一單項式中有順序，即排列問題（球不同的分配問題）。排列問題：從兩種元素中選n個的排列（a選r個，b選nr個）（二） 一般分配問題問題：將n個相異的球放入t個盒子，要求第1個盒子放入個，第2個盒子放入個，第t個盒子放入個，且盒中的球無次序，求不同的分配方案數(shù)。問題轉(zhuǎn)化：第i個盒中的個球是無序的，視為個相同的元素。問題：求重集（n1n2ntn）的全排列數(shù)RP(n，n)：仿照二項式系數(shù)，記為。（三） 多項式系數(shù)一般多項式系數(shù)與的關(guān)系：(xyz)3x3y3z33x2y3xy23x2z6xyzx3 y3 z3x2y xy2x2zxyz x3 y3 z3x2yxy2x2z xyz 【定理1.5.1】設(shè)n與t均為正整數(shù)，則有其中求和是在使的所有非負整數(shù)數(shù)列（n1, n2, , nt）上進行。（證）（1）所有項都具形式，且（2）一般項的系數(shù)：在n個因式中先選出個因式且這個因式中都取，然后再在其余的n個因式中選出個因式且這個因式中都取，最后在剩下的個因式中都取。得項，其系數(shù)為稱為多項式系數(shù)。（四） 多項式展開的項數(shù)【定理1.5.2】展開式的項數(shù)等于，而這些項的系數(shù)之和為 .（證）展開式的項從t個元素中取n個的n可重組合。在定理1.5.1中令1得(111)n（五） 例【例1.5.1】求(abcd)3的展開式。 （解）n3，t4，有RC(，3)C(431，3) 20（項）(abcd)333336abc6abd6acd6bcd【例1.5.2】的展開式中，項的系數(shù)420【例1.5.3】在的展開式中，項的系數(shù)是什么？（解）令，。展開：的系數(shù)中的系數(shù)的系數(shù)：36000【例1.5.4】求證， n1（證）（證明組合等式）在二項式定理中取ax，b1x1【例1.5.5】今天是星期日，再過天是星期幾？（解）（求余數(shù)，同余運算）等價問題：除以7的余數(shù)除以7的余數(shù)4（mod 7）答：再過天是星期四。另法：34（mod 7）（六） 問題請給出多項式的展開式中和兩項的系數(shù)。答：22680，189/21.6 排列的生成算法1. 6. 1 序數(shù)法（一） 數(shù)的位權(quán)表示（1）十進制數(shù)：小于的正整數(shù)n的位權(quán)形式：n， 0910例 315（r3）（2）推廣（p進制數(shù)）n， 0p（3）特點： 固定進制； 逢p進一；十進制r位數(shù)最小為0，最大為99991；將十進制換算為p進制數(shù)方法：除p取余法。（二） 變進制表示（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將十進制轉(zhuǎ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）特點： 變進制； 從右向左，第位逢1進一；n1位數(shù)最小為0，最大為：(n1)(n1)!(n2)(n2)!22!11!n!1n!； 將十進制換算為變進制數(shù)方法。（三） 序數(shù)法（1）規(guī)則設(shè)n 個元素為1，2，n。特點：n元排列n1位變進制數(shù)。對應(yīng)規(guī)則：序列排列（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, A, 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利用當(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說明：第（4）步的必要性（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從一端移到另一端，共進行了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è)組合c1c2cr滿足 c1< c2<< cr則 crn，cr1n1，c1nr1即 cinri，i1, 2, , r（2）當(dāng)cjnrj時，令imax，并令得新組合d1d2dr 。若每個cj nrj，則已經(jīng)達到最后一個組合，生成完畢。算法：初始組合： 當(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)的問題）。分類統(tǒng)計：（1） 萬位上數(shù)字是5：有15 4個符合要求的數(shù)；（2） 萬位上數(shù)字為4，千位上數(shù)字為4，5：有1253個；（3） 萬、位、百位分別為4、3、5：有11152個?？倲?shù)： 5425352900 （個）【例1.8.2】從2，1，0，1，2，3共6個數(shù)中不重復(fù)地選3個數(shù)作為二次函數(shù)的系數(shù)，使得拋物線的開口方向向下，共可作出多少個二次函數(shù)？（解）（不重復(fù)排列）拋物線的開口方向向下，必有a0。第一步：a從2、1中選一個，有種方法；第二步：在余下的五個數(shù)中選b和c，有種方法。函數(shù)個數(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放入，有變異一：求非負整數(shù)解（即）。用方法求解： 答：176851用方法求解：將100個相同的球放入4個不同的盒子，每個盒子的容量無限。求不同的放法數(shù)。答：176851變異二：求解。，。思想：將問題轉(zhuǎn)化為變異一。原方程 變換 ，轉(zhuǎn)化 （）答：解數(shù)為 166650問題：將原題用變異二的思路求解。【例1.8.4】把r個相異物體放入n不同的盒子里,每個盒子允許放任意個物體,而且要考慮放入同一盒中的物體的次序,求這種分配方案有多少?（解）特點：既不是相異元素的不重復(fù)排列，也不是簡單的重復(fù)排列。思路：放一個物體增加一個隔板（盒子）。方案數(shù) n(n1)(n2)(nr1)12345n1n說明：不考慮盒中相異物體的次序，方案數(shù)為應(yīng)用：A、B、C、D、E共5位同學(xué)由兩個門排隊進入教室，每個門每次只能同時進一人，問有多少種進法？答：23456720種前門人數(shù)后門人數(shù)方法備注0515!1200!5!1414!1201!4!232!3!120323!2!120414!1!120505!0!120若不考慮次序，總數(shù)為32。問題1：設(shè)前門寬大，可以同時進2人，那么又有多少種不同的進法？答：有 345672520種。問題2：火車站外有100名乘客，欲從4個門排隊進入候車室，問有多少種進門的排隊方式？問題3：大樓共有19層，今有12人從一樓進入電梯上樓，每層都可能有人出電梯，且電梯的門同時只能容許一個人出入，問有多少種方式出電梯？【例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元子集的方法有 屬于此類的劃分方法有種。總數(shù) 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個選k，間隔k個選例：【例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）點到達（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都是非負整數(shù)，并且。證明 （1.8.1） 等號何時成立？（解）在中取kr個元，有種取法。一種特殊取法：先取前k個元素；再從其余的個元素中取r個，有種。結(jié)論：后一種取法是前者的部分情況。等號成立的條件：nkr（否則總有不全含的kr元子集）。反過來，當(dāng)nkr時，確實有【例1.8.10】（一） 二進制串的漢明距離n位二進制碼， 的個數(shù)為k，記為，稱為a、b碼的Hamming距離。例 (0000, 0000)0，(0000, 1001)2，(0101, 1010)4（二） 性質(zhì)三角不等式 （證）設(shè)，d(a，c)k。若，分別討論：l ，；l ，。應(yīng)有位滿足條件（1），位滿足條件（2），且。由Hamming距離的定義， 例：a0100，b1001，c1010（三） 檢錯碼與糾錯碼檢錯碼：奇偶校驗碼、漢明碼、BCH碼等。糾錯碼：漢明碼、BCH碼、郭帕碼等。（四） 漢明碼（1） 思想：如若與碼a的距離r，則認為是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可編碼字符數(shù)：n8，r1，M28n8，r2，M6n10，r2，M18n12，r2，M51（五） 編碼量編碼集：（n位二進制碼）條件：與的距離小于等于r的數(shù)有個令Uia|d(a，ai)r，每個數(shù)最多只能屬于U1，U2，UM中的一個編碼量： M 1.9 習(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)于求在相異元素1, 3, 5, 7, 9中不重復(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人，最多坐8人，后排也如此?？煞殖扇N情況分別討論：.前排恰好坐6人，入坐方式有種；. 前排恰好坐7人，入坐方式有種；前排恰好坐8人，入坐方式有種。各類入坐方式互相不同，由加法法則，總的入坐方式總數(shù)為誤：先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個座位。故總的入坐方式共有種。但這樣計算無疑是有重復(fù)的，例如恰好選6人坐前排，其余8人全坐后排，那么上式中的就有重復(fù)。1-4. 一位學(xué)者要在一周內(nèi)安排50個小時的工作時間，而且每天至少工作5小時，問共有多少種安排方案？（解）是重復(fù)組合問題。（1）每周按7天計算，先要拿出5735小時平均分配到每一天，再將其余的15小時安排到7天之中，每天的小時數(shù)不受限制，則安排方案數(shù)為（2）若每周的工作日按6天計，則問題變成在平均分配完5630小時后，再將余下的20小時分配到這6天中，但此時每天最多只能分配19小時?；蛘吒话?，每天在5小時外再最多工作小時，那么，答案是多項式中的系數(shù)，其中。（3）另外，設(shè)每周工作t天，每天最少工作5小時，最多工作小時，可以不按照上邊的兩步分配方法求解，而是直接計算多項式，中的系數(shù)，即得答案。1-5. 若某兩人拒絕相鄰而坐，問12個人圍圓桌就坐有多少種方式？答 11！210！910！1-