組合數(shù)學(xué)第三章(1)

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院1第三章基本計數(shù)原理3.1加法原則與乘法原則3.2排列與組合3.3排列和組合的生成3.4二項式系數(shù)3.5集合的分劃與第二類Stirling數(shù)3.6正整數(shù)的分拆3.7分配問題2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院2加法原理(1)加法原理如果有p1種不同方法能夠從一堆物體中選擇出一個物體，有p2種不同方法能夠從另一堆物體中選擇出一個物體，那么從兩堆物體中選擇出一個物體的方法共有p1+p2種。

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院3推廣形式如果有p1種不同方法能夠從第1堆物體中選擇出一個物體，有p2種不同方法能夠第2堆物體中選擇出一個物體，…，有pn種不同方法能夠第n堆物體中選擇出一個物體，那么從這n堆物體中選擇出一個物體的方法共有p1+p2+…+pn種2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院4集合表達(dá)形式設(shè)集合，且對任意的1≤i<j≤n,有

則有|S|=|S1|+|S2|+…+|Sm|其中|S|表示集合S的元素數(shù)。

注意各子集間交集均為空2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院5加法原理例3.1.1

從100名教師和200名學(xué)生中挑選出1個代表參加會議，那么有多少種不同的挑選方法解：根據(jù)加法原理有100+200=300種不同的挑選方法。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院6加法原理例有五個學(xué)生選學(xué)英語或德語，其中有四個人學(xué)英語，三個人學(xué)德語，那么選出一名學(xué)英語或德語的學(xué)生的方法數(shù)5。上例的結(jié)果不是4+3＝7?這是因為選學(xué)英語的學(xué)生和選學(xué)德語的學(xué)生可能是同一個學(xué)生。注意：使用加法法則的時候要特別注意事件A和事件B產(chǎn)生的方式不能重疊，即一種產(chǎn)生的方式只能屬于其中的一個事件而不能同時屬于兩個事件．否則，需要使用容斥原理（第四章）。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院7(2)乘法原則如果執(zhí)行第1項任務(wù)有p1個結(jié)果，而不論第1項任務(wù)結(jié)果如何，執(zhí)行第2項任務(wù)有

p2個結(jié)果，那么，兩項任務(wù)連續(xù)執(zhí)行有

p1×p2個結(jié)果

乘法原則2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院8推廣形式如果執(zhí)行第1項任務(wù)有p1個結(jié)果，而不論第1項任務(wù)結(jié)果如何，執(zhí)行第2項任務(wù)有p2個結(jié)果，而不論第2項任務(wù)結(jié)果如何，執(zhí)行第3項任務(wù)有p3個結(jié)果，…，而不論第n-1項任務(wù)結(jié)果如何，執(zhí)行第n項任務(wù)有pn個結(jié)果，那么，所有任務(wù)連續(xù)執(zhí)行有p1×p2×…×pn個結(jié)果

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院9集合表達(dá)形式令S是n元組(a1,a2…,an)的集合，其中a1來自大小為p1的集合A1，a2來自大小為p2的集合A2，…，an來自大小為pn的集合An，而且每個ai的選擇是獨立的，則S的大小為p1×p2×…×pn

，即：∣S∣=p1×p2×…×pnn元組中各個元素的選擇是相互獨立的

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院10乘法原則例3.1.2

從100名教師和200名學(xué)生中挑選出教師和學(xué)生各1名參加會議，那么有多少種不同的挑選方法解：根據(jù)乘法原理有100×200=20000種不同的挑選方法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院11乘法原則2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院12乘法原則非01,3,5,7,9第1位第2位第3位第4位8×8×7×52024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院13

把元素的有序安排稱為排列把元素的無序安排即與順序無關(guān)的安排稱為組合集合的排列與組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院14組合計數(shù)問題類型2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院15集合的排列與組合

把沒有重復(fù)元素的排列和組合問題稱之為集合的排列與組合把有重復(fù)元素的排列和組合問題稱為多重集合的排列與組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院16相異元素不允許重復(fù)的排列數(shù)定義從含有n個元素的集合S中，有序選取的r個不重復(fù)的元素，叫做S的一個r-排列。不同排列的總數(shù)記作P(n,r)。如果r=n，則稱這個排列為S的全排列，簡稱為S的排列。r>n時，P(n,r)＝0。0?。?P(n,0)=1P(n,n)=n!2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院17相異元素不允許重復(fù)的組合數(shù)

定義 從n元集S中無序地取出r個元素，叫做S的一個r-組合。不同組合的總數(shù)記作C(n,r)。C(n,0)=1,n

0r>n時，有C(n,r)=0C(n,0)=C(n,n)=1若0

r

n，則C(n,r)=C(n,n-r)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院18(4)的組合意義

是n元集合S的r元子集的個數(shù)，是集合S的n-r元子集的個數(shù).設(shè)A是S的r元子集，則S-A是S的n-r元子集，這種對應(yīng)關(guān)系顯然是一一的。即S的r元子集的個數(shù)等于S的n-r元子集的個數(shù)

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院19集合排列組合問題抽象為分配問題

將r個有區(qū)別的小球放入n個不同的盒子，每盒不超過一個，則總的放法為P(n,r)。同樣，若小球不加以區(qū)別，則有種放法。

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院20相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院21相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院22相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院23相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院24例3.2.4把10個有區(qū)分的小球放到5個不同的盒子中，如果要求每個盒子中的小球有次序之分，求有多少種不同的放法相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院25

解：方法1分析把10個小球一一放到5個盒子中的所有情況12↑↑↑↑↑↑↑33333331↑↑↑↑↑↑222222相異元素不重復(fù)排列數(shù)和組合數(shù)12↑↑↑↑↑↑↑33333332024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院26

解：方法2分析用4個分隔符把10個小球分割成5堆的情況

**△*△***△**△**

↑↑↑↑35912相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院27相異元素不重復(fù)排列數(shù)和組合數(shù)12n-1n…2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院28在證明組合等式時不是進(jìn)行代數(shù)推導(dǎo)，而是對等式所代表的組合意義進(jìn)行分析，通過建立一一對應(yīng)的方法說明等式兩邊恰好是對同一組合模型進(jìn)行計數(shù)。這種組合分析的方法是很有用的，請看下面的例子。組合分析的方法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院29相異元素不重復(fù)排列數(shù)和組合數(shù)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院30作業(yè)pp.82,3.4,3.52024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院31相異元素不允許重復(fù)的圓排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院32定理3.2.1

一個n元集S的圓r-排列數(shù)是

P(n,r)/r=n!/r(n-r)!

如果r＝n，則S的圓排列數(shù)是(n-1)!

證明

我們把S的所有的線形r-排列分成組，使得同組的每個線形排列可以連接成同樣的圓排列。因為每組中恰含有r個線形排列，所以S的圓r-排列數(shù)

N＝p(n,r)/r，當(dāng)r＝n時，S的圓排列數(shù)為p(n,n)/n＝(n-1)!。12r-1r…2r…13………r1r-1r-2…相異元素不允許重復(fù)的圓排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院33例3.2.710個人圍坐圓桌旁聚餐，如果A和B不能相鄰，則不同的坐法有多少種？解不考慮限制條件，10個人的圓排列數(shù)為9！，考慮A和B相鄰的情況，有兩種情形A在B的左側(cè)和A在B的右側(cè)，則A和B相鄰的圓排列數(shù)為2×8！，所以不同的坐法有9！-2×8！=7×8！=282240種。相異元素不允許重復(fù)的圓排列12910…2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院34例3.2.8將5個不同顏色的珠子串成一條項鏈，能夠串成多少不同的項鏈？解 首先我們考慮5個元素的圓排列問題，根據(jù)定理3.2.1有4！=24個不同5-圓排列。但這個問題很特殊，因為項鏈可以翻轉(zhuǎn)但不影響珠子的相對位置，即每2個圓排列對應(yīng)同一個項鏈，因此能夠串成12個不同的項鏈。相異元素不允許重復(fù)的圓排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院35

排列的生成方法

(a)鄰位互換法

(b)字典序法組合的生成方法

(a)生成集合I={1,2,…,n}的所有組合

(b)生成集合I={1,2,…,n}的所有r-組合集合排列和組合的生成2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院36排列的生成全排列的生成算法就是對于給定的字符集，用有效的方法將所有可能的全排列無重復(fù)無遺漏地枚舉出來。

(a)鄰位互換法

(b)字典序法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院37鄰位互換法基本思想是遞歸地對集合{1,2,…,n-1}的(n-1)!個排列的每一個排列,通過把n插入到首、尾和任兩個數(shù)的中間共n個位置，產(chǎn)生集合{1,2,…,n}的n個排列，從而產(chǎn)生n

(n-1)!=n!個集合{1,2,…,n}的排列。

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院38鄰位互換法1221123132312321231213N=2N=3N=112024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院39鄰位互換法123412431423412341321432134213243124314234124312432134213241321423142341243142314213241321432134N=42024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院40活動整數(shù)定義：對任一給定整數(shù)k,其上加一個箭頭表示移動方向,或.對于集合{1,2,…,n}的任一個排列,其中每一個整數(shù)都有一個箭頭指出其移動方向,若整數(shù)k的箭頭指向與其相鄰但比它小的整數(shù),稱k是活動的.舉例：鄰位互換法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院41鄰位互換法算法3.1

鄰位互換法生成1,2,…,n的所有排列輸入：n輸出：{1,2,…,n}的所有n!個全排列步驟1：初始化，設(shè)，輸出P；步驟2：考慮排列P，若排列中無一處于活動狀態(tài)，則停止；步驟3：求所有處于活動狀態(tài)的數(shù)中的最大者，設(shè)為pm。pm和它的箭頭所指的一側(cè)的相鄰數(shù)互換位置，輸出P；步驟4：令比m大的所有數(shù)的箭頭改變方向，轉(zhuǎn)步驟2.

當(dāng)n=4時，算法生成各個排列的順序2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院42鄰位互換法1234124314234123413214321342132431243142341243124321342132413214231423412431423142132413214321342024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院43字典序法

對給定的字符集中的字符規(guī)定了一個先后關(guān)系，在此基礎(chǔ)上規(guī)定兩個全排列的先后是從左到右逐個比較對應(yīng)的字符的先后。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院44字典序法[例]字符集{1,2,3},較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321?！?/p>

一個全排列可看做一個字符串，字符串可有前綴、后綴。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院45字典序法高度為4的樹2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院46字典序法生成給定全排列的下一個排列所謂一個的下一個就是這一個與下一個之間沒有其他的。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院47按從樹根到樹葉讀各邊的標(biāo)號順序得一個排列，自左至右依次為

1234，1243，1324，1342，1423，1432，

2134，2143，2314，2341，2413，2431，

3124，3142，3214．3241，3412，3421，

4123，4132，4213，4231，4312，4321它是按“字典”的順序排列的，由排列P1P2…Pn生成下一個排列的算法如下：字典序法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院48字典序排列生成算法任務(wù)解析找到第一個需要交換的數(shù)的位置找到第二個需要交換的數(shù)的位置交換后處理2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院49排列字典序定義集合{1,2,…,n}上的字典序關(guān)系“<L”，對于和是集合{1,2,…,n}上的兩個排列，則從左向右掃描，當(dāng)出現(xiàn)第一個元素不同的位置（不妨設(shè)為第i個位置）時：如果則定義<L

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院50字典序排列生成算法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院51例：P1P2P3P4=3421

(a)

i=max｛j|Pj-1＜Pj}=2(b)

j=max｛k|Pi-1＜Pk}=2(c)

P1與P2互換得4321(d)4321中的321的順序逆轉(zhuǎn)得排列：

4123字典序法2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院52組合字典序定義設(shè)兩個n元組an-1an-2…a1a0和n元組bn-1bn-2…b1b0，從左至右比較兩個n元組，當(dāng)出現(xiàn)第一個元素不同的位置時，例如，第j個位置，若aj＝0,bj＝1：n元組an-1an-2…a1a0出現(xiàn)在n元組bn-1bn-2…b1b0的前面；aj＝1,bj＝0：n元組an-1an-2…a1a0出現(xiàn)在n元組bn-1bn-2…b1b0的后面；2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院53集合{1，2，3}字典序組合輸出子集元素123?000{3}001{2}010{2，3}011{1}100{1，3}101{1，2}110{1，2，3}1112024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院54生成集合I={1,2,…,n}的所有組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院55生成集合I={1,2,…,n}的所有r-組合舉例：生成集合{1，2，3，4，5，6}的所有4組合1234，1235，1236，1245，1246，1256，1345，1346，1356,14562345，2346，23562456,3456

設(shè)從[1,n]中取r元的組合全體為C(n,r).不妨設(shè)C1＜C2＜…＜Cri≤Ci≤(n－r+i),i=1,2,…,r2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院56生成集合I={1,2,…,n}的所有r-組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院57多重集

多重集中可以有重復(fù)的元素。這是對普通集合的擴(kuò)展多重集的排列，包括多重集r-排列和全排列多重集的組合，多重集r-組合例子

M表示為是一個10個元素的多重集合，其中有3個a，1個b，2個c，4個d.2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院58多重集2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院59多重集合的排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院60多重集合的排列這個問題對應(yīng)的分配問題模型是：將r個有區(qū)別的球放入n個不同的盒子中，且每個盒子的球數(shù)不加以限制，而且同盒的球不分次序，則不同的放法為nr種2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院61多重集合的排列推論設(shè)多重集 且對一切 則S的r-排列數(shù)為nr。

例

求不多于四位的二進(jìn)制數(shù)的個數(shù)。

解

這個問題相當(dāng)于多重集的4-排列問題。由定理3.2.2，所求的二進(jìn)制數(shù)的個數(shù)N＝24＝16。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院62多重集合的排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院63多重集合的排列例3.3.2使用英文字母表中26個字母構(gòu)成8個字母的單詞，且允許字母重復(fù)，如果要求

每個單詞至少含有3個元音字母，那么能構(gòu)成多少個這樣的單詞？解不考慮元音情況：有0個元音字母的單詞有有1個元音字母的單詞有有2個元音字母的單詞有根據(jù)加法原理共2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院64多重集合的排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院65多重集合的排列例3.3.3

求多重集的8-排列數(shù)分析：（1）目前已知的多重集排列公式（2）多重集的元素個數(shù)（3）每個元素的重復(fù)度均小于所求（4）構(gòu)造滿足公式所求的多重集2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院66解可分三種情況計算：

M-{a}的8-排列數(shù),即為排列數(shù)為：

M-的8-排列數(shù),即為排列數(shù)為：

M-{c}的8-排列數(shù),即為排列數(shù)為：多重集M的8-排列數(shù)為420+280+560=1260

多重集合的排列2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院67多重集合的排列例3.3.4

從4個a，4個b，4個c，4個d中選擇字母形成一個10個字母的序列，如果每個字母至少出現(xiàn)兩次，有多少種方法形成這樣的序列？分析：（1）問題描述：求多重集的10-排列數(shù)（2）要求：每個10排列中包含各個字母至少兩個。（3）目前已知的多重集排列公式（4）多重集的元素個數(shù)（5）每個元素的重復(fù)度均小于所求（6）構(gòu)造滿足公式所求的多重集2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院68（一）的10-排列數(shù);的10-排列數(shù)；的10-排列數(shù)：的10-排列數(shù)，這4種類情況的10-排列數(shù)相等，均為（二）的10-排列數(shù);的10-排列數(shù)；的10-排列數(shù)：的10-排列數(shù)；10-排列數(shù)；的10-排列數(shù)這6種類情況的10-排列數(shù)相等，均為

滿足條件的方法數(shù)為

2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院69多重集的排列問題小結(jié)2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院70多重集的組合

多重集合的r-組合是指從M中無序地選出r個元素例子

如果多重集M有n個元素(包括重復(fù)的元素)，則M的n-組合只有一個，就是M本身。如果M有n種不同元素，則M的1-組合恰有n個。2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院71多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院72多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院73多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院74多重集合的組合推論1

設(shè)多重集 且對一切i=1,2,…,n有ki＞＝r，則S的r-組合數(shù)為C(n+r-1,r)。 2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院75多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院76多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院77例3.3.5求集合S={1,2,…,n}的r-組合數(shù)，其中要求r-組合中任意兩個元素在S中都不是相鄰的。如當(dāng)n=6，r=3時，S={1,2,3,4,5,6}，{1,3,5}是滿足條件的3-組合，而{1,2,6}是不滿足條件的3-組合，因為1,2在S中是相鄰的。

多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院78分析（1）問題求普通集合的r-組合數(shù)（2）要求對于任一r-組合相鄰元素在S中不相鄰（3）問題表示：任一r-組合，不妨設(shè)為，那么就是要求

（4）關(guān)心的是選取的相鄰元素之間的關(guān)系多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院79解考慮S的任意一個r-組合，不妨設(shè)我們把1,2,…,n這n個數(shù)按從小到大的順序排成一個序列，其中我們只把標(biāo)識出來，其余數(shù)字用“……”表示。

多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院80在序列中每個ji后面用以豎線“|”標(biāo)記，則設(shè)第1個豎線前面的數(shù)字個數(shù)為x1，第1個豎線與第2個豎線間的數(shù)字個數(shù)為x2，…，第r個豎線前面的數(shù)字個數(shù)為xr+1。根據(jù)題意，因為中任意兩個數(shù)都彼此不相鄰，所以滿足：x1≥1，x2≥2，…，xr≥2，xr+1≥0，因為一共有n個數(shù)字，所以x1+x2+x3+…+xr+xr+1=n。

多重集合的組合2024/7/27計算機(jī)科學(xué)與技術(shù)學(xué)院81多重集合的組合這樣原問題要求的r-組合數(shù)就等價于方程x1+x2+…+xr+xr+1=n滿足條件x1≥1，x2≥2，…，xr≥2，xr+1≥0的整數(shù)解個數(shù)。進(jìn)行代換，令y1=x1-1，y2=x2-2，…，yr=xr-2，yr+1