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

精選優(yōu)質(zhì)文檔-傾情為你奉上第1章 組合數(shù)學(xué)基礎(chǔ)1. 排列組合的基本計(jì)數(shù)問(wèn)題2. 多項(xiàng)式系數(shù)的計(jì)算及其組合意義3. 排列組合算法1.1 緒 論（一） 背景起源：數(shù)學(xué)游戲幻方問(wèn)題：給定自然數(shù)1, 2, , n2，將其排列成n階方陣，要求每行、每列和每條對(duì)角線上n個(gè)數(shù)字之和都相等。這樣的n階方陣稱為n階幻方。每一行（或列、或?qū)蔷€）之和稱為幻方的和（簡(jiǎn)稱幻和）。例：3階幻方，幻和(1239)/315。關(guān)心的問(wèn)題 （1） 存在性問(wèn)題：即n階幻方是否存在？ （2） 計(jì)數(shù)問(wèn)題：如果存在，對(duì)某個(gè)確定的n，這樣的幻方有多少種？ （3） 構(gòu)造問(wèn)題：即枚舉問(wèn)題，亦即如何構(gòu)造n階幻方。816276357951492438奇數(shù)階幻方的生成方法：一坐上行正中央，依次斜填切莫忘，上邊出格往下填，右邊出格往左填，右上有數(shù)往下填，右上出格往下填。例：將2，4，6，8，10，12，14，16，18填入下列幻方：【例1.1.1】（拉丁方）36名軍官問(wèn)題：有1，2，3，4，5，6共六個(gè)團(tuán)隊(duì)，從每個(gè)團(tuán)隊(duì)中分別選出具有A、B、C、D、E、F六種軍銜的軍官各一名，共36名軍官。問(wèn)能否把這些軍官排成6×6的方陣，使每行及每列的6名軍官均來(lái)自不同的團(tuán)隊(duì)且具有不同軍銜？本問(wèn)題的答案是否定的。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】（計(jì)數(shù)圖形染色）用3種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個(gè)頂點(diǎn)，若某種染色方案在正方形旋轉(zhuǎn)某個(gè)角度后，與另一個(gè)方案重合，則認(rèn)為這兩個(gè)方案是相同的。求本質(zhì)上不同的染色方案。舉例：ryybbbrb（a）（b）專心-專注-專業(yè)形式總數(shù)：81種。實(shí)際總數(shù)（見(jiàn)第6章）：L24【例1.1.3】（存在性）不同身高的26個(gè)人隨意排成一行，那么，總能從中挑出6個(gè)人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見(jiàn)第5章）。注意：不改變?cè)瓉?lái)的相對(duì)順序。（二） 研究?jī)?nèi)容算法分類：l 第一類：數(shù)值算法。主要解決數(shù)值計(jì)算問(wèn)題，如方程求根、解方程組、求積分等，其數(shù)學(xué)基礎(chǔ)是高等數(shù)學(xué)與線性代數(shù)（解決建模問(wèn)題，數(shù)值分析或稱計(jì)算方法解決離散化問(wèn)題，即在計(jì)算機(jī)上的求解方法問(wèn)題）。l 第二類：組合算法。解決搜索、排序、組合優(yōu)化等問(wèn)題，其數(shù)學(xué)基礎(chǔ)為組合數(shù)學(xué)。按所研究問(wèn)題的類型，研究?jī)?nèi)容：l 組合計(jì)數(shù)理論l 組合設(shè)計(jì)l 組合矩陣論l 組合優(yōu)化本課程重點(diǎn)：以組合計(jì)數(shù)理論為主，部分涉及其它內(nèi)容。（三） 研究方法分類：第一類：從組合學(xué)基本概念、基本原理出發(fā)解題的所謂常規(guī)方法（利用容斥原理、二項(xiàng)式定理、Pólya 定理解計(jì)數(shù)問(wèn)題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問(wèn)題的抽屜原理等）。第二類：通常與問(wèn)題所涉及的組合學(xué)概念無(wú)關(guān)，而對(duì)多種問(wèn)題均可使用。例如：（1） 數(shù)學(xué)歸納法：前提是已知問(wèn)題的結(jié)果。（2） 迭代法【例】已知數(shù)列滿足關(guān)系，求的解析表達(dá)式。（解）直接迭代即得：1（3） 一一對(duì)應(yīng)技術(shù)原理：建立兩類事物之間的一一對(duì)應(yīng)關(guān)系，把一個(gè)較復(fù)雜的組合計(jì)數(shù)問(wèn)題A轉(zhuǎn)化成另一個(gè)容易計(jì)數(shù)的問(wèn)題B，從而利用對(duì)B的計(jì)數(shù)運(yùn)算達(dá)到對(duì)A的各種不同方案的計(jì)數(shù)。思路：將未解決問(wèn)題的模式轉(zhuǎn)化為一種已經(jīng)解決的問(wèn)題模式。（4） 殊途同歸方法原理：從不同角度討論計(jì)數(shù)問(wèn)題，以建立組合等式。應(yīng)用：組合恒等式的證明（也稱組合意義法）。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進(jìn)行分析推理的方法。組合數(shù)學(xué)用的較多的是方法（3）與（4）。【例1.1.4】有100名選手參加羽毛球比賽，如果采用單循環(huán)淘汰制，問(wèn)要產(chǎn)生冠軍共需要進(jìn)行多少場(chǎng)比賽？（解）常規(guī)思路：502512632199場(chǎng)10000名選手：5000250012506253121采用一一對(duì)應(yīng)方法：每場(chǎng)比賽產(chǎn)生一個(gè)失敗者，且每個(gè)失敗者只能失敗一次。反之，要淘汰一個(gè)選手，必須恰好經(jīng)過(guò)一場(chǎng)比賽。結(jié)論：失敗者比賽場(chǎng)次。應(yīng)該比賽99場(chǎng)。一般情況：?jiǎn)窝h(huán)淘汰制，n個(gè)選手，比賽n1場(chǎng)。【例1.1.5】設(shè)某地的街道將城市分割成矩形方格，某人在其住處A(0，0)的向東7個(gè)街道、向北5個(gè)街道的大廈B(7，5)處工作（見(jiàn)圖1.1.3），按照最短路徑（即只能向東或向北走），他每次上班必須經(jīng)過(guò)某12個(gè)街段，問(wèn)共有多少種不同的上班路線？（解）（1）將街道抽象為等長(zhǎng)的。 B(7, 5) A(0, 0)圖1.1.1 最短路徑（2）對(duì)應(yīng)為（元素可重復(fù)的）排列問(wèn)題：路徑（藍(lán)色） 排列排列 路徑（紅色）結(jié)論：最短路徑7個(gè)x和5個(gè)y的排列（3）求解：再對(duì)應(yīng)為（元素不重復(fù)的）排列問(wèn)題N792（4）一般情形：從（0，0）點(diǎn)到達(dá)（m，n）點(diǎn)的不同的最短路徑數(shù)為 N1.2 兩個(gè)基本法則1. 2. 1 加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個(gè)方案，而第一個(gè)方案有m種方法，第二個(gè)方案有n種方法可以實(shí)現(xiàn)。只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同。則完成這件事情共有mn種方法。l 集合描述：設(shè)有限集合A有m個(gè)元素，B有n個(gè)元素，且A與B不相交，則A與B的并共有mn個(gè)元素。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人，從中選出一名代表參加會(huì)議，問(wèn)共有多少種選法？（解）（1）兩個(gè)選擇方案：選男生（18種選法）或女生（12種選法）。由加法法則，全班共有181230選法。（2）設(shè)集合：A男生，B女生。該班中的學(xué)生要么屬于A，要么屬于B，且AB，故181230。（3）事件A選男生（18種可能），事件B選女生（12種可能）。事件“A或B” 選男生或女生，由加法法則，有181230種可能。【例1.2.2】用一個(gè)小寫英文字母或一個(gè)阿拉伯?dāng)?shù)字給一批機(jī)器編號(hào)，問(wèn)總共可能編出多少種號(hào)碼？（解）261036個(gè)。其中英文字母共有26個(gè)，數(shù)字09共10個(gè)。1. 2. 2 乘法法則（一） 乘法法則l 常規(guī)描述：如果完成一件事情需要兩個(gè)步驟，而第一步有m種方法、第二步有n種方法去實(shí)現(xiàn)。則完成該件事情共有m·n種方法。l 集合描述：設(shè)有限集合A有m個(gè)元素，B有n個(gè)元素，且A與B不相交，記為一有序?qū)?。所有有序?qū)?gòu)成的集合稱為A和B的積集（或笛卡兒乘積），記作。那么，共有個(gè)元素。l 概率角度描述：設(shè)離散型隨機(jī)變量X有m個(gè)取值，Y有n個(gè)取值，則離散型隨機(jī)向量（X，Y）有種可能的取值。（二） 應(yīng)用【例1.2.3】仍設(shè)某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問(wèn)共有多少種選法？（解）（1）分兩步挑選，先選女生（12種選法），再選男生（18種選法）。由乘法法則，全班共有12×18216種選法。（2）設(shè)集合：A男生，B女生。由乘法法則，A×B18×12216。（3）變量X男生（18種取值），變量Y女生（12種取值）。由乘法法則，隨機(jī)向量（X，Y），有18×12216種可能的值?！纠?.2.4】給程序模塊命名，需要用3個(gè)字符，其中首字符要求用字母AG或UZ，后兩個(gè)要求用數(shù)字19，問(wèn)最多可以給多少種程序命名？（解）首字符選法：7613種（加法法則）?？倲?shù)： 13×9×91053種（數(shù)字可重復(fù)使用）（乘法法則）。【例1.2.5】從A地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經(jīng)B或C到達(dá)目的地D共有多少種不同的走法? （解）路線ABD：×種走法（乘法法則） 路線ACD：×種走法（乘法法則）總數(shù)：種走法（加法法則）2×33×4181.3 排列與組合1. 3. 1 相異元素不允許重復(fù)的排列數(shù)和組合數(shù)（一） 計(jì)算公式從n個(gè)相異元素中不重復(fù)地取r個(gè)元素的排列數(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）特點(diǎn)：排列考慮順序，組合不然。（二） 數(shù)學(xué)模型（1）排列問(wèn)題：將r個(gè)有區(qū)別的球放入n個(gè)不同的盒子，每盒不超過(guò)一個(gè)，則總的放法數(shù)為P(n，r)。（2）組合問(wèn)題：將r個(gè)無(wú)區(qū)別的球放入n個(gè)不同的盒子，每盒不超過(guò)一個(gè)，則總的放法數(shù)為C(n，r)。對(duì)應(yīng)關(guān)系元素盒子位置球元素和位置編號(hào)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ù)的排列（一） 問(wèn)題從n個(gè)不同元素中允許重復(fù)地選r個(gè)元素的排列，簡(jiǎn)稱r元重復(fù)排列，排列數(shù)記為RP(，r)。（二） 模型將r個(gè)不相同的球放入n個(gè)有區(qū)別的盒子，每個(gè)盒子中的球數(shù)不加限制而且同盒的球不分次序。對(duì)應(yīng)關(guān)系元素盒子位置球元素和位置編號(hào)12345A B C排列1ABC1 1 4排列2C BA4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5（三） 計(jì)算公式RP(，r)（四） 集合描述方式設(shè)無(wú)窮集合，從S中取r個(gè)元素的排列數(shù)即為RP(，r)。不重復(fù)排列：S。1. 3. 3 不盡相異元素的全排列（一） 問(wèn)題有限重復(fù)排列（或部分排列）：設(shè)（），從S中任取r個(gè)元素，求其排列數(shù)RP(n，r)。（二） 模型將r個(gè)有區(qū)別的球放入t個(gè)不同的盒子，每個(gè)盒子的容量有限的，其中第i個(gè)盒子最多只能放入個(gè)球，求分配方案數(shù)。例： S2·1，4·2，1·3，3·4，2·51，1，2，2，2，2，3，4，4，4，5，5對(duì)應(yīng)關(guān)系元素盒子位置球元素和位置編號(hào)12345A B C排列1ABC1 1 4排列2B C A4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5說(shuō)明：（1）極端情形：相異元素不重復(fù)的排列強(qiáng)調(diào)的是不重復(fù)，即盒子的容量為1；（2）極端情形：相異元素允許重復(fù)的排列強(qiáng)調(diào)的是無(wú)限重復(fù)，即盒子的容量無(wú)限；（3）一般情形：不盡相異元素的排列強(qiáng)調(diào)的是有限重復(fù)，即盒子的容量有限，介于兩者之間。（三） 特例 （1） 1：RP(n, 1)t （2） n（全排列）即n個(gè)不同元素的全排列（n!種），但每個(gè)排列實(shí)際重復(fù)統(tǒng)計(jì)了次。例 與 與 （3） t2， （4） 1，即不重復(fù)的排列 （5） ，即重復(fù)排列1. 3. 4 相異元素不允許重復(fù)的圓排列（一） 圓排列【例1.3.1】把n個(gè)有標(biāo)號(hào)的珠子排成一個(gè)圓圈，共有多少種不同的排法？（解）稱為圓排列（相對(duì)于線排列）。條件：元素同時(shí)按同一方向旋轉(zhuǎn)，絕對(duì)位置變化，相對(duì)位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。結(jié)論：1個(gè)圓排列對(duì)應(yīng)n個(gè)線排列。CP(n，n)(n1)!32541 25413 54132 41325 13254【例1.3.2】從n個(gè)相異元素中不重復(fù)地取r個(gè)圍成圓排列，求不同的排列總數(shù)CP(n，r)。（解） CP(n，r) （二） 項(xiàng)鏈排列【例1.3.3】將5個(gè)標(biāo)有不同序號(hào)的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱為項(xiàng)鏈排列。條件：可以翻轉(zhuǎn)的圓排列。即同一項(xiàng)鏈不用剪斷重穿，翻過(guò)來(lái)仍是原項(xiàng)鏈。結(jié)論：兩個(gè)圓排列對(duì)應(yīng)一個(gè)項(xiàng)鏈排列，故有24/212種。（a） （b）圖1.3.1 項(xiàng)鏈排列一般情形，從n個(gè)相異珠子中取r個(gè)的項(xiàng)鏈排列數(shù)： 允許重復(fù)的圓排列：情況復(fù)雜，參見(jiàn)反演公式（第四章）。1. 3. 5 相異元素允許重復(fù)的組合（一） 問(wèn)題設(shè)，從S中允許重復(fù)地取r個(gè)元素構(gòu)成組合，稱為r可重組合，其組合數(shù)記為RC(，r)。（二） 抽象記S為。例：n5，r4： 1111，1122，1345，5555（三） 計(jì)算公式設(shè)所選r個(gè)元素為：1a1a2arn令 ， i1，2，r則 1b1b 2brn(r1)反之 結(jié)論：與從nr1個(gè)相異元素中不重復(fù)地取r個(gè)元素的組合方案一一對(duì)應(yīng)。 例：n5，r4分類重復(fù)組合不重復(fù)組合元素1，2，3，4，51，2，3，5，6，7，811111234112212452245236855555678（四） 模型將r個(gè)無(wú)區(qū)別的球放入n個(gè)不同的盒子，每個(gè)盒子的球數(shù)不受限制。（五） 應(yīng)用【例1.3.4】不同的5個(gè)字母通過(guò)通信線路被傳送，每?jī)蓚€(gè)相鄰字母之間至少插入3個(gè)空格，但要求空格的總數(shù)必須等于15，問(wèn)共有多少種不同的傳送方式？（解）三步求解：（1）先排列5個(gè)字母，排列數(shù) P(5，5)5!。（2）兩個(gè)字母間各插入3個(gè)空格，將12個(gè)空格均勻地放入4個(gè)間隔內(nèi)，有1種方案。 b d e a（3）將余下的3個(gè)空格插入4個(gè)間隔：分析：將3個(gè)相同的球放入4個(gè)不同的盒子，盒子的容量不限。方案1： b d e a方案2：b d e a歸納：從4個(gè)相異元素中可重復(fù)地取3個(gè)元素的組合數(shù)。（4）總方案數(shù)： L5！·1·2024001. 3. 6 不盡相異元素任取r個(gè)的組合問(wèn)題（一） 問(wèn)題設(shè)集合（），從S中任取r個(gè)，求其組合數(shù)RC(n，r)。（二） 組合數(shù)中間工具：組合問(wèn)題的母函數(shù)：答案：RC(n，r)（三） 應(yīng)用【例1.3.5】整數(shù)360有幾個(gè)正約數(shù)？（解）（1）標(biāo)準(zhǔn)素因數(shù)分解：36023×32×5（2）正約數(shù)及其條件120×30×50，22×30×50，320×3×50，520×30×5，2222×30×50，62×3×503×2，902×32×5，18022×32×5，36023×32×5結(jié)論：正整數(shù)d是360的正約數(shù)d且0a3，0b2，0c1。故14不是約數(shù)，16也不是約數(shù)。（3）問(wèn)題轉(zhuǎn)化：求集合的所有組合數(shù)之和。（4）求解：構(gòu)造多項(xiàng)式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系數(shù)求和： L135653124方法化簡(jiǎn)：求P6(1)4×3×224（5）一般規(guī)律：設(shè)正整數(shù)n分解為n，則L習(xí)題：18，211.4 組合等式及其組合意義組合等式的證明方法：（一） 歸納法（二） 組合意義法：借助于闡明等號(hào)兩端的不同表達(dá)式實(shí)質(zhì)上是同一個(gè)組合問(wèn)題的方案數(shù)（殊途同歸法），或者雖是兩個(gè)不同組合問(wèn)題的方案數(shù)，但二者的組合方案之間存在著一一對(duì)應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。對(duì)于恒等式的實(shí)質(zhì)揭露得更為深刻。（三） 母函數(shù)法：利用無(wú)窮級(jí)數(shù)（包括有限時(shí)的多項(xiàng)式）證明有關(guān)組合等式。是產(chǎn)生和證明組合恒等式的普遍方法?！镜仁?】對(duì)稱關(guān)系式 組合意義 從n個(gè)元素中取走r 個(gè)，必然余下nr個(gè)，故從n取r的組合與從n取nr的組合一一對(duì)應(yīng)。【等式2】加法公式 （一）組合意義：從n個(gè)元素中取r 個(gè)組合，以某個(gè)元素a1為準(zhǔn)，全體組合分類：（1） 取出的元素中含有a1：視為從剩下的n1個(gè)元素中任取r1個(gè)元素，然后再加上a1而構(gòu)成的組合，其組合數(shù)為。（2） 不含元素a1，視為從其余n1個(gè)元素中任取r個(gè)元素的組合，其數(shù)目為?？倲?shù)：注意：無(wú)第三種情形；兩類情況互不重復(fù)；用加法法則。（二）例：從1，2，3，4，5中取3個(gè)的組合情況為：第一類（包含元素“1”）： 123，124，125，134，135，145第二類（不包含元素“1”）： 234，235，245，345（三）路徑問(wèn)題：等價(jià)形式組合意義：從（0，0）點(diǎn)到（m，n）點(diǎn)的路徑數(shù)等于從（0，0）點(diǎn)分別到（m，n1）點(diǎn)和（m1，n）點(diǎn)的路徑數(shù)之和。 B(m, n) A(0, 0)【等式3】乘法公式 等式變形： 組合意義 （1） 左端：“將n個(gè)元素分為3堆：第一堆nk個(gè)，第二堆kr個(gè)，則第三堆為r個(gè)”，求組合方案數(shù)。（2） 右端：“將n個(gè)元素分為3堆：第三堆r個(gè)，第二堆nk個(gè)，第一堆kr個(gè)”，求組合方案數(shù)。（3） 兩個(gè)組合問(wèn)題等價(jià)，故其方案數(shù)亦相等。舉例：n20578785，推廣：n個(gè)元素分為t堆，且可以若干堆個(gè)數(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)（一）組合意義：（二）說(shuō)明：等式4是等式2的推廣。（三）相應(yīng)的路徑問(wèn)題： （r, n1） （0, 0）【等式5】Vandermonde（范德蒙）恒等式, rmin(m，n) 組合意義 n個(gè)相異的紅球，m個(gè)相異的藍(lán)球，選r個(gè)的組合。分類統(tǒng)計(jì)：i個(gè)紅球，ri個(gè)藍(lán)球的選法為（i0, 1, , r）。特例：mr， rn 【等式6】和式公式：組合意義 n個(gè)相異元素選i個(gè)的組合兩類元素可重復(fù)地選n個(gè)的排列組合排列不不不不不不取不取不不取取取取取取取【等式7】組合意義：等式變形奇組合數(shù)偶組合數(shù)。構(gòu)造一一對(duì)應(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人中選一人任主席，再?gòu)膎名先生中選nk人（1kn），方法數(shù)選法總數(shù)【等式9】設(shè)r，M都是自然數(shù)，Mr則有 組合意義（概率問(wèn)題）：設(shè)袋中有M個(gè)大小相同的球，其中白球r個(gè)，其余為黑球。每次摸出一個(gè)球，不放回，直至摸到白球?yàn)橹?。是必然事件（遲早會(huì)摸到白球），概率為1。另法：第一次摸到白球概率。第二次摸到白球，第k次才摸到白球（k2, 3, , Mr1）【等式10】當(dāng)nm時(shí)，組合意義：從n人中選出m名正式代表及若干名列席代表的選法（列席代表人數(shù)不限）。統(tǒng)計(jì)方法一：先選正式代表，再?gòu)娜酥羞x列席代表，總的選法為。統(tǒng)計(jì)方法二：先選mk人（k0, 1, , nm） ，再?gòu)闹羞x出m名正式代表，其余的k人為列席代表，有種選法?？倲?shù)1.5 多項(xiàng)式系數(shù)（一） Newton二項(xiàng)式 （1） 二項(xiàng)展開(kāi)式n是正整數(shù)，Newton二項(xiàng)式定理 （1.5.1）右端稱為二項(xiàng)式(ab)n的展開(kāi)式，組合數(shù)C(n，r)叫做二項(xiàng)式系數(shù)。 （2） 組合意義分配問(wèn)題：將n個(gè)相異的球放入兩個(gè)盒子，a盒放入個(gè)，b盒放入個(gè)，同盒的球不分次序，方案數(shù)為即項(xiàng)的系數(shù)為組合數(shù)。例 (ab)(ab)aaabbabb(ab)(ab)(ab)(aaabbabb)(ab)aaaaababaabbbaababbbabbb產(chǎn)生系數(shù)的根源：同一單項(xiàng)式中有順序，即排列問(wèn)題（球不同的分配問(wèn)題）。排列問(wèn)題：從兩種元素中選n個(gè)的排列（a選r個(gè)，b選nr個(gè)）（二） 一般分配問(wèn)題問(wèn)題：將n個(gè)相異的球放入t個(gè)盒子，要求第1個(gè)盒子放入個(gè)，第2個(gè)盒子放入個(gè)，第t個(gè)盒子放入個(gè)，且盒中的球無(wú)次序，求不同的分配方案數(shù)。問(wèn)題轉(zhuǎn)化：第i個(gè)盒中的個(gè)球是無(wú)序的，視為個(gè)相同的元素。問(wèn)題：求重集（n1n2ntn）的全排列數(shù)RP(n，n)：仿照二項(xiàng)式系數(shù)，記為。（三） 多項(xiàng)式系數(shù)一般多項(xiàng)式系數(shù)與的關(guān)系：(xyz)3x3y3z33x2y3xy23x2z6xyzx3 y3 z3x2y xy2x2zxyz x3 y3 z3x2yxy2x2z xyz 【定理1.5.1】設(shè)n與t均為正整數(shù)，則有其中求和是在使的所有非負(fù)整數(shù)數(shù)列（n1, n2, , nt）上進(jìn)行。（證）（1）所有項(xiàng)都具形式，且（2）一般項(xiàng)的系數(shù)：在n個(gè)因式中先選出個(gè)因式且這個(gè)因式中都取，然后再在其余的n個(gè)因式中選出個(gè)因式且這個(gè)因式中都取，最后在剩下的個(gè)因式中都取。得項(xiàng)，其系數(shù)為稱為多項(xiàng)式系數(shù)。（四） 多項(xiàng)式展開(kāi)的項(xiàng)數(shù)【定理1.5.2】展開(kāi)式的項(xiàng)數(shù)等于，而這些項(xiàng)的系數(shù)之和為 .（證）展開(kāi)式的項(xiàng)從t個(gè)元素中取n個(gè)的n可重組合。在定理1.5.1中令1得(111)n（五） 例【例1.5.1】求(abcd)3的展開(kāi)式。 （解）n3，t4，有RC(，3)C(431，3) 20（項(xiàng)）(abcd)333336abc6abd6acd6bcd【例1.5.2】的展開(kāi)式中，項(xiàng)的系數(shù)420【例1.5.3】在的展開(kāi)式中，項(xiàng)的系數(shù)是什么？（解）令，。展開(kāi)：的系數(shù)中的系數(shù)的系數(shù)：36000【例1.5.4】求證， n1（證）（證明組合等式）在二項(xiàng)式定理中取ax，b1x1【例1.5.5】今天是星期日，再過(guò)天是星期幾？（解）（求余數(shù)，同余運(yùn)算）等價(jià)問(wèn)題：除以7的余數(shù)除以7的余數(shù)4（mod 7）答：再過(guò)天是星期四。另法：34（mod 7）（六） 問(wèn)題請(qǐng)給出多項(xiàng)式的展開(kāi)式中和兩項(xiàng)的系數(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）特點(diǎn)： 固定進(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)! 2·2！1·1！1！n!1n!1(n1)(n1)!(n2)(n2)!2·2!1·1!類似 19·9·9·10 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（）（2）ai的計(jì)算man1(n1)!an2(n2)!a22!a11!記 n1man1an2a3a2m÷2!同理，a4(m)÷3!算法：其中表示不大于x的最大整數(shù)。 （3）特點(diǎn)： 變進(jìn)制； 從右向左，第位逢1進(jìn)一；n1位數(shù)最小為0，最大為：(n1)(n1)!(n2)(n2)!2·2!1·1!n!1n!； 將十進(jìn)制換算為變進(jìn)制數(shù)方法。（三） 序數(shù)法（1）規(guī)則設(shè)n 個(gè)元素為1，2，n。特點(diǎn)：n元排列n1位變進(jìn)制數(shù)。對(duì)應(yīng)規(guī)則：序列排列（p），其中ai為排列（p）中數(shù)i1所在位置后面比i1小的數(shù)的個(gè)數(shù)，即排列（p）中從數(shù)i1開(kāi)始向右統(tǒng)計(jì)不大于i的數(shù)的個(gè)數(shù)（2）實(shí)例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ù) 排列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元排列按照“字典順序”排成隊(duì)。初始排列：12n利用當(dāng)前排列（p）求下一個(gè)排列：（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說(shuō)明：第（4）步的必要性（2） i4，j6 q1 q2 q3q8 i8，j8 q1 q2 q3q8 i7，j8 q1 q2 q3q8 i8，j8 q1 q2 q3q8 i6，j7 q1 q2 q3q8 1. 6. 3 鄰位互換生成算法初始排列：（當(dāng)一個(gè)數(shù)上方箭頭所指的一側(cè)相鄰的數(shù)比該數(shù)小時(shí)，稱該數(shù)處于活動(dòng)狀態(tài)）設(shè)當(dāng)前排列（p）（1）若排列（p）（p1p2pn）中無(wú)一數(shù)處于活動(dòng)狀態(tài)，則停止，否則轉(zhuǎn)（2）；（2）求所有處于活動(dòng)狀態(tài)的數(shù)中的最大者，設(shè)為k，k和它的箭頭所指的一側(cè)的相鄰數(shù)互換位置，轉(zhuǎn)（3）；（3）令比k大的所有數(shù)的箭頭改變方向，轉(zhuǎn)（1）。舉例（n4）： 規(guī)律：4從一端移到另一端，共進(jìn)行了3次換位，然后暫停一次，3開(kāi)始活動(dòng)。3和4不能動(dòng)時(shí)換2，依次類推。1.7 組合的生成算法【例】從6個(gè)元素1, 2, 3, 4, 5, 6中取3個(gè)的組合：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時(shí)，令imax，并令得新組合d1d2dr 。若每個(gè)cj nrj，則已經(jīng)達(dá)到最后一個(gè)組合，生成完畢。算法：初始組合： 當(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這五個(gè)數(shù)字能組成多少個(gè)大于43500的五位數(shù)？（解）（有限制條件的RP(，5)的問(wèn)題）。分類統(tǒng)計(jì)：（1） 萬(wàn)位上數(shù)字是5：有1×5 4個(gè)符合要求的數(shù)；（2） 萬(wàn)位上數(shù)字為4，千位上數(shù)字為4，5：有1×2×53個(gè)；（3） 萬(wàn)、位、百位分別為4、3、5：有1×1×1×52個(gè)。總數(shù)： 542×5352900 （個(gè)）【例1.8.2】從2，1，0，1，2，3共6個(gè)數(shù)中不重復(fù)地選3個(gè)數(shù)作為二次函數(shù)的系數(shù)，使得拋物線的開(kāi)口方向向下，共可作出多少個(gè)二次函數(shù)？（解）（不重復(fù)排列）拋物線的開(kāi)口方向向下，必有a0。第一步：a從2、1中選一個(gè)，有種方法；第二步：在余下的五個(gè)數(shù)中選b和c，有種方法。函數(shù)個(gè)數(shù) 40（個(gè)）【例1.8.3】滿足的正整數(shù)解有多少組？（解）（組合問(wèn)題）方法思路：長(zhǎng)度為100的線段被分為4段，每段的長(zhǎng)度均為正整數(shù)，記為，。例：10，35，40，15，10354015100。 問(wèn)題轉(zhuǎn)化：在99個(gè)空位置上放3個(gè)“”號(hào)，未放“”號(hào)的線段合成一條線段，求放法總數(shù)。首尾和兩“”之間至少一段。模型：將3個(gè)相同的球放入99個(gè)相異的盒子，每盒最多放一個(gè)球。排列組合問(wèn)題：從99個(gè)相異元素中不重復(fù)地選3個(gè)。（組）方法：模型：將100個(gè)相同的“1”放入4個(gè)不同的盒子，每個(gè)盒子至少放一個(gè)。求不同的放法數(shù)。排列組合問(wèn)題：從4種相異元素中可重復(fù)地選100個(gè)，每種元素至少選一個(gè)。第一步：每個(gè)盒子先放一個(gè)，共有一種放法。第二步：將余下的96個(gè)1放入，有變異一：求非負(fù)整數(shù)解（即）。用方法求解： 答：用方法求解：將100個(gè)相同的球放入4個(gè)不同的盒子，每個(gè)盒子的容量無(wú)限。求不同的放法數(shù)。答：變異二：求解。，。思想：將問(wèn)題轉(zhuǎn)化為變異一。原方程 變換 ，轉(zhuǎn)化 （）答：解數(shù)為 問(wèn)題：將原題用變異二的思路求解?！纠?.8.4】把r個(gè)相異物體放入n不同的盒子里,每個(gè)盒子允許放任意個(gè)物體,而且要考慮放入同一盒中的物體的次序,求這種分配方案有多少?（解）特點(diǎn)：既不是相異元素的不重復(fù)排列，也不是簡(jiǎn)單的重復(fù)排列。思路：放一個(gè)物體增加一個(gè)隔板（盒子）。方案數(shù) n(n1)(n2)(nr1)12345n1n說(shuō)明：不考慮盒中相異物體的次序，方案數(shù)為應(yīng)用：A、B、C、D、E共5位同學(xué)由兩個(gè)門排隊(duì)進(jìn)入教室，每個(gè)門每次只能同時(shí)進(jìn)一人，問(wèn)有多少種進(jìn)法？答：2×3×4×5×6720種前門人數(shù)后門人數(shù)方法備注051×5!120×0!×5!14×1×4!120×1!×4!23×2!×3!12032×3!×2!12041×4!×1!12050×5!×0!120若不考慮次序，總數(shù)為32。問(wèn)題1：設(shè)前門寬大，可以同時(shí)進(jìn)2人，那么又有多少種不同的進(jìn)法？答：有 3×4×5×6×72520種。問(wèn)題2：火車站外有100名乘客，欲從4個(gè)門排隊(duì)進(jìn)入候車室，問(wèn)有多少種進(jìn)門的排隊(duì)方式？問(wèn)題3：大樓共有19層，今有12人從一樓進(jìn)入電梯上樓，每層都可能有人出電梯，且電梯的門同時(shí)只能容許一個(gè)人出入，問(wèn)有多少種方式出電梯？【例1.8.5】把元集S劃分成個(gè)無(wú)序非空子集（n4），共有多少種分法？ （解）（球不同盒子相同）模型：分配問(wèn)題：將n個(gè)不同的球放入n3個(gè)相同的盒子，每個(gè)盒子最少一個(gè)球求解：分三類情況： (1) 一個(gè)子集為4元集，其余子集為一元集，等于n元集的不重復(fù)的4組合數(shù)；(2) 一個(gè)子集3元，一個(gè)子集2元，其余子集1元：n元集S的5組合數(shù)為，把5元集劃分成一個(gè)3元子集和一個(gè)2元子集的方法有10種，由乘法法則，此類劃分方法有10種；(3) 3個(gè)子集2元，其余子集1元：n元集的6組合數(shù)為，把6元子集劃分成3個(gè)2元子集的方法有 屬于此類的劃分方法有種。總數(shù) L【例1.8.6】設(shè)是能夠從集合中選出兩兩之差均大于r的k元子集的方案數(shù)，試求。（解）（更一般的組合問(wèn)題）集合A中取k個(gè)兩兩之差超過(guò)r的數(shù)構(gòu)成組合，設(shè)r1， 1ijk令 ， 則 1， 1ijk且 1n(k1)r結(jié)論：從A中選k個(gè)元素的方案從集合B不重復(fù)地選取k個(gè)元素的方案（B） 說(shuō)明：r0，不重復(fù)組合-1，重復(fù)組合1，間隔1個(gè)選k，間隔k個(gè)選例：【例1.8.7】有7位科學(xué)家從事一項(xiàng)機(jī)密工作，他們的工作室裝有電子鎖，每位科學(xué)家都有打開(kāi)電子鎖的“鑰匙”。為了安全起見(jiàn)，必須同時(shí)有4人在場(chǎng)時(shí)才能打開(kāi)大門。試問(wèn)該電子鎖至少應(yīng)具備多少個(gè)特征？每位科學(xué)家的“鑰匙”至少應(yīng)有多少種特征？（解）（秘密共享）分析：任意3個(gè)人在一起，至少缺一種特征，不能打開(kāi)電子鎖。結(jié)論1：電子鎖最少特征數(shù)C(7，3)35原因：每一組合所形成的3人小組缺少的特征必須不一樣的。1ABC8ACF15AFG22BDG29CEF2ABD9ACG16BCD23BEF30CEG3ABE10ADE17BCE24BEG31CFG4ABF11ADF18BCF25BFG32DEF5ABG12ADG19BCG26CDE33DEG6ACD13AEF20BDE27CDF34DFG7ACE14AEG21BDF28CDG35EFG結(jié)論2：某位科學(xué)家A的“鑰匙”的特征個(gè)數(shù)至少為C(6，3)20原因：A須有其余6人缺的鑰匙。例：A1635；B615，2635；C25，1015，2025，3235；【例1.8.8】從（0，0）點(diǎn)到達(dá)（m，n）點(diǎn)（m<n），要求中間所經(jīng)過(guò)的每一個(gè)格子點(diǎn)（a，b）恒滿足b>a，問(wèn)有多少條最短路徑？（解）分析：第一步必須從（0，0）到（0，1）。等價(jià)于求滿足條件的從（0，1）點(diǎn)到（m，n）點(diǎn)的路徑數(shù)。從（1，0）到（m，n）的路徑從（0，1）到（m，n）點(diǎn)但經(jīng)過(guò)yx線上的格子點(diǎn)的路徑間 （m,n） （0，0）對(duì)應(yīng)規(guī)則：最后一次離開(kāi)對(duì)角線之前對(duì)稱，之后重合。結(jié)論：所求路徑數(shù)(0，1)點(diǎn)到（m，n）點(diǎn)路徑數(shù)(1，0)點(diǎn)到（m，n）點(diǎn)路徑數(shù) N (mn1)! (mn1)! （nm） 【例1.8.9】n, h, r都是非負(fù)整數(shù)，并且。證明 （1.8.1） 等號(hào)何時(shí)成立？（解）在中取kr個(gè)元，有種取法。一種特殊取法：先取前k個(gè)元素；再?gòu)钠溆嗟膫€(gè)元素中取r個(gè)，有種。結(jié)論：后一種取法是前者的部分情況。等號(hào)成立的條件：nkr（否則總有不全含的kr元子集）。反過(guò)來(lái)，當(dāng)nkr時(shí)，確實(shí)有【例1.8.10】（一） 二進(jìn)制串的漢明距離n位二進(jìn)制碼， 的個(gè)數(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（三） 檢錯(cuò)碼與糾錯(cuò)碼檢錯(cuò)碼：奇偶校驗(yàn)碼、漢明碼、BCH碼等。糾錯(cuò)碼：漢明碼、BCH碼、郭帕碼等。（四） 漢明碼（1） 思想：如若與碼a的距離r，則認(rèn)為是a的錯(cuò)誤碼而予以糾正。（2） 編碼的距離要求：任意兩個(gè)碼字a、b，滿足2r1否則可構(gòu)造c，使之滿足r而無(wú)法糾錯(cuò)。反之，設(shè)任何2r1。若r，則由三角不等式知對(duì)其它碼字b，有(2r1)rr1r（3） 例：r1，n8字母碼字相近碼a，b，c，可編碼字符數(shù)：n8，r1，M28n8，r2，M6n10，r2，M18n12，r2，M51（五） 編碼量編碼集：（n位二進(jìn)制碼）條件：與的距離小于等于r的數(shù)有個(gè)令Uia|d(a，ai)r，每個(gè)數(shù)最多只能屬于U1，U2，UM中的一個(gè)編碼量： M 1.9 習(xí)題1（1）基本題：19，14，16，19，2223，29，31（2）加強(qiáng)題：1112，17，18，21，28（3）提高題：13，15，20，2426，30，32（4）關(guān)聯(lián)題：10，271-1. 在1到9999之間，有多少個(gè)每位上數(shù)字全不相同而且由奇數(shù)構(gòu)成的整數(shù)？（解）問(wèn)題相當(dāng)于求在相異元素1, 3, 5, 7, 9中不重復(fù)地取1個(gè)、2個(gè)、4個(gè)元素的所有排列數(shù)，答案為520601202051-2. 比5400小并具有下列性質(zhì)的正整數(shù)有多少個(gè)？（1） 每位的數(shù)字全不同； （2） 每位數(shù)字不同且不出現(xiàn)數(shù)字2與7。（解）（1）分類統(tǒng)計(jì)：一位正整數(shù)有個(gè)；兩位正整數(shù)有81個(gè)；三位正整數(shù)有9×9×8648個(gè)；千位數(shù)小于5的四位數(shù)有4×9×8×72016個(gè)；千位數(shù)等于5，百位數(shù)小于4的數(shù)有4×8×7224個(gè)。由乘法法則，滿足條件的數(shù)的總個(gè)數(shù)為98164820162242978（2）仿（1），總個(gè)數(shù)為74929463015011301-3. 一教室有兩排，每排8個(gè)坐位，今有14名學(xué)生，問(wèn)按下列不同的方式入座，各有多少種坐法？（1） 規(guī)定某5人總坐在前排，某4人總在后排，但每人具體坐位不指定；（2） 要求前排至少坐5人，后排至少坐4人。（解）（1）5人在前排就座，其坐法數(shù)為 ，4人在后排就座，其坐法數(shù)為 ，還空7個(gè)坐位，讓剩下的個(gè)人入坐，就座方式為 種，由乘法法則，就座方式總數(shù)為28 449 792 000（2）因前排至少需坐6人，最多坐8人，后排也如此?？煞殖扇N情況分別討論：.前排恰好坐6人，入坐方式有種；. 前排恰好坐7人，入坐方式有種；前排恰好坐8人，入坐方式有種。各類入坐方式互相不同，由加法法則，總的入坐方式總數(shù)為誤：先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個(gè)座位。故總的入坐方式共有種。但這樣計(jì)算無(wú)疑是有重復(fù)的，例如恰好選6人坐前排，其余8人全坐后排，那么上式中的就有重復(fù)。1-4. 一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作時(shí)間，而且每天至少工作5小時(shí)，問(wèn)共有多少種安排方案？（解）是重復(fù)組合問(wèn)題。（1）每周按7天計(jì)算，先要拿出5×735小時(shí)平均分配到每一天，再將其余的15小時(shí)安排到7天之中，每天的小時(shí)數(shù)不受限制，則安排方案數(shù)為（2）若每周的工作日按6天計(jì)，則問(wèn)題變成在平均分配完5×630小時(shí)后，再將余下的20小時(shí)分配到這6天中，但此時(shí)每天最多只能分配19小時(shí)。或者更一般，每天在5小時(shí)外再最多工作小時(shí)，那么，答案是多項(xiàng)式中的系數(shù)，其中。（3）另外，設(shè)每周工作t天，每天最少工作5小時(shí)，最多工作小時(shí)，可以不按照上邊的兩步分配方法求解，而是直接計(jì)算多項(xiàng)式，中的系數(shù)，即得答案。1-5. 若某兩人拒絕相鄰而坐，問(wèn)12個(gè)人圍圓桌就坐有多少種方式？答 11！2×10！9×10！1-6. 有15名選手，其中5名只能打后衛(wèi)，8名只能打前鋒，2名能打前鋒或后衛(wèi)，今欲選出11人組成一支球隊(duì)，而且需要7人打前鋒，4人打后衛(wèi)，試問(wèn)有多少種選法？答 402×(14080)(280802×280)1 4001-7. 求展開(kāi)式中項(xiàng)前的系數(shù)。答 100801-8. 求的展開(kāi)式。（解）由多項(xiàng)式的展開(kāi)式公式