【正文】 （三） 特例（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ì)于線排列）。結(jié)論：1個(gè)圓排列對(duì)應(yīng)n個(gè)線排列。（解） CP(n，r)＝ ＝（二） 項(xiàng)鏈排列【】將5個(gè)標(biāo)有不同序號(hào)的珠子穿成一環(huán)，共有多少種不同的穿法？（解）稱為項(xiàng)鏈排列。即同一項(xiàng)鏈不用剪斷重穿，翻過來仍是原項(xiàng)鏈。（a） （b） 項(xiàng)鏈排列一般情形：從n個(gè)相異珠子中取r個(gè)的項(xiàng)鏈排列數(shù)： ＝ 允許重復(fù)的圓排列：情況復(fù)雜，參見反演公式（第四章）。（二） 抽象記S為。∴ 例： 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ù)不受限制。（2）兩個(gè)字母間各插入3個(gè)空格，將12個(gè)空格均勻地放入4個(gè)間隔內(nèi)，有1種方案。方案1：△△△▲▲ b △△△ d △△△▲ e △△△ a方案2：△△△b △△△ d △△△e △△△▲▲▲ a歸納：從4個(gè)相異元素中可重復(fù)地取3個(gè)元素的組合數(shù)。1（二） 組合數(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。（3）問題轉(zhuǎn)化：求的所有組合數(shù)之和。 組合等式及其組合意義組合等式的證明方法：（1） 歸納法（2） 組合意義法：借助于闡明等號(hào)兩端的不同表達(dá)式實(shí)質(zhì)上是同一個(gè)組合問題的方案數(shù)（殊途同歸法），或者雖是兩個(gè)不同組合問題的方案數(shù)，但二者的組合方案之間存在著一一對(duì)應(yīng)關(guān)系，因此等式兩端必須相等，從而達(dá)到證明等式成立的目的。（3） 母函數(shù)法：利用無窮級(jí)數(shù)（包括有限時(shí)的多項(xiàng)式）證明有關(guān)組合等式。（4） 其它方法：二項(xiàng)式展開、反演公式等【等式1】對(duì)稱關(guān)系式 組合意義：的r組合n－r組合【等式2】加法公式 （一）組合意義：的r組合，分為兩類：（1） 取出的元素中含有：組合數(shù)為?？倲?shù)：注意：①無第三種情形；②兩類情況互不重復(fù)；③用加法法則。 【等式3】乘法公式 等式變形： 組合意義 （1） 左端：“將n個(gè)元素分為3堆：第一堆個(gè)，第二堆個(gè)，則第三堆為r個(gè)”，求組合方案數(shù)。（3） 兩個(gè)組合問題等價(jià)。＝＝＝＝……＝＝（三）相應(yīng)的路徑問題： …………… 【等式5】Vandermonde（范德蒙）恒等式＝＝, r≤min(m，n) 組合意義 n個(gè)相異的紅球，m個(gè)相異的藍(lán)球，選r個(gè)的組合。特例：m＝r＝， r≤n＝＝【等式6】和式公式：組合意義：n個(gè)相異元素選i個(gè)的組合兩類元素的n可重排列組合排列φ不不不不不不000000取取取取取取111111取不取不不取101001【等式7】組合意義：等式變形奇組合數(shù)＝偶組合數(shù)。例：n＝4奇組合aabcabdacdbcdbcd偶組合φbcbdcdabacadabcd【等式8】組合意義：從n名先生、n名太太中選出n人，其中一人擔(dān)任主席，且必須為太太，求選法數(shù)。選法總數(shù)為。選法總數(shù)＝【等式9】設(shè)r，M都是自然數(shù)，M≥r則有 組合意義（概率問題）：設(shè)袋中有M個(gè)大小相同的球，其中白球r個(gè)，其余為黑球。是必然事件（遲早會(huì)摸到白球），概率為1。第二次摸到白球，第k次才摸到白球（k＝2, 3, …, M－r＋1）【等式10】當(dāng)n≥m時(shí)，組合意義：從n人中選出m名正式代表及若干名列席代表的選法（列席代表人數(shù)不限）。統(tǒng)計(jì)方法二：先選m＋k人（k＝0, 1, …, n－m） ，再從中選出m名正式代表，其余的k人為列席代表，有種選法。(2) 組合意義分配問題：將n個(gè)相異的球放入兩個(gè)盒子，a盒放入個(gè)，b盒放入個(gè)，同盒的球不分次序，方案數(shù)為＝即項(xiàng)的系數(shù)為組合數(shù)。排列問題：從兩種元素中選n個(gè)的排列（a選r個(gè)，b選個(gè)）（二） 一般分配問題問題：將n個(gè)相異的球放入t個(gè)盒子，要求第1個(gè)盒子放入個(gè)，第2個(gè)盒子放入個(gè)，……，第t個(gè)盒子放入個(gè)，且盒中的球無次序，求不同的分配方案數(shù)。（三） 多項(xiàng)式系數(shù)一般多項(xiàng)式系數(shù)與的關(guān)系：＝x3＋y3＋z3＋3x2y＋3xy2＋3x2z＋…＋6xyz＝x3＋ y3＋ z3＋x2y ＋xy2＋x2z＋…＋xyz＝x3＋y3＋z3＋x2y＋xy2＋x2z ＋…＋【】設(shè)n與t均為正整數(shù)，則有＝其中求和是在使的所有非負(fù)整數(shù)數(shù)列（n1,n2,…,nt）上進(jìn)行。（四） 多項(xiàng)式展開的項(xiàng)數(shù)【】展開式的項(xiàng)數(shù)等于，而這些項(xiàng)的系數(shù)之和為.（證）展開式的項(xiàng)從t種元素中取n個(gè)的n可重組合。（解）n＝3，t＝4，有RC(∞，3)＝C(4＋3－1，3)＝20（項(xiàng)）＝＋＋…＋＋…＋＋＋…＋＝＋＋＋＋3＋3＋3＋…＋3＋6abc＋6abd＋6acd＋6bcd【】的展開式中，項(xiàng)的系數(shù)。l 展開：的系數(shù)＝＝中的系數(shù)l 的系數(shù)：＝＝－36000【】求證，n≥1（證）（證明組合等式）在二項(xiàng)式中取a＝－x，b＝1＋x1＝＝＝【】今天是星期日，再過天是星期幾？（解）（求余數(shù)，同余運(yùn)算）＝＝＝等價(jià)問題：除以7的余數(shù)＝除以7的余數(shù)＝＝＝＝≡4（mod 7）另法：＝＝＝＝＝＝－3≡4（mod 7）（六） 問題請(qǐng)給出多項(xiàng)式的展開式中和兩項(xiàng)的系數(shù)（答：22680，－189/2）。（二） 變進(jìn)制表示（1）依據(jù)： n!＝(n－1)(n－1)!＋(n－1)!遞歸：n!＝(n－1)(n－1)!＋(n－2)(n－2)!＋(n－2)!＝(n－1)(n－1)!＋(n－2)(n－2)!＋(n－3)(n－3)!＋(n－3)!……＝(n－1)(n－1)!＋(n－2)(n－2)!＋…＋21!＋1!n!＝＋1n!－1＝(n－1)(n－1)!＋(n－2)(n－2)!＋…＋21!類似 －1＝9＋9＋…＋9101＋9結(jié)論：從0到n!－1的任何整數(shù)m都可唯一地表示為m＝(n－1)!＋(n－2)!＋…＋2!＋1!＝其中 （＝1，2，…，n－1）結(jié)論： m將十進(jìn)制轉(zhuǎn)換為變進(jìn)制：20＝3*3!＋1*2!＋0*1!＝(310)30＝1*4!＋1*3!＋0*2!＋0*1!＝(1100)100＝4*4!＋0*3!＋2*2!＋0*1!＝(4020)200＝(13110)，8005＝(143201)（2）的計(jì)算記 ＝an－1＋an－2＋…＋a3＋a2m247。3!＝算法：其中表示不大于x的最大整數(shù)。2!＋1（三） 序數(shù)法（1）規(guī)則設(shè)n 個(gè)元素為1，2，…，n。對(duì)應(yīng)規(guī)則：序列排列（p）＝，其中ai為排列（p）中數(shù)i＋1所在位置后面比i＋1小的數(shù)的個(gè)數(shù)，即排列（p）中從數(shù)i＋1開始向右統(tǒng)計(jì)不大于i的數(shù)的個(gè)數(shù)（2）實(shí)例1）排列數(shù)：n＝4 （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ù) (987654321) 排列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ì)。（二） 例（1）設(shè)＝3421：i＝2，j＝2，p1與p2交換得q1 q2 q3 q4 ＝4321，321逆轉(zhuǎn)得下一排列4123 。（3） 令比k大的所有數(shù)的箭頭改變方向，轉(zhuǎn)（1）。3和4不能動(dòng)時(shí)換2，依次類推。（1）設(shè)組合c1c2…cr滿足 c1＜c2＜…＜cr則 cr≤n，c