經典課件：基本的組合計數公式

離散數學第12章基本的組合計數公式17十一月2022離散數學第12章11十一月2022前言組合數學是一個古老而又年輕的數學分支。 據傳說，大禹在4000多年前就觀察到神龜背上的幻方…...前言組合數學是一個古老而又年輕的數學分支。前言 幻方可以看作是一個3階方陣，其元素是1到9的正整數，每行、每列以及兩條對角線的和都是15。519372486前言 幻方可以看作是一個3階方陣，其元素是1到9的正整數，每前言賈憲北宋數學家（約11世紀）著有《黃帝九章細草》、《算法斅古集》斅音“笑（“古算法導引”）都已失傳。楊輝著《詳解九章算法》（1261年）中曾引賈憲的“開方作法本源”圖（即指數為正整數的二項式展開系數表，現稱“楊輝三角形”）和“增乘開方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。前言賈憲北宋數學家（約11世紀）著有前言1666年萊布尼茲所著《組合學論文》一書問世，這是組合數學的第一部專著。書中首次使用了組合論（Combinatorics）一詞。前言1666年萊布尼茲所著《組合學論文》一書問世，這前言組合數學的蓬勃發(fā)展則是在計算機問世和普遍應用之后。由于組合數學涉及面廣，內容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個統(tǒng)一而有效的理論體系。這與數學分析形成了對照。前言組合數學的蓬勃發(fā)展則是在計算機問世和普遍應用之前言組合數學經常使用的方法并不高深復雜。最主要的方法是計數時的合理分類和組合模型的轉換。但是，要學好組合數學并非易事，既需要一定的數學修養(yǎng)，也要進行相當的訓練。前言組合數學經常使用的方法并不高深復雜。最主要的方計數問題計數問題是組合數學研究的主要問題之一。西班牙數學家AbrahambenMeiribnEzra(1092～1167)和法國數學家、哲學家、天文學家LevibenGerson(1288～1344)是排列與組合領域的兩位早期研究者。另外，法國數學家BlaisePascal還發(fā)明了一種機械計算器，這種計算器非常類似于20世紀40年代在數字電子計算機發(fā)明之前使用的一種機械計算器。同時，計數技術在數學和計算機科學中是很重要的，特別是在《數據結構》、《算法分析與設計》等后續(xù)課程中有非常重要的應用。計數問題計數問題是組合數學研究的主要問題之一。西班牙

內容提要二項式定理與組合恒等式3多項式定理4加法法則與乘法法則1排列與組合2內容提要二項式定理與組合恒等式3多項式定理4加法法則與乘法

本章學習要求重點掌握一般掌握了解11加法法則和原理法則2排列組合的計算31離散概率2離散概念的計算公式及性質2二項式定理與組合恒等式計算

本章學習要求重點掌握一般掌握了解11加法法則和原理法則31組合問題的處理技巧一一對應數學歸納法上下界逼近組合問題的處理技巧一一對應一一對應與上下界逼近例1在允許移動被切割的物體的情況下，最少用多少次切割可以將333的立方體切成27個單位邊長的立方體？中間的小立方體的6個面都是切割產生的面，每次切割至多產生一個面，至少需要6次切割。存在一種切割方法恰好用6次切割。例2100個選手淘汰賽，為產生冠軍至少需要多少輪比賽？方法1：50+25+12+6+3+2+1=99方法2：比賽次數與淘汰人數之間存在一一對應，總計淘汰99人，因此至少需要99場比賽.一一對應與上下界逼近例1在允許移動被切割的物體的情況下，最12.1加法法則與乘法法則開胃食品主食飲料種類價格(元)種類價格種類價格玉米片(Co)2.15漢堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85魚排(F)3.15可樂(C)0.75啤酒(B)0.75表112.1加法法則與乘法法則開胃食品主食飲料種類價格(元)種類乘法法則如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，…，第t步有nt種不同的選擇，那么完成這項工作所有可能的選擇種數為：乘法法則如果一些工作需要t步完成，第一步有n1種不例1Melissa病毒1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來破壞計算機系統(tǒng)，通過以含惡意宏的字處理文檔為附件的電子郵件傳播。當字處理文檔被打開時，宏從用戶的地址本中找出前50個地址，并將病毒轉發(fā)給他們。用戶接收到這些被轉發(fā)的附件并將字處理文檔打開后，病毒會自動繼續(xù)轉發(fā)，不斷往復擴散。病毒非?？焖俚剞D發(fā)郵件，將被轉發(fā)的郵件臨時存儲在某個磁盤上，當磁盤占滿后，系統(tǒng)將會死鎖甚至崩潰。問經過四次轉發(fā)，共有多少個接收者？解根據Melissa病毒的擴散原理，經過四次轉發(fā)，共有50×50×50×50+50×50×50+50×50+50+1=6377551個接收者。例1Melissa病毒1990年，一種名叫Melissa例2在一幅數字圖像中，若每個像素點用8位進行編碼，問每個點有多少種不同的取值。分析用8位進行編碼可分為8個步驟：選擇第一位，選擇第二位，…，選擇第八位。每一個位有兩種選擇，故根據乘法原理，8位編碼共有2×2×2×2×2×2×2×2=28=256種取值。解每個點有256(=28)種不同的取值。例2在一幅數字圖像中，若每個像素點用8位進行編碼，問每個點有加法法則假定X1,X2,…,Xt均為集合，第i個集合Xi有ni個元素。如{X1,X2,…,Xt}為兩兩不相交的集合，則可以從X1,X2,…,Xt中選出的元素總數為：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt個元素。加法法則假定X1,X2,…,Xt均為集合，第例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六個人組成的委員會，要選出一個主席、一個秘書和一個出納員。（1）共有多少種選法？（2）若主席必須從Alice和Ben種選出，共有多少種選法？（3）若Egbert必須有職位，共有多少種選法？（4）若Dolph和Francisco都有職位，共有多少種選法？例3由Alice、Ben、Connie、Dolph、Egbe例3解（1）根據乘法法則，可能的選法種數為6×5×4=120；（2）[法一]

根據題意，確定職位可分為3個步驟：確定主席有2種選擇；主席選定后，秘書有5個人選；主席和秘書都選定后，出納有4個人選。根據乘法法則，可能的選法種數為2×5×4=40；[法二]若Alice被選為主席，共有5×4=20種方法確定其他職位；若Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據加法法則，共有20＋20=40種選法；例3解（1）根據乘法法則，可能的選法種數為6×5×4=1例3解(續(xù))(3)[法一]

將確定職位分為3步：確定Egbert的職位,有3種方法；確定余下的較高職位人選,有5個人選；確定最后一個職位的人選,有4個人選。根據乘法法則，共有3×5×4=60種選法；[法二]

根據(1)的結論，如果Egbert為主席，有20種方法確定余下的職位；若Egbert為秘書，有20種方法確定余下的職位；若Egbert為出納員，也有20種方法確定余下的職位。由于三種選法得到的集合不相交，根據加法法則，共有20＋20＋20=60種選法；例3解(續(xù))(3)[法一]將確定職位分為3步：確定Egb例3解(續(xù))（4）將給Dolph、Francisco和另一個人指定職位分為3步：

給Dolph指定職位，有3個職位可選；

給Francisco指定職位，有2個職位可選；

確定最后一個職位的人選，有4個人選。根據乘法法則，共有3×2×4=24種選法。例3解(續(xù))（4）將給Dolph、Francisco和另一12.2排列與組合Zeke、Yung、Xeno和Wilma四個候選人競選同一職位。為了使選票上人名的次序不對投票者產生影響，有必要將每一種可能的人名次序打印在選票上。會有多少種不同的選票呢？從某個集合中有序的選取若干個元素的問題，稱為排列問題。12.2排列與組合Zeke、Yung、Xeno和Wi排列問題定義12.1

（1）

從含n個不同元素的集合S中有序選取的r個元素叫做S的一個r-排列，不同的排列總數記為P(n,r)。如果r=n，則稱這個排列為S的一個全排列，簡稱為S的排列。顯然，當r>n時，P(n,r)=0。

排列問題定義12.1例1從含3個不同元素的集合S中有序選取2個元素的排列總數。解從含3個元素的不同集合S中有序選取2個元素的排列總數為6種。如果將這3個元素記為A、B和C，則6個排列為AB,AC,BA,BC,CB,CA。例1從含3個不同元素的集合S中有序選取2個元素的排列總數。定理12.1對滿足r≤n的正整數n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)定理12.1對滿足r≤n的正整數n和r有第r位第r-1位第3注意：n個不同元素的排列共有n！種，其中

注意：n個不同元素的排列共有n！種，其中例2A,B,C,D,E,F組成的排列中，（1）有多少含有DEF的子串？（2）三個字母D、E和F相連的有多少種？解(1)將DEF看成一個對象，根據定理，滿足條件的排列為A,B,C,DEF的全排列，共有4！=24種；（2）根據題意，滿足該條件的排列分為兩步：第一步確定D,E和F三個字母的全排列，有3！種排列，第二步將已排序的D,E和F看成一個整體，與A,B和C共4個元素構造出A,B,C,D,E,F的全排列，有4！種排列。又根據乘法原理，滿足條件的排列總數有3！×4！=144。例2A,B,C,D,E,F組成的排列中，例36個人圍坐在圓桌上，有多少種不同的坐法？通過轉圈得到的坐法視為同一種坐法。解6個人圍坐在圓桌上，有120種不同的坐法。AEFBDCn個人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個人中選出r個人為圓桌而坐稱為環(huán)形r-排列。例36個人圍坐在圓桌上，有多少種不同的坐法？通過轉圈得到的坐推論1含n個不同元素的集合的環(huán)形r-排列數Pc(n,r)是推論1含n個不同元素的集合的環(huán)形r-排列數Pc(n,r)是例4求滿足下列條件的排列數。(1)10個男孩和5個女孩站成一排，無兩個女孩相鄰。(2)10個男孩和5個女孩站成一圓圈，無兩個女孩相鄰.解(1)根據定理，10個男孩的全排列為10!，5個女孩插入到10個男孩形成的11個空格中的插入方法數為P(11,5)。根據乘法法則，10個男孩和5個女孩站成一排，沒有兩個女孩相鄰的排列數為：10!×P(11,5)=（10!×11!)/6!。例4求滿足下列條件的排列數。例4解（續(xù)）（2）根據定理，10個男孩站成一個圓圈的環(huán)排列數為9！，5個女孩插入到10男孩形成的10個空中的插入方法數為P(10,5)。根據乘法原理，10個男孩和5個女孩站成一個圓圈，沒有兩個女孩相鄰的排列法為：9!×P(10,5)=（9!×10!)/5!。例4解（續(xù)）（2）根據定理，10個男孩站成一個圓圈的環(huán)排組合問題定義12.1（2）從含有n個不同元素的集合S中無序選取的r個元素叫做S的一個r-組合，不同的組合總數記為C(n,r)。當n≥r=0時，規(guī)定C(n,r)=1。顯然，當r>n時，C(n,r)=0。組合問題定義12.1定理12.1（2）對滿足0<r≤n的正整數n和r有，即

證明先從n個不同元素中選出r個元素，有C(n,r)種選法，再把每一種選法選出的r個元素做全排列，有r！種排法。定理12.1（2）對滿足0<r≤n的正整數n和r有，即定理12.1（2）（續(xù)）根據乘法法則，n個元素的r排列數為：即

定理12.1（2）（續(xù)）根據乘法法則，n個元素的r排列數為：例5一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；各有13種點數，分別為A,2—10,J,Q,K。試求滿足下列條件的組合數。（1）手中持有5張牌稱為一手牌，一手牌共有多少種可能的組合？（2）一手牌中的5張都是同一花色，共有多少種可能的組合？（3）一手牌中有3張牌點數相同，另外兩張牌點數相同，共有多少種可能的組合？例5一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；例5解（1）一手牌可能的組合數等于從52張牌中選出5張的可能組合數，有C(52,5)種可能的組合；（2）選同一花色的5張牌分兩步進行：一選花色，有C(4,1)種，二在選定的花色中選5張牌，有C(13,5)種。據乘法原理，有C(4,1)×C(13,5)種；例5解（1）一手牌可能的組合數等于從52張牌中選出5張的可例5解（續(xù)）（3）該組合問題需四步完成：

一選第一個點數，有C(13,1)種；

二選第二個點數，有C(12,1)種：

三選第一點數的3張牌，有C(4,3)種；

四選第二點數的2張牌，有C(4,2)種。根據乘法法則，共有C(13,1)×C(12,1)×C(4,3)×C(4,2)=13×12×4×6=3744種選法。例5解（續(xù)）（3）該組合問題需四步完成：集合的排列定義12.1

從n元集S中有序、不重復選取的r個元素稱為S的一個r排列，S的所有r

排列的數目記作

P(n,r)定理12.1

證明使用乘法法則推論1

S的環(huán)排列數=集合的排列定義12.1從n元集S中有序、不重復集合的組合定義12.1

從n元集S中無序、不重復選取的r個元素稱為S

的一個r

組合，S的所有r組合的數目記作C(n,r)定理12.1推論2

設n,r為正整數，則(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r)集合的組合定義12.1從n元集S中無序、不重復選證明方法方法1：公式代入并化簡方法2：組合證明實例：證明

C(n,r)=C(n,nr)證設S={1,2,…,n}是n元集合，對于S的任意r-組合A={a1,a2,…,ar}，都存在一個S的nr組合SA與之對應.顯然不同的r組合對應了不同的nr組合，反之也對，因此S的r組合數恰好與S的(nr)組合數相等.C(n,r)=C(n1,r1)+C(n1,r)稱為Pascal公式，也對應了楊輝三角形，

兩種證明方法都適用.證明方法方法1：公式代入并化簡楊輝三角楊輝三角基本計數公式的應用解分類選取

A={1,4,…,298}

B={2,5,…,299}

C={3,6,…,300}分別取自A,B,C:各C(100,3)A,B,C各取1個（分步處理）：C(100,1)3

N=C(100,3)+1003=1485100例1

從1—300中任取3個數使得其和能被3整除有多少種方法？基本計數公式的應用解分類選取例1從1—300中任取3個基本計數公式的應用(續(xù))解:1000!=1000999998…21將上面的每個因子分解，若分解式中共有i個5,j個2，那么min(i,j)就是0的個數.1,…,1000中有500個是2的倍數，j>500;200個是5的倍數，40個是25的倍數（多加40個5），8個是125的倍數（再多加8個5），1個是625的倍數（再多加1個5）i=200+40+8+1=249.min(i,j)=249.例2

求1000！的末尾有多少個0？基本計數公式的應用(續(xù))解:1000!=1000基本計數公式的應用(續(xù))例3

設A為n元集，問(1)A上的自反關系有多少個？(2)A上的反自反關系有多少個？(3)A上的對稱關系有多少個？(4)A上的反對稱關系有多少個？(5)A上既不對稱也不是反對稱的關系有多少個？基本計數公式的應用(續(xù))例3設A為n元集，問多重集的排列定理12.2

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk

=n

證明：分步選取.先放a1,有C(n,n1)種方法；再放a2,有C(n

n1,n2)種方法,...,放ak,有C(nn1n2

…

nk1,nk)種方法

(2)若rni

時，每個位置都有

k種選法，得

kr.多重集的排列定理12.2多重集S={n1a1,n2a多重集的組合定理12.3

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞當r

ni,S的r組合數為N=C(k+r1,r),證明一個r組合為{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

=r,xi為非負整數.這個不定方程的非負整數解對應于下述排列1…101…101…10……01…1

x1個x2個

x3個xk個r個1，k1個0的全排列數為多重集的組合定理12.3多重集S={n1a1,n2實例例5

排列26個字母，使得a與b之間恰有7個字母，求方法數.解：設盒子的球數依次記為x1,x2,…,xn,則滿足

x1+x2+…+xn

=r，x1,x2,…,xn為非負整數

N=C(n+r1,r)

例4

r

個相同的球放到n個不同的盒子里，每個盒子球數不限，求放球方法數.解：固定a和b,中間選7個字母，有2P(24,7)種方法，將它看作大字母與其余17個字母全排列有18！種，共

N=2P(24,7)18!實例例5排列26個字母，使得a與b之間恰有7個字實例(續(xù))例6(1)10個男孩，5個女孩站成一排，若沒有女孩相鄰，有多少種方法？(2)如果站成一個圓圈，有多少種方法？解:(1)

P(10,10)P(11,5)(2)

P(10,10)P(10,5)/10解：相當于2n不同的球放到n個相同的盒子，每個盒子2個，放法為例7

把2n個人分成n

組，每組2人，有多少分法？實例(續(xù))例6(1)10個男孩，5個女孩站成一排，若沒有實例(續(xù))解使用一一對應的思想求解這個問題.a1,a2,…,ak

：k個不相鄰的數,屬于集合{1,2,…,n}b1,b2,…,bk：k個允許相鄰的數,屬于集合{1,…,n(k1)}

對應規(guī)則是

bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例8

從S={1,2,…,n}中選擇k個不相鄰的數，有多少種方法？實例(續(xù))解使用一一對應的思想求解這個問題.例8從12.3二項式定理與組合恒等式12.3.1二項式定理12.3.2組合恒等式12.3.3非降路徑問題12.3二項式定理與組合恒等式12.3.1二項式定理二項式定理定理12.4設n是正整數，對一切x和y

證明方法:數學歸納法、組合分析法.證當乘積被展開時其中的項都是下述形式：xiyni,i=0,1,2,…,n.而構成形如xiyni的項，必須從n個和(x+y)中選i個提供x，其它的ni個提供y.因此，xiyni的系數是，定理得證.

二項式定理定理12.4設n是正整數，對一切x和y二項式定理的應用例1

求在(2x－3y)25的展開式中x12y13的系數.解由二項式定理令i=13得到展開式中x12y13的系數，即

二項式定理的應用例1求在(2x－3y)25的展開式中x1組合恒等式——遞推式證明方法：公式代入、組合分析應用：1式用于化簡2式用于求和時消去變系數3式用于求和時拆項（兩項之和或者差），然后合并組合恒等式——遞推式證明方法：公式代入、組合分析組合恒等式——變下項求和證明公式4.方法：二項式定理或者組合分析.設S={1,2,…,n}，下面計數S的所有子集.

一種方法就是分類處理，n元集合的k子集個數是根據加法法則，子集總數是另一種方法是分步處理，為構成S的子集A，每個元素有2種選擇，根據乘法法則，子集總數是2n.組合恒等式——變下項求和證明公式4.方法：二項式定理或者恒等式求和——變系數和證明方法：二項式定理、級數求導其他組合恒等式代入恒等式求和——變系數和證明方法：證明公式6(二項式定理+求導)證明公式6(二項式定理+求導)證明公式7(已知恒等式代入)證明公式7(已知恒等式代入)恒等式——變上項求和證明組合分析.令S={a1,a2,…,an+1}為n+1元集合.等式右邊是S的k+1子集數.考慮另一種分類計數的方法.將所有的k+1元子集分成如下n+1類：第1類：含a1,剩下k個元素取自{a2,…,an+1}

第2類：不含a1,含a2,剩下k個元素取自{a3,…,an+1}……不含a1,a2,…,an,含an+1,剩下k個元素取自空集由加法法則公式得證恒等式——變上項求和證明組合分析.令S={a1,a恒等式——乘積轉換式證明方法：組合分析.n元集中選取

r個元素，然后在這r個元素中再選

k個元素.不同的r

元子集可能選出相同的k子集，例如{a,b,c,d,e}{a,b,c,d}{b,c,d}{b,c,d,e}{b,c,d}重復度為：應用：將變下限r變成常數k，求和時提到和號外面.恒等式——乘積轉換式證明方法：組合分析.恒等式——積之和關系證明思路：考慮集合A={a1,a2,…,am}，B={b1,b2,…,bn}.等式右邊計數了從這兩個集合中選出r個元素的方法.將這些選法按照含有A中元素的個數k進行分類，k=0,1,…,r.然后使用加法法則.恒等式——積之和關系證明思路：考慮集合A={a1,a2,…,組合恒等式解題方法小結證明方法：已知恒等式帶入二項式定理冪級數的求導、積分歸納法組合分析

求和方法：Pascal公式級數求和觀察和的結果，然后使用歸納法證明利用已知的公式組合恒等式解題方法小結證明方法：非降路徑問題基本計數模型限制條件下的非降路徑數非降路徑模型的應用證明恒等式單調函數計數棧的輸出

非降路徑問題基本計數模型基本計數模型(0,0)到(m,n)的非降路徑數：C(m+n,m)(a,b)到(m,n)的非降路徑數：等于(0,0)到(ma,nb)的非降路徑數(a,b)經過(c,d)到(m,n)的非降路徑數：乘法法則基本計數模型(0,0)到(m,n)的非降路徑數：C(m限制條件的非降路徑數從(0,0)到(n,n)不接觸對角線的非降路徑數NN1：從(0,0)到(n,n)下不接觸對角線非降路徑數N2：從(1,0)到(n,n1)下不接觸對角線非降路徑數N0:從(1,0)到(n,n1)

的非降路徑數N3:從(1,0)到(n,n1)

接觸對角線的非降路徑數關系:N=2N1=2N2=2[N0

N3]限制條件的非降路徑數從(0,0)到(n,n)不接觸對角線的非一一對應N3:從(1,0)到(n,n1)接觸對角線的非降路徑數N4:從(0,1)到(n,n1)無限制條件的非降路徑數關系:N3=N4

一一對應N3:從(1,0)到(n,n1)應用——證明恒等式例2

證明證：計數(0,0)到(m+nr,r)的非降路徑數按照k分類，再分步.(0,0)到(mk,k)路徑數，(mk,k)到(m+nr,r)的路徑數應用——證明恒等式例2證明應用——單調函數計數例3A={1,2,…,m},B={1,2,…,n}，N1:B上單調遞增函數個數是(1,1)到(n+1,n)的非降路徑數N:B上單調函數個數

N=2N1N2:A到B單調遞增函數個數是從(1,1)到(m+1,n)的非降路徑數N:A到B的單調函數個數，N=2N2

嚴格單調遞增函數、遞減函數個數都是C(n,m)

應用——單調函數計數例3A={1,2,…,m},B={1函數計數小結A={1,2,…,m},B={1,2,…,n}f:AB函數計數小結A={1,2,…,m},B=應用——棧輸出的計數例4將1,2,…,n按照順序輸入棧,有多少個不同的輸出序列？解：將進棧、出棧分別記作x,y,出棧序列是n個x，n個y的排列，排列中任何前綴的x

個數不少于y的個數.等于從(0,0)到(n,n)的不穿過對角線的非降路徑數.實例：n=5

x,x,x,y,y,x,y,y,x,y

進,進,進,出,出,進,出,出,進,出

3,2,4,1,5應用——棧輸出的計數例4將1,2,…,n按照順序輸入棧,應用——棧輸出的計數(續(xù))N:堆棧輸出個數N:(0,0)到(n,n)不穿過對角線的非降路徑數N0:(0,0)到(n,n)的非降路徑總數N1:(0,0)到(n,n)的穿過對角線的非降路徑數N2:(1,1)到(n,n)的非降路徑數.關系：N=N=N0N1,N1=N2應用——棧輸出的計數(續(xù))N:堆棧輸出個數8.4.1多項式定理8.4.2多項式系數12.4多項式定理8.4.1多項式定理12.4多項式定理多項式定理.定理12.5

設n為正整數，xi為實數，i=1,2,…,t.求和是對滿足方程n1+n2+…+nt=n的一切非負整數解求在n個因式中選n1個因式貢獻x1,從剩下nn1個因式選n2個因式貢獻x2,…,從剩下的nn1n2…nt1個因式中選nt個因式貢獻xt.證明展開式中的項是如下構成的:多項式定理.定理12.5設n為正整數，xi為實數，i推論推論1

多項式展開式中不同的項數為方程的非負整數解的個數

C(n+t1,n)推論2

例1

求(2x13x2+5x3)6中x13x2x32的系數.解由多項式定理得推論推論1多項式展開式中不同的項數為方程例1求(2多項式系數組合意義多項式系數多重集S={n1

a1,n2a2,…,nt

at}的全排列數

n個不同的球放到

t個不同的盒子使得第一個盒子含n1個球，第二個盒子含n2個球，…，第t個盒子含nt個球的方案數多項式系數組合意義多項式系數(續(xù))恒等式推論2定理12.5組合證明多項式系數(續(xù))恒等式推論2定理12.5組合證明補充計數問題的應用例17個科學工作者從事一項機密的技術研究，他們的工作室裝有電子鎖，每位科學工作者都有打開電子鎖用的“鑰匙”。為了安全起見，必須有4位在場時才能打開大門。試問該電子鎖至少應具備多少個特征？每位科學工作者的“鑰匙”至少應有多少種特征？解為了使任意3個人在場時至少缺少一個特征而打不開門，該電子鎖應具備C(7,3)=35種特征；每個科學工作者的“鑰匙”至少要有C(6,3)=20種特征。補充計數問題的應用例17個科學工作者從事一項機密的技術例2某一制造鐵盤的工廠，由于設備和技術的原因只能將生產盤子的重量控制在a克到（a+0.1）克之間?，F需要制成重量相差不超過0.005克的兩鐵盤來配制一架天平，問該工廠至少要生產多少鐵盤才能得到一對符合要求的鐵盤。例2某一制造鐵盤的工廠，由于設備和技術的原因只能將生產盤子的例2解將鐵盤按重量分類，所有a克到a+0.005克的分為第一類；a+0.005克到a+0.01克的分為一類；a+0.01克到a+0.015克的又為一類，….，最后，a+0.095克到a+0.1克為一類，共計20類，由鴿籠原理知，若該工廠生產21個鐵盤，那么就能得知有兩個鐵盤屬于同一類，因而它們之間的重量差將不超過0.005克。例2解將鐵盤按重量分類，例3Fibonacci數列假定一對新出生的兔子一個月又成熟，并且再過一個月開始生出一對小兔子。按此規(guī)律，在沒有兔子死亡的情形下，一對初生的兔子，一年可以繁殖成多少隊兔子？解因為Fn=Fn-1+Fn-2，所以根據迭代法，有F12=F11+F10=2F10+F9=3F9+2F8

=5F8+3F7=8F7+5F6=…=89F2+55F1=89+55=143。例3Fibonacci數列假定一對新出生的兔子一個月又成熟例4計算下面算法中基本操作的次數算法

輸入：s1,s2,…,sn和序列的長度。

輸出：s1,s2,…,sn，按非遞減順序排列。例4計算下面算法中基本操作的次數算法例4（續(xù)）1.selection_sorts(s,n){2.//基本情況3.if(n==1)4.return5.//找到最大的元素6.max_index=1//初始時認為s1是最大的元素7.fori=2ton8.if(si>smax_index)//比較得到較大的元素，并更新最大元素9.max_index=i10.//將最大的元素移至序列尾11.swap((sn,smax_index)12.selection_sort(s,n-1)13.}例4（續(xù)）1.selection_sorts(s,n){例4解設計算n個數排序的比較執(zhí)行次數為bn，則該算法中的比較語句的執(zhí)行次數的遞歸關系為：bn=bn-1+n–1，其初始條件為：b1=0。例4解設計算n個數排序的比較執(zhí)行次數為bn，則該算法中的比例4解（續(xù)）用迭代法求解該遞歸關系：bn=bn-1+n–1=bn-2+n–2+n-1=bn-3+n–3+n–2+n–1=…=b1+1+2+…+n–3+n–2+n–1=0+1+2+…+n–3+n–2+n–1=n(n-1)/2。例4解（續(xù)）用迭代法求解該遞歸關系：個人觀點供參考，歡迎討論個人觀點供參考，歡迎討論離散數學第12章基本的組合計數公式17十一月2022離散數學第12章11十一月2022前言組合數學是一個古老而又年輕的數學分支。 據傳說，大禹在4000多年前就觀察到神龜背上的幻方…...前言組合數學是一個古老而又年輕的數學分支。前言 幻方可以看作是一個3階方陣，其元素是1到9的正整數，每行、每列以及兩條對角線的和都是15。519372486前言 幻方可以看作是一個3階方陣，其元素是1到9的正整數，每前言賈憲北宋數學家（約11世紀）著有《黃帝九章細草》、《算法斅古集》斅音“笑（“古算法導引”）都已失傳。楊輝著《詳解九章算法》（1261年）中曾引賈憲的“開方作法本源”圖（即指數為正整數的二項式展開系數表，現稱“楊輝三角形”）和“增乘開方法”（求高次冪的正根法）。前者比帕斯卡三角形早600年，后者比霍納（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。前言賈憲北宋數學家（約11世紀）著有前言1666年萊布尼茲所著《組合學論文》一書問世，這是組合數學的第一部專著。書中首次使用了組合論（Combinatorics）一詞。前言1666年萊布尼茲所著《組合學論文》一書問世，這前言組合數學的蓬勃發(fā)展則是在計算機問世和普遍應用之后。由于組合數學涉及面廣，內容龐雜，并且仍在很快地發(fā)展著，因而還沒有一個統(tǒng)一而有效的理論體系。這與數學分析形成了對照。前言組合數學的蓬勃發(fā)展則是在計算機問世和普遍應用之前言組合數學經常使用的方法并不高深復雜。最主要的方法是計數時的合理分類和組合模型的轉換。但是，要學好組合數學并非易事，既需要一定的數學修養(yǎng)，也要進行相當的訓練。前言組合數學經常使用的方法并不高深復雜。最主要的方計數問題計數問題是組合數學研究的主要問題之一。西班牙數學家AbrahambenMeiribnEzra(1092～1167)和法國數學家、哲學家、天文學家LevibenGerson(1288～1344)是排列與組合領域的兩位早期研究者。另外，法國數學家BlaisePascal還發(fā)明了一種機械計算器，這種計算器非常類似于20世紀40年代在數字電子計算機發(fā)明之前使用的一種機械計算器。同時，計數技術在數學和計算機科學中是很重要的，特別是在《數據結構》、《算法分析與設計》等后續(xù)課程中有非常重要的應用。計數問題計數問題是組合數學研究的主要問題之一。西班牙

內容提要二項式定理與組合恒等式3多項式定理4加法法則與乘法法則1排列與組合2內容提要二項式定理與組合恒等式3多項式定理4加法法則與乘法

本章學習要求重點掌握一般掌握了解11加法法則和原理法則2排列組合的計算31離散概率2離散概念的計算公式及性質2二項式定理與組合恒等式計算

本章學習要求重點掌握一般掌握了解11加法法則和原理法則31組合問題的處理技巧一一對應數學歸納法上下界逼近組合問題的處理技巧一一對應一一對應與上下界逼近例1在允許移動被切割的物體的情況下，最少用多少次切割可以將333的立方體切成27個單位邊長的立方體？中間的小立方體的6個面都是切割產生的面，每次切割至多產生一個面，至少需要6次切割。存在一種切割方法恰好用6次切割。例2100個選手淘汰賽，為產生冠軍至少需要多少輪比賽？方法1：50+25+12+6+3+2+1=99方法2：比賽次數與淘汰人數之間存在一一對應，總計淘汰99人，因此至少需要99場比賽.一一對應與上下界逼近例1在允許移動被切割的物體的情況下，最12.1加法法則與乘法法則開胃食品主食飲料種類價格(元)種類價格種類價格玉米片(Co)2.15漢堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85魚排(F)3.15可樂(C)0.75啤酒(B)0.75表112.1加法法則與乘法法則開胃食品主食飲料種類價格(元)種類乘法法則如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，…，第t步有nt種不同的選擇，那么完成這項工作所有可能的選擇種數為：乘法法則如果一些工作需要t步完成，第一步有n1種不例1Melissa病毒1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來破壞計算機系統(tǒng)，通過以含惡意宏的字處理文檔為附件的電子郵件傳播。當字處理文檔被打開時，宏從用戶的地址本中找出前50個地址，并將病毒轉發(fā)給他們。用戶接收到這些被轉發(fā)的附件并將字處理文檔打開后，病毒會自動繼續(xù)轉發(fā)，不斷往復擴散。病毒非?？焖俚剞D發(fā)郵件，將被轉發(fā)的郵件臨時存儲在某個磁盤上，當磁盤占滿后，系統(tǒng)將會死鎖甚至崩潰。問經過四次轉發(fā)，共有多少個接收者？解根據Melissa病毒的擴散原理，經過四次轉發(fā)，共有50×50×50×50+50×50×50+50×50+50+1=6377551個接收者。例1Melissa病毒1990年，一種名叫Melissa例2在一幅數字圖像中，若每個像素點用8位進行編碼，問每個點有多少種不同的取值。分析用8位進行編碼可分為8個步驟：選擇第一位，選擇第二位，…，選擇第八位。每一個位有兩種選擇，故根據乘法原理，8位編碼共有2×2×2×2×2×2×2×2=28=256種取值。解每個點有256(=28)種不同的取值。例2在一幅數字圖像中，若每個像素點用8位進行編碼，問每個點有加法法則假定X1,X2,…,Xt均為集合，第i個集合Xi有ni個元素。如{X1,X2,…,Xt}為兩兩不相交的集合，則可以從X1,X2,…,Xt中選出的元素總數為：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt個元素。加法法則假定X1,X2,…,Xt均為集合，第例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六個人組成的委員會，要選出一個主席、一個秘書和一個出納員。（1）共有多少種選法？（2）若主席必須從Alice和Ben種選出，共有多少種選法？（3）若Egbert必須有職位，共有多少種選法？（4）若Dolph和Francisco都有職位，共有多少種選法？例3由Alice、Ben、Connie、Dolph、Egbe例3解（1）根據乘法法則，可能的選法種數為6×5×4=120；（2）[法一]

根據題意，確定職位可分為3個步驟：確定主席有2種選擇；主席選定后，秘書有5個人選；主席和秘書都選定后，出納有4個人選。根據乘法法則，可能的選法種數為2×5×4=40；[法二]若Alice被選為主席，共有5×4=20種方法確定其他職位；若Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據加法法則，共有20＋20=40種選法；例3解（1）根據乘法法則，可能的選法種數為6×5×4=1例3解(續(xù))(3)[法一]

將確定職位分為3步：確定Egbert的職位,有3種方法；確定余下的較高職位人選,有5個人選；確定最后一個職位的人選,有4個人選。根據乘法法則，共有3×5×4=60種選法；[法二]

根據(1)的結論，如果Egbert為主席，有20種方法確定余下的職位；若Egbert為秘書，有20種方法確定余下的職位；若Egbert為出納員，也有20種方法確定余下的職位。由于三種選法得到的集合不相交，根據加法法則，共有20＋20＋20=60種選法；例3解(續(xù))(3)[法一]將確定職位分為3步：確定Egb例3解(續(xù))（4）將給Dolph、Francisco和另一個人指定職位分為3步：

給Dolph指定職位，有3個職位可選；

給Francisco指定職位，有2個職位可選；

確定最后一個職位的人選，有4個人選。根據乘法法則，共有3×2×4=24種選法。例3解(續(xù))（4）將給Dolph、Francisco和另一12.2排列與組合Zeke、Yung、Xeno和Wilma四個候選人競選同一職位。為了使選票上人名的次序不對投票者產生影響，有必要將每一種可能的人名次序打印在選票上。會有多少種不同的選票呢？從某個集合中有序的選取若干個元素的問題，稱為排列問題。12.2排列與組合Zeke、Yung、Xeno和Wi排列問題定義12.1

（1）

從含n個不同元素的集合S中有序選取的r個元素叫做S的一個r-排列，不同的排列總數記為P(n,r)。如果r=n，則稱這個排列為S的一個全排列，簡稱為S的排列。顯然，當r>n時，P(n,r)=0。

排列問題定義12.1例1從含3個不同元素的集合S中有序選取2個元素的排列總數。解從含3個元素的不同集合S中有序選取2個元素的排列總數為6種。如果將這3個元素記為A、B和C，則6個排列為AB,AC,BA,BC,CB,CA。例1從含3個不同元素的集合S中有序選取2個元素的排列總數。定理12.1對滿足r≤n的正整數n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)n-(r-1)定理12.1對滿足r≤n的正整數n和r有第r位第r-1位第3注意：n個不同元素的排列共有n！種，其中

注意：n個不同元素的排列共有n！種，其中例2A,B,C,D,E,F組成的排列中，（1）有多少含有DEF的子串？（2）三個字母D、E和F相連的有多少種？解(1)將DEF看成一個對象，根據定理，滿足條件的排列為A,B,C,DEF的全排列，共有4！=24種；（2）根據題意，滿足該條件的排列分為兩步：第一步確定D,E和F三個字母的全排列，有3！種排列，第二步將已排序的D,E和F看成一個整體，與A,B和C共4個元素構造出A,B,C,D,E,F的全排列，有4！種排列。又根據乘法原理，滿足條件的排列總數有3！×4！=144。例2A,B,C,D,E,F組成的排列中，例36個人圍坐在圓桌上，有多少種不同的坐法？通過轉圈得到的坐法視為同一種坐法。解6個人圍坐在圓桌上，有120種不同的坐法。AEFBDCn個人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個人中選出r個人為圓桌而坐稱為環(huán)形r-排列。例36個人圍坐在圓桌上，有多少種不同的坐法？通過轉圈得到的坐推論1含n個不同元素的集合的環(huán)形r-排列數Pc(n,r)是推論1含n個不同元素的集合的環(huán)形r-排列數Pc(n,r)是例4求滿足下列條件的排列數。(1)10個男孩和5個女孩站成一排，無兩個女孩相鄰。(2)10個男孩和5個女孩站成一圓圈，無兩個女孩相鄰.解(1)根據定理，10個男孩的全排列為10!，5個女孩插入到10個男孩形成的11個空格中的插入方法數為P(11,5)。根據乘法法則，10個男孩和5個女孩站成一排，沒有兩個女孩相鄰的排列數為：10!×P(11,5)=（10!×11!)/6!。例4求滿足下列條件的排列數。例4解（續(xù)）（2）根據定理，10個男孩站成一個圓圈的環(huán)排列數為9！，5個女孩插入到10男孩形成的10個空中的插入方法數為P(10,5)。根據乘法原理，10個男孩和5個女孩站成一個圓圈，沒有兩個女孩相鄰的排列法為：9!×P(10,5)=（9!×10!)/5!。例4解（續(xù)）（2）根據定理，10個男孩站成一個圓圈的環(huán)排組合問題定義12.1（2）從含有n個不同元素的集合S中無序選取的r個元素叫做S的一個r-組合，不同的組合總數記為C(n,r)。當n≥r=0時，規(guī)定C(n,r)=1。顯然，當r>n時，C(n,r)=0。組合問題定義12.1定理12.1（2）對滿足0<r≤n的正整數n和r有，即

證明先從n個不同元素中選出r個元素，有C(n,r)種選法，再把每一種選法選出的r個元素做全排列，有r！種排法。定理12.1（2）對滿足0<r≤n的正整數n和r有，即定理12.1（2）（續(xù)）根據乘法法則，n個元素的r排列數為：即

定理12.1（2）（續(xù)）根據乘法法則，n個元素的r排列數為：例5一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；各有13種點數，分別為A,2—10,J,Q,K。試求滿足下列條件的組合數。（1）手中持有5張牌稱為一手牌，一手牌共有多少種可能的組合？（2）一手牌中的5張都是同一花色，共有多少種可能的組合？（3）一手牌中有3張牌點數相同，另外兩張牌點數相同，共有多少種可能的組合？例5一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；例5解（1）一手牌可能的組合數等于從52張牌中選出5張的可能組合數，有C(52,5)種可能的組合；（2）選同一花色的5張牌分兩步進行：一選花色，有C(4,1)種，二在選定的花色中選5張牌，有C(13,5)種。據乘法原理，有C(4,1)×C(13,5)種；例5解（1）一手牌可能的組合數等于從52張牌中選出5張的可例5解（續(xù)）（3）該組合問題需四步完成：

一選第一個點數，有C(13,1)種；

二選第二個點數，有C(12,1)種：

三選第一點數的3張牌，有C(4,3)種；

四選第二點數的2張牌，有C(4,2)種。根據乘法法則，共有C(13,1)×C(12,1)×C(4,3)×C(4,2)=13×12×4×6=3744種選法。例5解（續(xù)）（3）該組合問題需四步完成：集合的排列定義12.1

從n元集S中有序、不重復選取的r個元素稱為S的一個r排列，S的所有r

排列的數目記作

P(n,r)定理12.1

證明使用乘法法則推論1

S的環(huán)排列數=集合的排列定義12.1從n元集S中有序、不重復集合的組合定義12.1

從n元集S中無序、不重復選取的r個元素稱為S

的一個r

組合，S的所有r組合的數目記作C(n,r)定理12.1推論2

設n,r為正整數，則(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r)集合的組合定義12.1從n元集S中無序、不重復選證明方法方法1：公式代入并化簡方法2：組合證明實例：證明

C(n,r)=C(n,nr)證設S={1,2,…,n}是n元集合，對于S的任意r-組合A={a1,a2,…,ar}，都存在一個S的nr組合SA與之對應.顯然不同的r組合對應了不同的nr組合，反之也對，因此S的r組合數恰好與S的(nr)組合數相等.C(n,r)=C(n1,r1)+C(n1,r)稱為Pascal公式，也對應了楊輝三角形，

兩種證明方法都適用.證明方法方法1：公式代入并化簡楊輝三角楊輝三角基本計數公式的應用解分類選取

A={1,4,…,298}

B={2,5,…,299}

C={3,6,…,300}分別取自A,B,C:各C(100,3)A,B,C各取1個（分步處理）：C(100,1)3

N=C(100,3)+1003=1485100例1

從1—300中任取3個數使得其和能被3整除有多少種方法？基本計數公式的應用解分類選取例1從1—300中任取3個基本計數公式的應用(續(xù))解:1000!=1000999998…21將上面的每個因子分解，若分解式中共有i個5,j個2，那么min(i,j)就是0的個數.1,…,1000中有500個是2的倍數，j>500;200個是5的倍數，40個是25的倍數（多加40個5），8個是125的倍數（再多加8個5），1個是625的倍數（再多加1個5）i=200+40+8+1=249.min(i,j)=249.例2

求1000！的末尾有多少個0？基本計數公式的應用(續(xù))解:1000!=1000基本計數公式的應用(續(xù))例3

設A為n元集，問(1)A上的自反關系有多少個？(2)A上的反自反關系有多少個？(3)A上的對稱關系有多少個？(4)A上的反對稱關系有多少個？(5)A上既不對稱也不是反對稱的關系有多少個？基本計數公式的應用(續(xù))例3設A為n元集，問多重集的排列定理12.2

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞(1)全排列r=n,n1+n2+…+nk

=n

證明：分步選取.先放a1,有C(n,n1)種方法；再放a2,有C(n

n1,n2)種方法,...,放ak,有C(nn1n2

…

nk1,nk)種方法

(2)若rni

時，每個位置都有

k種選法，得

kr.多重集的排列定理12.2多重集S={n1a1,n2a多重集的組合定理12.3

多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞當r

ni,S的r組合數為N=C(k+r1,r),證明一個r組合為{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

=r,xi為非負整數.這個不定方程的非負整數解對應于下述排列1…101…101…10……01…1

x1個x2個

x3個xk個r個1，k1個0的全排列數為多重集的組合定理12.3多重集S={n1a1,n2實例例5

排列26個字母，使得a與b之間恰有7個字母，求方法數.解：設盒子的球數依次記為x1,x2,…,xn,則滿足

x1+x2+…+xn

=r，x1,x2,…,xn為非負整數

N=C(n+r1,r)

例4

r

個相同的球放到n個不同的盒子里，每個盒子球數不限，求放球方法數.解：固定a和b,中間選7個字母，有2P(24,7)種方法，將它看作大字母與其余17個字母全排列有18！種，共

N=2P(24,7)18!實例例5排列26個字母，使得a與b之間恰有7個字實例(續(xù))例6(1)10個男孩，5個女孩站成一排，若沒有女孩相鄰，有多少種方法？(2)如果站成一個圓圈，有多少種方法？解:(1)

P(10,10)P(11,5)(2)

P(10,10)P(10,5)/10解：相當于2n不同的球放到n個相同的盒子，每個盒子2個，放法為例7

把2n個人分成n

組，每組2人，有多少分法？實例(續(xù))例6(1)10個男孩，5個女孩站成一排，若沒有實例(續(xù))解使用一一對應的思想求解這個問題.a1,a2,…,ak

：k個不相鄰的數,屬于集合{1,2,…,n}b1,b2,…,bk：k個允許相鄰的數,屬于集合{1,…,n(k1)}

對應規(guī)則是

bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例8

從S={1,2,…,n}中選擇k個不相鄰的數，有多少種方法？實例(續(xù))解使用一一對應的思想求解這個問題.例8從12.3二項式定理與組合恒等式12.3.1二項式定理12.3.2組合恒等式12.3.3非降路徑問題12.3二項式定理與組合恒等式12.3.1二項式定理二項式定理定理12.4設n是正整數，對一切x和y

證明方法:數學歸納法、組合分析法.