《《組合數(shù)學》教案 1章(排列組合基礎)》由會員分享，可在線閱讀，更多相關《《組合數(shù)學》教案 1章(排列組合基礎)（57頁珍藏版）》請在裝配圖網上搜索。
1、組合數(shù)學 第一章 組合數(shù)學基礎第1章 組合數(shù)學基礎1. 排列組合的基本計數(shù)問題2. 多項式系數(shù)的計算及其組合意義3. 排列組合算法1.1 緒 論（一） 背景起源：數(shù)學游戲幻方問題：給定自然數(shù)1, 2, , n2，將其排列成n階方陣，要求每行、每列和每條對角線上n個數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。每一行（或列、或對角線）之和稱為幻方的和（簡稱幻和）。例：3階幻方，幻和(1239)/315。關心的問題 （1） 存在性問題：即n階幻方是否存在？ （2） 計數(shù)問題：如果存在，對某個確定的n，這樣的幻方有多少種？ （3） 構造問題：即枚舉問題，亦即如何構造n階幻方。8162763579514
2、92438奇數(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 A2
3、C3 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）涂染平面正方形的四個頂點，若某種染色方案在正方形旋轉某個角度后，與另一個方案重合，則認為這兩個方案是相同的。求本質上不同的染色方案。舉例：ryybbbrb（a）（b）57/57 姜建國形式總數(shù)：81種。實際總數(shù)（見第6章）：L24【例1.1.3】（存在性）不同身高的26個人隨意排
4、成一行，那么，總能從中挑出6個人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見第5章）。注意：不改變原來的相對順序。（二） 研究內容算法分類：l 第一類：數(shù)值算法。主要解決數(shù)值計算問題，如方程求根、解方程組、求積分等，其數(shù)學基礎是高等數(shù)學與線性代數(shù)（解決建模問題，數(shù)值分析或稱計算方法解決離散化問題，即在計算機上的求解方法問題）。l 第二類：組合算法。解決搜索、排序、組合優(yōu)化等問題，其數(shù)學基礎為組合數(shù)學。按所研究問題的類型，研究內容：l 組合計數(shù)理論l 組合設計l 組合矩陣論l 組合優(yōu)化本課程重點：以組合計數(shù)理論為主，部分涉及其它內容。（三） 研究方法分類：第一類：從組合學基本概念、
5、基本原理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項式定理、Plya 定理解計數(shù)問題；解遞推關系的特征根方法、母函數(shù)方法；解存在性問題的抽屜原理等）。第二類：通常與問題所涉及的組合學概念無關，而對多種問題均可使用。例如：（1） 數(shù)學歸納法：前提是已知問題的結果。（2） 迭代法【例】已知數(shù)列滿足關系，求的解析表達式。（解）直接迭代即得：1（3） 一一對應技術原理：建立兩類事物之間的一一對應關系，把一個較復雜的組合計數(shù)問題A轉化成另一個容易計數(shù)的問題B，從而利用對B的計數(shù)運算達到對A的各種不同方案的計數(shù)。思路：將未解決問題的模式轉化為一種已經解決的問題模式。（4） 殊途同歸方法原理：從不同角度討論計
6、數(shù)問題，以建立組合等式。應用：組合恒等式的證明（也稱組合意義法）。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質進行分析推理的方法。組合數(shù)學用的較多的方法：（3）與（4）?！纠?.1.4】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問要產生冠軍共需要進行多少場比賽？（解）常規(guī)思路：502512632199場10000名選手：5000250012506253121采用一一對應方法：每場比賽產生一個失敗者，且每個失敗者只能失敗一次（場次失敗者）。反之，要淘汰一個選手，必須恰好經過一場比賽（失敗者場次）。結論：失敗者比賽場次。應該比賽99場。一般情況：單循環(huán)淘汰制，n個選手，比賽n
7、1場。【例1.1.5】設某地的街道將城市分割成矩形方格，某人在其住處的向東7個街道、向北5個街道的大廈處工作（見圖1.1.3），按照最短路徑（即只能向東或向北走），他每次上班必須經過某12個街段，問共有多少種不同的上班路線？（解）（1）將街道抽象為等長的。 （2）對應為（元素可重復的）排列問題：路徑（藍色） 排列排列 路徑（紅色）結論：最短路徑7個x和5個y的排列（3）求解：再對應為（元素不重復的）排列問題792（4）一般情形：從（0，0）點到達（m，n）點的不同的最短路徑數(shù)為 1.2 兩個基本法則1. 2. 1 加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個方案，而第一個方案有
8、m種方法，第二個方案有n種方法可以實現(xiàn)。只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同。則完成這件事情共有mn種方法。l 集合描述：設有限集合A有m個元素，B有n個元素，且A與B不相交，則A與B的并共有mn個元素。l 概率角度描述：設事件A有m種產生方式，事件B有n種產生方式，則事件“A或B”有mn種產生方式。當然A與B各自所含的基本事件是互相不同的。（二） 應用【例1.2.1】某班又男生18人，女生12人，從中選出一名代表參加會議，問共有多少種選法？（解）（1）兩個選擇方案：男生（18種選法）或女生（12種選法）。由加法法則，有181230選法。（2）設集合：A
9、男生，B女生。該班中的學生要么屬于A，要么屬于B，且AB，故181230。（3）事件A選男生（18種可能），事件B選女生（12種可能）。事件“A或B”選男生或女生，由加法法則，有181230種可能?！纠?.2.2】用一個小寫英文字母或一個阿拉伯數(shù)字給一批機器編號，問總共可能編出多少種號碼？（解）261036個。其中英文字母共有26個，數(shù)字09共10個。1. 2. 2 乘法法則（一） 乘法法則l 常規(guī)描述：如果完成一件事情需要兩個步驟，而第一步有m種方法、第二步有n種方法去實現(xiàn)。則完成該件事情共有mn種方法。l 集合描述：設有限集合A有m個元素，B有n個元素，且A與B不相交，記為一有序對。所有有
10、序對構成的集合稱為A和B的積集（或笛卡兒乘積），記作。那么，共有個元素。l 概率角度描述：設離散型隨機變量X有m個取值，Y有n個取值，則離散型隨機向量（X，Y）有種可能的取值。（二） 應用【例1.2.3】仍設某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問共有多少種選法？（解）（1）分兩步挑選，先選女生（12種選法），再選男生（18種選法）。由乘法法則，有1218216種選法。（2）設集合：A男生，B女生。由乘法法則，AB1812216。（3）變量X男生（18種取值），變量Y女生（12種取值）。由乘法法則，隨機向量（X，Y）有1812216種可能的值?！纠?.2
11、.4】給程序模塊命名，需要用3個字符，其中首字符要求用字母AG或UZ，后兩個要求用數(shù)字19，問最多可以給多少種程序命名？（解）首字符選法：7613種（加法法則）?？倲?shù)： 13991053種（數(shù)字可重復使用）（乘法法則）?！纠?.2.5】從A地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經B或C到達目的地D共有多少種不同的走法? （解）路線ABD：種走法（乘法法則） 路線ACD：種走法（乘法法則）總數(shù)：種走法（加法法則）2334181.3 排列與組合1. 3. 1 相異元素不允許重復的排列數(shù)和組合數(shù)（一） 計算公式從n個相
12、異元素中不重復地取r個元素的排列數(shù)和組合數(shù)：（1）排列： 推導：反復利用加法法則與乘法法則（2）組合： 推導：利用組合與排列的異同（3）例：n5，r3，即元素為1，2，3，4，5 排列：134，143，314，341，413，431；254，425，組合：134，245，（4）特點：排列考慮順序，組合不然。（二） 數(shù)學模型（1）排列問題：將r個有區(qū)別的球放入n個不同的盒子，每盒不超過一個，則總的放法數(shù)為P(n，r)。（2）組合問題：將r個無區(qū)別的球放入n個不同的盒子，每盒不超過一個，則總的放法數(shù)為C(n，r)。對應關系元素盒子位置球元素和位置編號12345A B C排列1ABC1 3 4排列2
13、CBA4 3 1排列3ACB1 4 3排列4ACB2 5 4排列5BAC4 2 5組合11 3 4組合22 4 51. 3. 2 相異元素允許重復的排列（一） 問題從n個不同元素中允許重復地選r個元素的排列，簡稱r元重復排列，排列數(shù)記為RP(，r)。（二） 模型將r個不相同的球放入n個有區(qū)別的盒子，每個盒子中的球數(shù)不加限制而且同盒的球不分次序。對應關系元素盒子位置球元素和位置編號12345A B C排列1ABC1 1 4排列2C BA4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5（三） 計算公式RP(，r)（四） 集合描述方式設無窮集合，從S中取r個元素的排
14、列數(shù)即為RP(，r)。不重復排列：S。1. 3. 3 不盡相異元素的全排列（一） 問題有限重復排列（或部分排列）：設（），從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對應關系元素盒子位置球元素和位置編號12345A B C排列1ABC1 1 4排列2B C A4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5說明：（1）極端情形：相異元素不重復的排列強調的是不重復，即
15、盒子的容量為1；（2）極端情形：相異元素允許重復的排列強調的是無限重復，即盒子的容量無限；（3）一般情形：不盡相異元素的排列強調的是有限重復，即盒子的容量有限，介于兩者之間。（三） 特例（1）1：RP(n, 1)t（2）n（全排列）例 與 與（3）t2，（4）1，即不重復的排列（5），即重復排列1. 3. 4 相異元素不允許重復的圓排列（一） 圓排列【例1.3.1】把n個有標號的珠子排成一個圓圈，共有多少種不同的排法？（解）稱為圓排列（相對于線排列）。條件：元素同時按同一方向旋轉，絕對位置變化，相對位置未變，即元素間的相鄰關系未變，視為同一圓排列。結論：1個圓排列對應n個線排列。(n1)!32
16、541 25413 54132 41325 13254【例1.3.2】從n個相異元素中不重復地取r個圍成圓排列，求不同的排列總數(shù)CP(n，r)。（解） CP(n，r) （二） 項鏈排列【例1.3.3】將5個標有不同序號的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱為項鏈排列。條件：可以翻轉的圓排列。即同一項鏈不用剪斷重穿，翻過來仍是原項鏈。結論：兩個圓排列對應一個項鏈排列，故有24/212種。（a） （b）圖1.3.1 項鏈排列一般情形：從n個相異珠子中取r個的項鏈排列數(shù)： 允許重復的圓排列：情況復雜，參見反演公式（第四章）。1. 3. 5 相異元素允許重復的組合（一） 問題設，從S中允許重復
17、地取r個元素構成組合，稱為r可重組合，其組合數(shù)記為RC(，r)。（二） 抽象記S為。例：n5，r4： 1111，1122，1345，5555（三） 計算公式設所選r個元素為：1a1a2arn令 ， i1，2，r則 1b1b 2brn(r1)反之 結論：與從nr1個相異元素中不重復地取r個元素的組合方案一一對應。 例：n5，r4分類重復組合不重復組合元素1，2，3，4，51，2，3，5，6，7，8部分組合11111234112212452245236855555678（四） 模型將r個無區(qū)別的球放入n個不同的盒子，每個盒子的球數(shù)不受限制。（五） 應用【例1.3.4】不同的5個字母通過通信線路被傳
18、送，每兩個相鄰字母之間至少插入3個空格，但要求空格的總數(shù)必須等于15，問共有多少種不同的傳送方式？（解）三步求解：（1）先排列5個字母，排列數(shù) P(5，5)5!。（2）兩個字母間各插入3個空格，將12個空格均勻地放入4個間隔內，有1種方案。 b d e a（3）將余下的3個空格插入4個間隔：分析：將3個相同的球放入4個不同的盒子，盒子的容量不限。方案1： b d e a方案2：b d e a歸納：從4個相異元素中可重復地取3個元素的組合數(shù)。（4）總方案數(shù)： L5！12024001. 3. 6 不盡相異元素任取r個的組合問題（一） 問題設集合（），從S中任取r個，求其組合數(shù)RC(n，r)。（二）
19、 組合數(shù)中間工具：組合問題的母函數(shù)：答案：RC(n，r)（三） 應用【例1.3.5】整數(shù)360有幾個正約數(shù)？（解）（1）標準素因數(shù)分解：36023325（2）正約數(shù)及其條件1203050，223050，320350，520305，22223050，6235032，902325，18022325，36023325結論：正整數(shù)d是360的正約數(shù)d且0a3，0b2，0c1。故14不是約數(shù)，16也不是約數(shù)。（3）問題轉化：求的所有組合數(shù)之和。（4）求解：構造多項式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系數(shù)求和： 135653124方法化簡：求P6(1)432
20、24（5）一般規(guī)律：設正整數(shù)n分解為，則習題：18，21小結：課程任務；技巧性。1.4 組合等式及其組合意義組合等式的證明方法：（1） 歸納法（2） 組合意義法：借助于闡明等號兩端的不同表達式實質上是同一個組合問題的方案數(shù)（殊途同歸法），或者雖是兩個不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對應關系，因此等式兩端必須相等，從而達到證明等式成立的目的。對于恒等式的實質揭露得更為深刻。（3） 母函數(shù)法：利用無窮級數(shù)（包括有限時的多項式）證明有關組合等式。是產生和證明組合恒等式的普遍方法。（4） 其它方法：二項式展開、反演公式等【等式1】對稱關系式 組合意義：的r組合nr組合【等式2】加法
21、公式 （一）組合意義：的r組合，分為兩類：（1） 取出的元素中含有：組合數(shù)為。（2） 不含元素，組合數(shù)為?？倲?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ù)之和。 【等式3】乘法公式 等式變形： 組合意義 （1） 左端：“將n個元素分為3堆：第一堆個，第二堆個，則第三堆為r個”，求
22、組合方案數(shù)。（2） 右端：“將n個元素分為3堆：第三堆r個，第二堆個，第一堆個”，求組合方案數(shù)。（3） 兩個組合問題等價。舉例：n20578785，推廣：n個元素分為t堆，且可以若干堆個數(shù)相等n2042592945，【等式4】C(nr1，r) C(nr，r)C(nr1，r1)C(nr2，r2)C(nr3，r3)C(n，0) 或 C(nr1，r) C(nr，n)C(nr1，n)C(nr2，n)C(n，n)（一）組合意義：（二）說明：等式2的推廣。（三）相應的路徑問題： 【等式5】Vandermonde（范德蒙）恒等式, rmin(m，n) 組合意義 n個相異的紅球，m個相異的藍球，選r個的組合。
23、分類統(tǒng)計：i個紅球，ri個藍球的選法為。特例：mr， rn【等式6】和式公式：組合意義：n個相異元素選i個的組合兩類元素的n可重排列組合排列不不不不不不000000取取取取取取111111取不取不不取101001【等式7】組合意義：等式變形奇組合數(shù)偶組合數(shù)。啟發(fā)：存在一一對應關系。例：n4奇組合aabcabdacdbcdbcd偶組合bcbdcdabacadabcd【等式8】組合意義：從n名先生、n名太太中選出n人，其中一人擔任主席，且必須為太太，求選法數(shù)。選法1：選一名太太任主席；再選n1人。選法總數(shù)為。選法2：從n名太太中選k人；從此k人中選一人任主席；再從n名先生中選nk人（1kn）。選法
24、總數(shù)【等式9】設r，M都是自然數(shù)，Mr則有 組合意義（概率問題）：設袋中有M個大小相同的球，其中白球r個，其余為黑球。每次摸出一個球，不放回，直至摸到白球為止。是必然事件（遲早會摸到白球），概率為1。另法：第一次摸到白球概率。第二次摸到白球，第k次才摸到白球（k2, 3, , Mr1）【等式10】當nm時，組合意義：從n人中選出m名正式代表及若干名列席代表的選法（列席代表人數(shù)不限）。統(tǒng)計方法一：先選正式代表，再從人中選列席代表，總的選法為。統(tǒng)計方法二：先選mk人（k0, 1, , nm） ，再從中選出m名正式代表，其余的k人為列席代表，有種選法?？倲?shù)1.5 多項式系數(shù)（一） Newton二項式
25、(1) 二項展開式Newton二項式定理（n是正整數(shù)）右端稱為二項式(ab)n的展開式，叫做二項式系數(shù)。(2) 組合意義分配問題：將n個相異的球放入兩個盒子，a盒放入個，b盒放入個，同盒的球不分次序，方案數(shù)為即項的系數(shù)為組合數(shù)。例 (ab)(ab)aaabbabb(ab)(ab)(ab)(aaabbabb)(ab)aaaaababaabbbaababbbabbb產生系數(shù)的根源：同一單項式中有順序，即排列問題（球不同的分配問題）。排列問題：從兩種元素中選n個的排列（a選r個，b選個）（二） 一般分配問題問題：將n個相異的球放入t個盒子，要求第1個盒子放入個，第2個盒子放入個，第t個盒子放入個，且
26、盒中的球無次序，求不同的分配方案數(shù)。轉化：求（n1n2ntn）的全排列數(shù)RP(n，n)：仿照二項式系數(shù)，記為。（三） 多項式系數(shù)一般多項式系數(shù)與的關系：x3y3z33x2y3xy23x2z6xyzx3 y3 z3x2y xy2x2zxyzx3y3z3x2yxy2x2z 【定理1.5.1】設n與t均為正整數(shù)，則有其中求和是在使的所有非負整數(shù)數(shù)列（n1,n2,nt）上進行。（證）（1）所有項都具形式，且（2）一般項的系數(shù)：個因式中選取，得項，其系數(shù)為稱為多項式系數(shù)。（四） 多項式展開的項數(shù)【定理1.5.2】展開式的項數(shù)等于，而這些項的系數(shù)之和為.（證）展開式的項從t種元素中取n個的n可重組合。在定
27、理1.5.1中令1得（五） 例【例1.5.1】求的展開式。（解）n3，t4，有RC(，3)C(431，3)20（項）33336abc6abd6acd6bcd【例1.5.2】的展開式中，項的系數(shù)。420【例1.5.3】在的展開式中，項的系數(shù)是什么？（解）令，。l 展開：的系數(shù)中的系數(shù)l 的系數(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/2）
28、。1.6 排列的生成算法1. 6. 1 序數(shù)法（一） 數(shù)的位權表示（1）十進制數(shù)：小于的正整數(shù)n的位權形式：n， 0910例 315（r3）（2）推廣（p進制數(shù)）n， 0p（3）特點：固定進制；逢p進一；十進制r位數(shù)最小為0，最大為99991；將十進制換算為p進制數(shù)方法：除p取余法。（二） 變進制表示（1）依據： 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!類似 1999101
29、9結論：從0到n!1的任何整數(shù)m都可唯一地表示為m(n1)!(n2)!2!1!其中 （1，2，n1）結論： m將十進制轉換為變進制：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）的計算記 an1an2a3a2m2!(m)3!算法：其中表示不大于x的最大整數(shù)。 （3）特點： 變進制； 從右向左，第位逢1進一；n1位數(shù)最小為0，最大為：(n1)(n1)!(n2)(n2)!22!11!n!1n!；將十進制換算為變進制數(shù)方法。（三） 序數(shù)法（1）規(guī)則設n 個元素
30、為1，2，n。特點：n元排列n1位變進制數(shù)。對應規(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
31、 p2 p3 p4ma3 a2 a1p1 p2 p3 p4012345678910110000010100110200211001011101111201211234213413242314312432141243214313422341314232411213141516171819202122232002012102112202213003013103113203211423241314322431341234214123421341324231431243211. 6. 2 字典序法（一） 算法將所有n元排列按照“字典順序”排成隊。初始排列： 設當前排列為（1） 求滿足關系式的k的最大值
32、，設為i，即（2） 求滿足關系式的k的最大值，設為j，即（3） 與互換位置得（4） 中部分的元素順序逆轉，得新排列。（二） 例（1）設3421：i2，j2，p1與p2交換得q1 q2 q3 q4 4321，321逆轉得下一排列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 85476321 854123678541236
33、7 i8，j8 85412376 85412376 i7，j8 85412673 8541263785413726 i8，j8 8541376285413762 i6，j7 85416732 854167231. 6. 3 鄰位互換生成算法初始排列：（當一個數(shù)上方箭頭所指的一側相鄰的數(shù)比該數(shù)小時，稱該數(shù)處于活動狀態(tài)）初始排列：設當前排列為 （1） 若排列中無一數(shù)處于活動狀態(tài)，則停止，否則轉（2）；（2） 求所有處于活動狀態(tài)的數(shù)中的最大者，設為k，k和它的箭頭所指的一側的相鄰數(shù)互換位置，轉（3）;（3） 令比k大的所有數(shù)的箭頭改變方向，轉（1）。舉例（n4）： 規(guī)律：4從一端移到另一端，共進行了
34、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）設組合c1c2cr滿足 c1c2cr則 crn，cr1n1，c1nr1即 cinri，i1, 2, , r（2）當cjnrj時，令imax，并令得新組合d1d2dr 。若每個cj nrj，則已經達到最后一個組合，生成完畢。算法：初始組合： 當前組合：（1）
35、若imax存在，轉（2），否則，停止；（2） cici1;（3） ，ji1, i2, , r。輸出，轉（1）。例：n10，r514678 14679 1467A 14689 1468A 1469A 147891.8 應用舉例【例1.8.1】試確定由1，2，3，4，5這五個數(shù)字能組成多少個大于43500的五位數(shù)？（解）（有限制條件的RP(，5)的問題）。分類統(tǒng)計：（1） 萬位上數(shù)字是5：有15 4個符合要求的數(shù)；（2） 萬位4，千位4，5：有1253個；（3） 萬、位、百位分別為4、3、5：有11152個?？倲?shù)： 5425352900 （個）【例1.8.2】從2，1，0，1，2，3共6個數(shù)中不重
36、復地選3個數(shù)作為二次函數(shù)的系數(shù)，使得拋物線的開口方向向下，共可作出多少個二次函數(shù)？（解）（不重復排列）拋物線開口向下a0。第一步：a從2、1中選一個，有種方法；第二步：在余下的五個數(shù)中選b和c，有種方法。函數(shù)個數(shù) 40（個）【例1.8.3】滿足的正整數(shù)解有多少組？（解）（組合問題）方法思路：長度為100的線段被分為4段，每段的長度均為正整數(shù)，記為，。例：10，35，40，15，10354015100。 問題轉化：在99個空位置上放3個“”號，未放“”號的線段合成一條線段，求放法總數(shù)。首尾和兩“”之間至少一段。分配模型：將3個相同的球放入99個相異的盒子，每盒最多放一個球。排列組合問題：從99個
37、相異元素中不重復地選3個。156849（組）方法：分配模型：將100個相同的“1”放入4個不同的盒子，每個盒子至少放一個。求不同的放法數(shù)。排列組合問題：從4種相異元素中可重復地選100個，每種元素至少選一個。第一步：每個盒子先放一個，共有一種放法。第二步：將余下的96個1放入，有變異一：求非負整數(shù)解（即）。用方法求解： 答：176851用方法求解：將100個相同的球放入4個不同的盒子，每個盒子的容量無限。求不同的放法數(shù)。答：176851變異二：求解。，。思想：將問題轉化為變異一。原方程 變換 ，轉化 （）答：解數(shù)為 166650問題：將原題用變異二的思路求解?！纠?.8.4】把r個相異物體放入
38、n不同的盒子里,每個盒子允許放任意個物體,而且要考慮放入同一盒中的物體的次序,求這種分配方案有多少?特點：既不是相異元素的不重復排列，也不是簡單的重復排列。思路：放一個物體增加一個隔板（盒子）。方案數(shù) n(n1)(n2)(nr1)12345n1n說明：不考慮盒中相異物體的次序，方案數(shù)為應用：A、B、C、D、E共5位同學由兩個門排隊進入教室，每個門每次只能同時進一人，問有多少種進法？答：23456720種前門人數(shù)后門人數(shù)方法備注0515!1200!5!1414!1201!4!232!3!120323!2!120414!1!120505!0!120若不考慮次序，總數(shù)為32。問題1：設前門寬大，可以
39、同時進2人，那么又有多少種不同的進法？答：有 345672520種。問題2：火車站外有100名乘客，欲從4個門排隊進入候車室，問有多少種進門的排隊方式？問題3：大樓共有19層，今有12人從一樓進入電梯上樓，每層都可能有人出電梯，且電梯的門同時只能容許一個人出入，問有多少種方式出電梯？【例1.8.5】把元集S劃分成個無序非空子集（n4），共有多少種分法？ （解）（球不同盒子相同）模型：分配問題：將n個不同的球放入n3個相同的盒子，每個盒子最少一個球求解：分三類情況： (1) 一個子集為4元集，其余子集為一元集，等于n元集的不重復的4組合數(shù)；(2) 一個子集3元，一個子集2元，其余子集1元：n元集
40、S的5組合數(shù)為，把5元集劃分成一個3元子集和一個2元子集的方法有10種，由乘法法則，此類劃分方法有10種；(3) 3個子集2元，其余子集1元：n元集的6組合數(shù)為，把6元子集劃分成3個2元子集的方法有 屬于此類的劃分方法有種?？倲?shù) L【例1.8.6】設是能夠從集合中選出兩兩之差均大于r的k元子集的方案數(shù)，試求。（解）（更一般的組合問題）集合A中取k個兩兩之差超過r的數(shù)構成組合，設r1， 1ijk令 ， 則 1， 1ijk且 1n(k1)r結論：從A中選k個元素的方案從集合B不重復地選取k個元素的方案（B） 說明：r0，不重復組合-1，重復組合1，間隔1個選m，間隔m個選例：【例1.8.7】有7位
41、科學家從事一項機密工作，他們的工作室裝有電子鎖，每位科學家都有打開電子鎖的“鑰匙”。為了安全起見，必須同時有4人在場時才能打開大門。試問該電子鎖至少應具備多少個特征？每位科學家的“鑰匙”至少應有多少種特征？（解）（秘密共享）分析：任意3個人在一起，至少缺一種特征，不能打開電子鎖。結論1：電子鎖最少特征數(shù)：C(7，3)35原因：每一組合所形成的3人小組缺少的特征必須不一樣的。1ABC8ACF15AFG22BDG29CEF2ABD9ACG16BCD23BEF30CEG3ABE10ADE17BCE24BEG31CFG4ABF11ADF18BCF25BFG32DEF5ABG12ADG19BCG26CD
42、E33DEG6ACD13AEF20BDE27CDF34DFG7ACE14AEG21BDF28CDG35EFG結論2：科學家A的“鑰匙”的特征個數(shù)至少為C(6，3)20原因：A須有其余6人缺的鑰匙。例：A1635；B615，2635；C25，1015，2025，3235；【例1.8.8】從（0，0）點到達（m，n）點（ma，問有多少條最短路徑？（解）分析：第一步必須從（0, 0）到（0, 1）。等價于從（0, 1）點到（m, n）點的路徑數(shù)（前提：滿足條件）。從（1, 0）到（m, n）的路徑從（0, 1）到（m, n）點但經過yx線上的格子點的路徑 （m, n） （0, 0）對應規(guī)則：最后一次
43、離開對角線之前對稱，之后重合。結論：所求路徑數(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個，有種。結論：后一種取法是前者的部分情況。等號成立的條件：nkr（否則總有不全含的kr元子集）。反過來，當nkr時，確實有【例1.8.10】（一） 二進制串的漢明距離位二進制碼， 的個數(shù)為k，記為，稱為a、b碼的Hamming距離。例：(0000, 000
44、0)0，(0000, 1001)2，(0101, 1010)4（二） 性質三角不等式 （三） 檢錯碼與糾錯碼檢錯碼：奇偶校驗碼、漢明碼、BCH碼等。糾錯碼：漢明碼、BCH碼、郭帕碼等。（四） 漢明碼（1） 思想：如若與碼a的距離r，則認為是a的錯誤碼而予以糾正。（2） 編碼的距離要求：2r1否則可構造c，使之滿足r而無法糾錯。反之，設任何2r1。若r，則由三角不等式知對其它碼字b，有(2r1)rr1r（3） 例：r1，n8字母碼字相近碼a0000000010000000，01000000，00000001b1110000001100000，10100000，11100001c000111001
45、0011100，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 習題1（1）基本題：19，14，16，19，2223，29，31（2）加強題：1112，17，18，21，28（3）提高題：13，15，20，2426，30，32（4）關聯(lián)題：10，271-1. 在1到9999之間，有多少個每位上數(shù)字全不相同而且由奇數(shù)構成的整數(shù)？（解）問題相當于求在相異元素1, 3
46、, 5, 7, 9中不重復地取1個、2個、4個元素的所有排列數(shù)，答案為520601202051-2. 比5400小并具有下列性質的正整數(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名學生，問按下列不同的方式入座，各有多少
47、種坐法？（1） 規(guī)定某5人總坐在前排，某4人總在后排，但每人具體坐位不指定；（2） 要求前排至少坐5人，后排至少坐4人。（解）（1）5人在前排就座，其坐法數(shù)為 ，4人在后排就座，其坐法數(shù)為 ，還空7個坐位，讓剩下的14545個人入坐，就座方式為 種，由乘法法則，就座方式總數(shù)為28 449 792 000（2）因前排至少需坐6人，最多坐8人，后排也如此?？煞殖扇N情況分別討論：.前排恰好坐6人，入坐方式有種；. 前排恰好坐7人，入坐方式有種；前排恰好坐8人，入坐方式有種。各類入坐方式互相不同，由加法法則，總的入坐方式總數(shù)為誤：先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個座位。故總的入
48、坐方式共有種。但這樣計算無疑是有重復的，例如恰好選6人坐前排，其余8人全坐后排，那么上式中的就有重復。1-4. 一位學者要在一周內安排50個小時的工作時間，而且每天至少工作5小時，問共有多少種安排方案？（解）是重復組合問題。（1）每周按7天計算，先要拿出5735小時平均分配到每一天，再將其余的15小時安排到7天之中，每天的小時數(shù)不受限制，則安排方案數(shù)為（2）若每周的工作日按6天計，則問題變成在平均分配完5630小時后，再將余下的20小時分配到這6天中，但此時每天最多只能分配19小時?；蛘吒话?，每天在5小時外再最多工作小時，那么，答案是多項式中的系數(shù)，其中。（3）另外，設每周工作t天，每天最少
49、工作5小時，最多工作小時，可以不按照上邊的兩步分配方法求解，而是直接計算多項式，中的系數(shù)，即得答案。1-5. 若某兩人拒絕相鄰而坐，問12個人圍圓桌就坐有多少種方式？（答） 11！210！910！1-6. 有15名選手，其中5名只能打后衛(wèi)，8名只能打前鋒，2名能打前鋒或后衛(wèi)，今欲選出11人組成一支球隊，而且需要7人打前鋒，4人打后衛(wèi)，試問有多少種選法？（答） 402(14080)(280802280)1 4001-7. 求展開式中項前的系數(shù)。（答） 100801-8. 求的展開式。（解）由多項式的展開式公式可以驗證，系數(shù)之和134663123811-9. 求展開式中的系數(shù)。（答） 8401-1
50、0. 試證任一正整數(shù)n可唯一地表成如下形式：n ，0aii， 1-11. 證明 nC(n1，r)(r1)C(n，r1)。并給出組合意義。意義：將n個人分為3組：一組1人，一組r人，另一組人。一種分法是先從n個人中選出r1人，剩下人為一組，再將所選的r1人分為兩組，一組1人，一組r人。另一種分法是先選一人為一組，再從其余的人中選人為一組，剩下的人為一組。1-12. 證明 。（證）用殊途同歸法。將n個不同的球放入標號為A、B、C的3個盒子，其中要求A盒只放1個球，其余兩盒的球數(shù)不限。那么，有兩種思路：（1） 先從此n個不同的球中選出1個，放入A盒，再將其余個球放入另外兩盒，有種放法；（2） 先由n個球中選出k個，再從所選的k個球中選出1個放入A盒，將其余的k1個球放入B盒，所剩的nk個球放入C盒，有種放法。當，各種情況互不重復，且包含了所有放法，故對k求和，即得等式左端。1-13. 有n個不同的整數(shù)，從中取出兩組來，要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù)，問有多少種方案？（解） 設取的第一組數(shù)有a個，第二組有b個，而要求第一組數(shù)中最小數(shù)大于第二組中最大的，即只要從n個數(shù)中
《組合數(shù)學》教案 1章(排列組合基礎)
