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