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