【正文】 次序。對(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è)無窮集合，從S中取r個(gè)元素的排列數(shù)即為RP(∞，r)。不重復(fù)排列：S＝＝。1. 3. 3 不盡相異元素的全排列（一） 問題有限重復(fù)排列（或部分排列）：設(shè)（），從S中任取r個(gè)元素，求其排列數(shù)RP(n，r)。（二） 模型將r個(gè)有區(qū)別的球放入t個(gè)不同的盒子，每個(gè)盒子的容量有限，其中第i個(gè)盒子最多只能放入個(gè)球，求分配方案數(shù)。例： S＝{21，42，13，34，25}＝{1，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說明：（1）極端情形：相異元素不重復(fù)的排列強(qiáng)調(diào)的是不重復(fù)，即盒子的容量為1；（2）極端情形：相異元素允許重復(fù)的排列強(qiáng)調(diào)的是無限重復(fù)，即盒子的容量無限；（3）一般情形：不盡相異元素的排列強(qiáng)調(diào)的是有限重復(fù)，即盒子的容量有限，介于兩者之間。（三） 特例（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è)圓圈，共有多少種不同的排法？（解）稱為圓排列（相對(duì)于線排列）。條件：元素同時(shí)按同一方向旋轉(zhuǎn)，絕對(duì)位置變化，相對(duì)位置未變，即元素間的相鄰關(guān)系未變，視為同一圓排列。結(jié)論：1個(gè)圓排列對(duì)應(yīng)n個(gè)線排列。＝(n－1)!32541 25413 54132 41325 13254【】從n個(gè)相異元素中不重復(fù)地取r個(gè)圍成圓排列，求不同的排列總數(shù)CP(n，r)。（解） CP(n，r)＝ ＝（二） 項(xiàng)鏈排列【】將5個(gè)標(biāo)有不同序號(hào)的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱為項(xiàng)鏈排列。條件：可以翻轉(zhuǎn)的圓排列。即同一項(xiàng)鏈不用剪斷重穿，翻過來仍是原項(xiàng)鏈。結(jié)論：兩個(gè)圓排列對(duì)應(yīng)一個(gè)項(xiàng)鏈排列，故有24/2＝12種。（a） （b） 項(xiàng)鏈排列一般情形：從n個(gè)相異珠子中取r個(gè)的項(xiàng)鏈排列數(shù)： ＝ 允許重復(fù)的圓排列：情況復(fù)雜，參見反演公式（第四章）。1. 3. 5 相異元素允許重復(fù)的組合（一） 問題設(shè)，從S中允許重復(fù)地取r個(gè)元素構(gòu)成組合，稱為r可重組合，其組合數(shù)記為RC(∞，r)。（二） 抽象記S為。例：n＝5，r＝4： 1111，1122，1345，5555（三） 計(jì)算公式設(shè)所選r個(gè)元素為：1≤a1≤a2≤…≤ar≤n令 ， i＝1，2，…，r則 1≤b1＜b 2＜…＜br≤n＋(r－1)反之 結(jié)論：與從n＋r－1個(gè)相異元素中不重復(fù)地取r個(gè)元素的組合方案一一對(duì)應(yīng)?！? 例： n＝5，r＝4分類重復(fù)組合不重復(fù)組合元素1，2，3，4，51，2，3，5，6，7，8部分組合11111234112212452245236855555678（四） 模型將r個(gè)無區(qū)別的球放入n個(gè)不同的盒子，每個(gè)盒子的球數(shù)不受限制。（五） 應(yīng)用【】不同的5個(gè)字母通過通信線路被傳送，每兩個(gè)相鄰字母之間至少插入3個(gè)空格，但要求空格的總數(shù)必須等于15，問共有多少種不同的傳送方式？（解）三步求解：（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ù)： L＝5！120＝24001. 3. 6 不盡相異元素任取r個(gè)的組合問題（一） 問題設(shè)集合（），從S中任取r個(gè)，求其組合數(shù)RC(n，r)。（二） 組合數(shù)中間工具：組合問題的母函數(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。故14不是約數(shù)，16＝也不是約數(shù)。（3）問題轉(zhuǎn)化：求的所有組合數(shù)之和。（4）求解：構(gòu)造多項(xiàng)式P6 (x)＝(1＋x＋x2＋x3)(1＋x＋x2)(1＋x)＝1＋3x＋5x2＋6x3＋5x4＋3x5＋x6系數(shù)求和： ＝1＋3＋5＋6＋5＋3＋1＝24方法化簡：求P6(1)＝＝432＝24（5）一般規(guī)律：設(shè)正整數(shù)n分解為，則習(xí)題：18，21小結(jié)：課程任務(wù)；技巧性。 組合等式及其組合意義組合等式的證明方法：（1） 歸納法（2） 組合意義法：借助于闡明等號(hào)兩端的不同表達(dá)式實(shí)質(zhì)上是同一個(gè)組合問題的方案數(shù)（殊途同歸法），或者雖是兩個(gè)不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對(duì)應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。對(duì)于恒等式的實(shí)質(zhì)揭露得更為深刻。（3） 母函數(shù)法：利用無窮級(jí)數(shù)（包括有限時(shí)的多項(xiàng)式）證明有關(guān)組合等式。是產(chǎn)生和證明組合恒等式的普遍方法。（4） 其它方法：二項(xiàng)式展開、反演公式等【等式1】對(duì)稱關(guān)系式 組合意義：的r組合n－r組合【等式2】加法公式 （一）組合意義：的r組合，分為兩類：（1） 取出的元素中含有：組合數(shù)為。（2） 不含元素，組合數(shù)為。總數(shù)：注意：①無第三種情形；②兩類情況互不重復(fù)；③用加法法則。（二）例：從{1，2，3，4，5}中取3個(gè)的組合情況：第一類（包含元素“1”）： 123，124，125，134，135，145第二類（不包含“1”）： 234，235，245，345（三）路徑問題：等價(jià)形式組合意義：從（0，0）點(diǎn)到（m，n）點(diǎn)的路徑數(shù)等于從（0，0）點(diǎn)分別到（m，n－1）點(diǎn)和（m－1，n）點(diǎn)的路徑數(shù)之和。 【等式3】乘法公式 等式變形： 組合意義 （1） 左端：“將n個(gè)元素分為3堆：第一堆個(gè)，第二堆個(gè)，則第三堆為r個(gè)”，求組合方案數(shù)。（2） 右端：“將n個(gè)元素分為3堆：第三堆r個(gè)，第二堆個(gè)，第一堆個(gè)”，求組合方案數(shù)。（3） 兩個(gè)組合問題等價(jià)。舉例：n＝20＝5＋7＋8＝7＋8＋5，＝推廣：n個(gè)元素分為t堆，且可以若干堆個(gè)數(shù)相等n＝20＝4＋2＋5＋9＝2＋9＋4＋5，＝【等式4】C(n＋r＋1，r)＝ ＝C(n＋r，r)＋C(n＋r－1，r－1)＋C(n＋r－2，r－2)＋C(n＋r－3，r－3)＋…＋C(n，0) 或 C(n＋r＋1，r)＝ ＝ C(n＋r，n)＋C(n＋r－1，n)＋C(n＋r－2，n)＋…＋C(n，n)（一）組合意義：（二）說明：等式2的推廣。＝＝＝＝……＝＝（三）相應(yīng)的路徑問題： …………… 【等式5】Vandermonde（范德蒙）恒等式＝＝, r≤min(m，n) 組合意義 n個(gè)相異的紅球，m個(gè)相異的藍(lán)球，選r個(gè)的組合。分類統(tǒng)計(jì)：i個(gè)紅球，r－i個(gè)藍(lán)球的選法為。特例：m＝r＝， r≤n＝＝【等式6】和式公式：組合意義：n個(gè)相異元素選i個(gè)的組合兩類元素的n可重排列組合排列φ不不不不不不000000取取取取取取111111取不取不不取101001【等式7】組合意義：等式變形奇組合數(shù)＝偶組合數(shù)。啟發(fā)：存在一一對(duì)應(yīng)關(guān)系。例：n＝4奇組合aabcabdacdbcdbcd偶組合φbcbdcdabacadabcd【等式8】組合意義：從n名先生、n名太太中選出n人，其中一人擔(dān)任主席，且必須為太太，求選法數(shù)。選法1：①選一名太太任主席；②再選n－1人。選法總數(shù)為。選法2：①從n名太太中選k人；②從此k人中選一人任主席；③再從n名先生中選n－k人（1≤k≤n）。選法總數(shù)＝【等式9】設(shè)r，M都是自然數(shù)，M≥r則有 組合意義（概率問題）：設(shè)袋中有M個(gè)大小相同的球，其中白球r個(gè)，其余為黑球。每次摸出一個(gè)球，不放回，直至摸到白球?yàn)橹?。是必然事件（遲早會(huì)摸到白球），概率為1。另法：第一次摸到白球概率。第二次摸到白球，第k次才摸到白球（k＝2, 3, …, M－r＋1）【等式10】當(dāng)n≥m時(shí)，組合意義：從n人中選出m名正式代表及若干名列席代表的