【正文】 式2】加法公式 （一）組合意義：的r組合，分為兩類(lèi)：（1） 取出的元素中含有：組合數(shù)為。 組合等式及其組合意義組合等式的證明方法：（1） 歸納法（2） 組合意義法：借助于闡明等號(hào)兩端的不同表達(dá)式實(shí)質(zhì)上是同一個(gè)組合問(wèn)題的方案數(shù)（殊途同歸法），或者雖是兩個(gè)不同組合問(wèn)題的方案數(shù)，但二者的組合方案之間存在著一一對(duì)應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。（二） 組合數(shù)中間工具：組合問(wèn)題的母函數(shù)：＝＝答案：RC(n，r)＝（三） 應(yīng)用【】整數(shù)360有幾個(gè)正約數(shù)？（解）（1）標(biāo)準(zhǔn)素因數(shù)分解：360＝23325（2）正約數(shù)及其條件1＝203050，2＝23050，3＝20350，5＝20305，22＝223050，6＝2350＝32，…90＝2325，180＝22325，360＝23325結(jié)論：正整數(shù)d是360的正約數(shù)d＝且0≤a≤3，0≤b≤2，0≤c≤1。方案1：△△△▲▲ b △△△ d △△△▲ e △△△ a方案2：△△△b △△△ d △△△e △△△▲▲▲ a歸納：從4個(gè)相異元素中可重復(fù)地取3個(gè)元素的組合數(shù)。∴ 例： n＝5，r＝4分類(lèi)重復(fù)組合不重復(fù)組合元素1，2，3，4，51，2，3，5，6，7，8部分組合11111234112212452245236855555678（四） 模型將r個(gè)無(wú)區(qū)別的球放入n個(gè)不同的盒子，每個(gè)盒子的球數(shù)不受限制。（a） （b） 項(xiàng)鏈排列一般情形：從n個(gè)相異珠子中取r個(gè)的項(xiàng)鏈排列數(shù)： ＝ 允許重復(fù)的圓排列：情況復(fù)雜，參見(jiàn)反演公式（第四章）。（解） CP(n，r)＝ ＝（二） 項(xiàng)鏈排列【】將5個(gè)標(biāo)有不同序號(hào)的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱(chēng)為項(xiàng)鏈排列。（三） 特例（1）＝1：RP(n, 1)＝t（2）＝n（全排列）例 與 與（3）t＝2，（4）＝1，即不重復(fù)的排列（5），即重復(fù)排列1. 3. 4 相異元素不允許重復(fù)的圓排列（一） 圓排列【】把n個(gè)有標(biāo)號(hào)的珠子排成一個(gè)圓圈，共有多少種不同的排法？（解）稱(chēng)為圓排列（相對(duì)于線(xiàn)排列）。2，11. 3. 3 不盡相異元素的全排列（一） 問(wèn)題有限重復(fù)排列（或部分排列）：設(shè)（），從S中任取r個(gè)元素，求其排列數(shù)RP(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組合1●●●1 3 4組合2●●●2 4 51. 3. 2 相異元素允許重復(fù)的排列（一） 問(wèn)題從n個(gè)不同元素中允許重復(fù)地選r個(gè)元素的排列，簡(jiǎn)稱(chēng)r元重復(fù)排列，排列數(shù)記為RP(∞，r)?？倲?shù)： 1399＝1053種（數(shù)字可重復(fù)使用）（乘法法則）。由乘法法則，AB＝1812＝216。l 概率角度描述：設(shè)離散型隨機(jī)變量X有m個(gè)取值，Y有n個(gè)取值，則離散型隨機(jī)向量（X，Y）有種可能的取值。n種方法?！尽坑靡粋€(gè)小寫(xiě)英文字母或一個(gè)阿拉伯?dāng)?shù)字給一批機(jī)器編號(hào)，問(wèn)總共可能編出多少種號(hào)碼？（解）26＋10＝36個(gè)。（2）設(shè)集合：A——男生，B——女生。l 概率角度描述：設(shè)事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則事件“A或B”有m＋n種產(chǎn)生方式。 （2）對(duì)應(yīng)為（元素可重復(fù)的）排列問(wèn)題：路徑（藍(lán)色）→ 排列ｘｙｙｘｘｙｙｘｘｘｘｙ排列ｙｘｘｙｙｙｙｘｘｘｘｘ → 路徑（紅色）結(jié)論：最短路徑7個(gè)x和5個(gè)y的排列（3）求解：再對(duì)應(yīng)為（元素不重復(fù)的）排列問(wèn)題＝＝＝792（4）一般情形：從（0，0）點(diǎn)到達(dá)（m，n）點(diǎn)的不同的最短路徑數(shù)為 兩個(gè)基本法則1. 2. 1 加法法則（一） 加法法則l 常規(guī)描述：如果完成一件事情有兩個(gè)方案，而第一個(gè)方案有m種方法，第二個(gè)方案有n種方法可以實(shí)現(xiàn)。結(jié)論：失敗者比賽場(chǎng)次。（5） 數(shù)論方法特別是利用整數(shù)的奇偶性、整除性等數(shù)論性質(zhì)進(jìn)行分析推理的方法。（解）直接迭代即得：＝＋1＝＝＝＝＝（3） 一一對(duì)應(yīng)技術(shù)原理：建立兩類(lèi)事物之間的一一對(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ù)。lya 定理解計(jì)數(shù)問(wèn)題；解遞推關(guān)系的特征根方法、母函數(shù)方法；解存在性問(wèn)題的抽屜原理等）。l 第二類(lèi)：組合算法。實(shí)際總數(shù)（見(jiàn)第6章）：L＝＝24【】（存在性）不同身高的26個(gè)人隨意排成一行，那么，總能從中挑出6個(gè)人，讓其出列后，他們的身高必然是由低到高或由高到低排列的（見(jiàn)第5章）。問(wèn)能否把這些軍官排成66的方陣，使每行及每列的6名軍官均來(lái)自不同的團(tuán)隊(duì)且具有不同軍銜？本問(wèn)題的答案是否定的。例：3階幻方，幻和＝(1＋2＋3＋…＋9)/3＝15。《組合數(shù)學(xué)》 第一章 組合數(shù)學(xué)基礎(chǔ)第1章 組合數(shù)學(xué)基礎(chǔ)1. 排列組合的基本計(jì)數(shù)問(wèn)題2. 多項(xiàng)式系數(shù)的計(jì)算及其組合意義3. 排列組合算法 緒 論（一） 背景起源：數(shù)學(xué)游戲幻方問(wèn)題：給定自然數(shù)1, 2, …, n2，將其排列成n階方陣，要求每行、每列和每條對(duì)角線(xiàn)上n個(gè)數(shù)字之和都相等。關(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階幻方。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【】（計(jì)數(shù)——圖形染色）用3種顏色紅（r）、黃（y）、藍(lán)（b）涂染平面正方形的四個(gè)頂點(diǎn)，若某種染色方案在正方形旋轉(zhuǎn)某個(gè)角度后，與另一個(gè)方案重合，則認(rèn)為這兩個(gè)方案是相同的。注意：不改變?cè)瓉?lái)的相對(duì)順序。解決搜索、排序、組合優(yōu)化等問(wèn)題，其數(shù)學(xué)基礎(chǔ)為《組合數(shù)學(xué)》。第二類(lèi)：通常與問(wèn)題所涉及的組合學(xué)概念無(wú)關(guān)，而對(duì)多種問(wèn)題均可使用。思路：將未解決問(wèn)題的模式轉(zhuǎn)化為一種已經(jīng)解決的問(wèn)題模式。組合數(shù)學(xué)用的較多的方法：（3）與（4）。應(yīng)該比賽99場(chǎng)。只要選擇任何方案中的某一種方法，就可以完成這件事情，并且這些方法兩兩互不相同。當(dāng)然A與B各自所含的基本事件是互相不同的。該班中的學(xué)生要么屬于A，要么屬于B，且AB＝，故＝18＋12＝30。其中英文字母共有26個(gè)，數(shù)字0～9共10個(gè)。l 集合描述：設(shè)有限集合A有m個(gè)元素，B有n個(gè)元素，且A與B不相交，記為一有序?qū)Α＃ǘ? 應(yīng)用【】仍設(shè)某班有男生18人，女生12人，現(xiàn)要求從中分別選出男女生各一名代表全班參加比賽，問(wèn)共有多少種選法？（解）（1）分兩步挑選，先選女生（12種選法），再選男生（18種選法）。（3）變量X——男生（18種取值），變量Y——女生（12種取值）?！尽繌腁地到B地有條不同的道路，從A地到C地有條不同的道路，從B地到D地有條不同的道路，從C地到D地有條不同的道路，那么，從A地經(jīng)B或C到達(dá)目的地D共有多少種不同的走法? （解）路線(xiàn)ABD：種走法（乘法法則） 路線(xiàn)ACD：種走法（乘法法則）總數(shù)：＋種走法（加法法則）23＋34＝18 排列與組合1. 3. 1 相異元素不允許重復(fù)的排列數(shù)和組合數(shù)（一） 計(jì)算公式從n個(gè)相異元素中不重復(fù)地取r個(gè)元素的排列數(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）特點(diǎn)：排列考慮順序，組合不然。（二） 模型將r個(gè)不相同的球放入n個(gè)有區(qū)別的盒子，每個(gè)盒子中的球數(shù)不加限制而且同盒的球不分次序。（二） 模型將r個(gè)有區(qū)別的球放入t個(gè)不同的盒子，每個(gè)盒子的容量有限，其中第i個(gè)盒子最多只能放入個(gè)球，求分配方案數(shù)。3，3條件：元素同時(shí)按同一方向旋轉(zhuǎn)，絕對(duì)位置變化，相對(duì)位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。條件：可以翻轉(zhuǎn)的圓排列。1. 3. 5 相異元素允許重復(fù)的組合（一） 問(wèn)題設(shè)，從S中允許重復(fù)地取r個(gè)元素構(gòu)成組合，稱(chēng)為r可重組合，其組合數(shù)記為RC(∞，r)。（五） 應(yīng)用【】不同的5個(gè)字母通過(guò)通信線(xiàn)路被傳送，每?jī)蓚€(gè)相鄰字母之間至少插入3個(gè)空格，但要求空格的總數(shù)必須等于15，問(wèn)共有多少種不同的傳送方式？（解）三步求解：（1）先排列5個(gè)字母，排列數(shù) P(5，5)＝5!。（4）總方案數(shù)： L＝5！故14不是約數(shù)，16＝也不是約數(shù)。對(duì)于恒等式的實(shí)質(zhì)揭露得更為深刻。（2） 不含元素，組合數(shù)為。（2） 右端：“將n個(gè)元素分為3堆：第三堆r個(gè)，第二堆個(gè)，第一堆個(gè)”，求組合方案數(shù)。分類(lèi)統(tǒng)計(jì)：i個(gè)紅球，r－i個(gè)藍(lán)球的選法為。選法1：①選一名太太任主席；②再選n－1人。每次摸出一個(gè)球，不放回，直至摸到白球?yàn)橹?。統(tǒng)計(jì)方法一：先選正式代表，再?gòu)娜酥羞x列席代表，總的選法為。例 ＝(a＋b)(a＋b)＝aa＋ab＋ba＋bb＝＝(a＋b)(a＋b)(a＋b)＝(aa＋ab＋ba＋bb)(a＋b)＝aaa＋aab＋aba＋abb＋baa＋bab＋bba＋b