基本的組合計(jì)算公式

基本的組合計(jì)算公式1第1頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月第十二章基本的組合計(jì)數(shù)公式主要內(nèi)容加法法則與乘法法則排列與組合二項(xiàng)式定理與組合恒等式多項(xiàng)式定理2第2頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月12.1加法法則與乘法法則加法法則乘法法則分類(lèi)處理與分步處理3第3頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月加法法則加法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A或B”有m+n種產(chǎn)生方式.使用條件：事件A與B產(chǎn)生方式不重疊適用問(wèn)題：分類(lèi)選取推廣：事件A1有p1種產(chǎn)生方式，事件A2有p2種產(chǎn)生方式，…,事件Ak有pk

種產(chǎn)生的方式，則“事件A1或A2或…Ak”有p1+p2+…+pk

種產(chǎn)生的方式.4第4頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月乘法法則乘法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與B”有mn種產(chǎn)生方式.使用條件：事件A與B產(chǎn)生方式彼此獨(dú)立適用問(wèn)題：分步選取推廣：事件A1有p1種產(chǎn)生方式，事件A2有p2種產(chǎn)生方式，…,事件Ak有pk

種產(chǎn)生的方式，則“事件A1與A2與…Ak”有p1p2…pk

種產(chǎn)生的方式.5第5頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月分類(lèi)處理與分步處理分類(lèi)處理：對(duì)產(chǎn)生方式的集合進(jìn)行劃分，分別計(jì)數(shù)，然后使用加法法則分步處理：一種產(chǎn)生方式分解為若干獨(dú)立步驟，對(duì)每步分別進(jìn)行計(jì)數(shù)，然后使用乘法法則分類(lèi)與分步結(jié)合使用

先分類(lèi)，每類(lèi)內(nèi)部分步先分步，每步又分類(lèi)6第6頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月實(shí)例：關(guān)系計(jì)數(shù)例1設(shè)A為n元集，問(wèn)(1)A上的自反關(guān)系有多少個(gè)？(2)A上的對(duì)稱(chēng)關(guān)系有多少個(gè)？(3)A上的反對(duì)稱(chēng)關(guān)系有多少個(gè)？(4)A上的函數(shù)有多少個(gè)？其中雙射函數(shù)有多少個(gè)？.(2)考慮對(duì)稱(chēng)關(guān)系的矩陣.i行j列(i≠j)的元素rij=rji.能夠獨(dú)立選擇0或1的位置有(n2n)/2個(gè).加上主對(duì)角線(xiàn)的n個(gè)位置，總計(jì)(n2+n)/2個(gè)位置，每個(gè)位置2種選擇，根據(jù)乘法法則，構(gòu)成矩陣的方法數(shù)是(1)在自反關(guān)系矩陣中，主對(duì)角線(xiàn)元素都是1，其他位置的元素可以是1，也可以是0，有2種選擇.這種位置有n2n個(gè)，根據(jù)乘法法則，自反關(guān)系的個(gè)數(shù)7第7頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月解答(3)非主對(duì)角線(xiàn)位置分成(n2n)/2組，每組包含元素rij和rji.根據(jù)反對(duì)稱(chēng)的性質(zhì)，rij與rji的取值有以下3種可能：

rij=1,rji=0；rij=0,rji=1；rij=rji=0.所有這些位置元素的選擇方法數(shù)為.再考慮到主對(duì)角線(xiàn)元素的選取，由乘法法則總方法數(shù)為(4)設(shè)A={x1,x2,…,xn}，任何A上的函數(shù)f:AA具有下述形式：f={<x1,y1>,<x2,y2>,…,<xn,yn>}其中每個(gè)yi（i=1,2,…,n）有n種可能的選擇，根據(jù)乘法法則，有nn個(gè)不同的函數(shù).若f是雙射的，那么y1確定以后，y2只有n1種可能的取值,…,yn只有1種取值.構(gòu)成雙射函數(shù)的方法數(shù)是n(n1)(n2)…1=n!.8第8頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月A0netid(7位)hosted(24位)B10netid(14位)hostid(16位)C110netid(21位)hostid(8位)D1110(28位)E11110(27位)例2：Ipv4網(wǎng)址計(jì)數(shù)32位地址網(wǎng)絡(luò)標(biāo)識(shí)+主機(jī)標(biāo)識(shí)(1)A類(lèi)：最大網(wǎng)絡(luò)；B類(lèi)：中等網(wǎng)絡(luò)；C：小網(wǎng)絡(luò)；D：多路廣播；E：備用(2)限制條件：1111111在A(yíng)類(lèi)中的netid部分無(wú)效hostid部分不允許全0或全1

9第9頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月

netidhostidA類(lèi)：0+7位，24位B類(lèi)：10+14位，16位C類(lèi)：110+21位，8位限制條件：1111111在A(yíng)類(lèi)中的netid部分無(wú)效hostid部分不允許全0或全1A類(lèi)：netid271,hosted2242，

NA＝12716777214＝2130706178B類(lèi)：netid214,hosted2162，

NB＝1638465534＝1073709056C類(lèi)：netid221,hosted282,

NC＝2097152254＝532676608

N＝NA+NB+NC＝3737091842解答10第10頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月選取問(wèn)題：設(shè)n元集合S，從S中選取r個(gè)元素.根據(jù)是否有序,是否允許重復(fù),將該問(wèn)題分為四個(gè)子類(lèi)型不重復(fù)選取重復(fù)選取有序選取集合的排列多重集的排列無(wú)序選取集合的組合多重集的組合12.2排列與組合11第11頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月定義12.1設(shè)S為n元集，(1)從S中有序選取的r個(gè)元素稱(chēng)為S的一個(gè)r排列，S的不同r排列總數(shù)記作P(n,r),r=n的排列是S的全排列.(2)從S中無(wú)序選取的r個(gè)元素稱(chēng)為S的一個(gè)r組合，S的不同r組合總數(shù)記作C(n,r)集合的排列定理1.1

設(shè)n,r為自然數(shù)，規(guī)定0!=1，則12第12頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月下面考慮nr的情況.(1)排列的第一個(gè)元素有n種選擇的方式.排列的第二個(gè)元素有n1種選法,…,第r個(gè)元素的方式數(shù)n

r+1.根據(jù)乘法法則，總的選法數(shù)為

n(n

1)(n2)…(n

r+1)=(2)分兩步構(gòu)成r排列.首先無(wú)序地選出r個(gè)元素，然后再構(gòu)造這r個(gè)元素的全排列.無(wú)序選擇r個(gè)元素的方法數(shù)是C(n,r)；針對(duì)每種選法，能構(gòu)造r!個(gè)不同的全排列.根據(jù)乘法法則，不同的r排列數(shù)滿(mǎn)足P(n,r)=C(n,r)r!組合數(shù)C(n,r)也稱(chēng)為二項(xiàng)式系數(shù)，記作證明13第13頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月推論設(shè)n,r為正整數(shù)，則(1)C(n,r)=(2)C(n,r)=C(n,nr)(3)C(n,r)=C(n1,r1)+C(n1,r)推論例3證明C(n,r)=C(n,nr)證設(shè)S={1,2,…,n}是n元集合，對(duì)于S的任意r組合A={a1,a2,…,ar}，都存在一個(gè)S的nr組合SA與之對(duì)應(yīng).顯然不同的r組合對(duì)應(yīng)了不同的nr組合，反之也對(duì)，因此S的r組合數(shù)恰好與S的nr組合數(shù)相等.公式(3)

稱(chēng)為Pascal公式，也對(duì)應(yīng)了楊輝三角形證明方法：公式代入并化簡(jiǎn)，組合證明14第14頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月楊輝三角111121133114641510101161520515611n=0n=1n=2n=3n=4n=5n=6r=0r=1r=2r=3r=4r=5r=615第15頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月多重集的排列與組合定義12.2多重集S={n1a1,n2a2,…,nkak}，n=n1+n2+…nk表示S中元素的總數(shù).(1)從S中有序選取的r個(gè)元素稱(chēng)為多重集S的一個(gè)r排列.r=n的排列稱(chēng)為S的全排列(2)從S中無(wú)序選取的r個(gè)元素稱(chēng)作多重集S的一個(gè)r組合

注意：多重集中元素的重復(fù)度，0<ni

+∞,當(dāng)ni＝+∞，表示ai重復(fù)選取的次數(shù)沒(méi)有限制S的子集X={x1a1,x2a2,…,xkak},其中0

xi

+∞16第16頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月多重集的排列計(jì)數(shù)定理12.2設(shè)S={n1a1,n2a2,…,nk

ak}為多重集，(1)S的全排列數(shù)是(2)若r

ni，i=1,2,…,k，那么S的r排列數(shù)是kr

證明(1)有C(n,n1)種方法放a1，有C(nn1,n2)種方法放a2,…,最后有C(nn1n2…nk1,nk)方法放ak.根據(jù)乘法法則,

(2)r個(gè)位置中的每個(gè)位置都有k種選法，由乘法法則得kr

17第17頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月多重集的組合定理12.3多重集S={n1a1,n2a2,…,nkak}，0<ni

+∞當(dāng)r

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

=r,xi為非負(fù)整數(shù).這個(gè)不定方程的非負(fù)整數(shù)解對(duì)應(yīng)于下述排列1…101…101…10……01…1

x1個(gè)x2個(gè)x3個(gè)xk個(gè)r個(gè)1，k1個(gè)0的全排列數(shù)為18第18頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月例3排列26個(gè)字母，使得a與b之間恰有7個(gè)字母，求方法數(shù).解固定a和b,中間選7個(gè)字母，有2P(24,7)種方法，將它看作大字母與其余17個(gè)字母全排列有18！種，共

N=2P(24,7)18!組合計(jì)數(shù)的應(yīng)用解相當(dāng)于2n不同的球放到n個(gè)相同的盒子，每個(gè)盒子2個(gè)，放法為例4把2n個(gè)人分成n組，每組2人，有多少分法？19第19頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月解使用一一對(duì)應(yīng)的思想求解這個(gè)問(wèn)題.a1,a2,…,ak：k個(gè)不相鄰的數(shù),屬于集合{1,2,…,n}b1,b2,…,bk：k個(gè)允許相鄰的數(shù),屬于集合{1,…,n(k1)}對(duì)應(yīng)規(guī)則是

bi=ai(i1).i=1,2,…,k因此N=C(nk+1,k)例5從S={1,2,…,n}中選擇k個(gè)不相鄰的數(shù)，有多少種方法？一一對(duì)應(yīng)的技巧20第20頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月主要內(nèi)容二項(xiàng)式定理組合恒等式非降路徑問(wèn)題12.3二項(xiàng)式定理與組合恒等式21第21頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月二項(xiàng)式定理定理12.4

設(shè)n是正整數(shù)，對(duì)一切x和y

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

22第22頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月二項(xiàng)式定理的應(yīng)用解由二項(xiàng)式定理令i=13得到展開(kāi)式中x12y13的系數(shù)，即

例6求在(2x－3y)25的展開(kāi)式中x12y13的系數(shù).

23第23頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月組合恒等式：遞推式證明方法：公式代入、組合分析應(yīng)用：1式用于化簡(jiǎn)2式用于求和時(shí)消去變系數(shù)3式用于求和時(shí)拆項(xiàng)（兩項(xiàng)之和或者差），然后合并24第24頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月組合恒等式：基本求和式證明公式4.方法：二項(xiàng)式定理或者組合分析.設(shè)S={1,2,…,n}，下面計(jì)數(shù)S的所有子集.一種方法就是分類(lèi)處理，n元集合的k子集個(gè)數(shù)是根據(jù)加法法則，子集總數(shù)是另一種方法是分步處理，為構(gòu)成S的子集A，每個(gè)元素有2種選擇，根據(jù)乘法法則，子集總數(shù)是2n.25第25頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月恒等式求和:變系數(shù)和證明方法：二項(xiàng)式定理、級(jí)數(shù)求導(dǎo)其他組合恒等式代入26第26頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月證明公式627第27頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月證明公式728第28頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月恒等式:變上項(xiàng)求和證明組合分析.令S={a1,a2,…,an+1}為n+1元集合.等式右邊是S的k+1子集數(shù).考慮另一種分類(lèi)計(jì)數(shù)的方法.將所有的k+1元子集分成如下n+1類(lèi)：第1類(lèi)：含a1,剩下k個(gè)元素取自{a2,…,an+1}

第2類(lèi)：不含a1,含a2,剩下k個(gè)元素取自{a3,…,an+1}……不含a1,a2,…,an,含an+1,剩下k個(gè)元素取自空集由加法法則公式得證29第29頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月恒等式:乘積轉(zhuǎn)換式證明方法：組合分析.n元集中選取r個(gè)元素，然后在這r個(gè)元素中再選k個(gè)元素.不同的r元子集可能選出相同的k子集，例如{a,b,c,d,e}{a,b,c,d

}{b,c,d}{b,c,d,e}{b,c,d}重復(fù)度為：應(yīng)用：將變下限r(nóng)變成常數(shù)k，求和時(shí)提到和號(hào)外面.30第30頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月恒等式:積之和關(guān)系證明思路：考慮集合A={a1,a2,…,am}，B={b1,b2,…,bn}.等式右邊計(jì)數(shù)了從這兩個(gè)集合中選出r個(gè)元素的方法.將這些選法按照含有A中元素的個(gè)數(shù)k進(jìn)行分類(lèi)，k=0,1,…,r.然后使用加法法則.31第31頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月組合恒等式解題方法小結(jié)證明方法：已知恒等式帶入二項(xiàng)式定理冪級(jí)數(shù)的求導(dǎo)、積分歸納法組合分析求和方法：Pascal公式級(jí)數(shù)求和觀(guān)察和的結(jié)果，然后使用歸納法證明利用已知的公式32第32頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月非降路徑的計(jì)數(shù)(0,0)到(m,n)的非降路徑數(shù)：C(m+n,m)(a,b)到(m,n)的非降路徑數(shù)：等于(0,0)到(ma,nb)的非降路徑數(shù)(a,b)經(jīng)過(guò)(c,d)到(m,n)的非降路徑數(shù)：乘法法則(m,n)(0,0)33第33頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月從(0,0)到(n,n)不接觸對(duì)角線(xiàn)的非降路徑數(shù)NN1：從(0,0)到(n,n)下不接觸對(duì)角線(xiàn)非降路徑數(shù)N2：從(1,0)到(n,n1)下不接觸對(duì)角線(xiàn)非降路徑數(shù)N0:從(1,0)到(n,n1)的非降路徑數(shù)N3:從(1,0)到(n,n1)接觸對(duì)角線(xiàn)的非降路徑數(shù)關(guān)系:N=2N1=2N2=2[N0

N3](0,0)(1,0)(n,n-1)(n,n)限制條件的非降路徑數(shù)34第34頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月N3:從(1,0)到(n,n1)接觸對(duì)角線(xiàn)的非降路徑數(shù)N4:從(0,1)到(n,n1)無(wú)限制條件的非降路徑數(shù)關(guān)系:N3=N4

一一對(duì)應(yīng)(1,0)(0,1)(n,n-1)(0,0)(n,n)35第35頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月例7A={1,2,…,m},B={1,2,…,n}，N1:B上單調(diào)遞增函數(shù)個(gè)數(shù)是(1,1)到(n+1,n)的非降路徑數(shù)N:B上單調(diào)函數(shù)個(gè)數(shù)

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

嚴(yán)格單調(diào)遞增函數(shù)、遞減函數(shù)個(gè)數(shù)都是C(n,m)

(1,f(1))(2,f(2))(n,f(n))(n+1,n)(1,1)應(yīng)用:單調(diào)函數(shù)計(jì)數(shù)36第36頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月棧輸出的計(jì)數(shù)例8將1,2,…,n按照順序輸入棧，有多少個(gè)不同的輸出序列？分析：將進(jìn)棧、出棧分別記作x,y,出棧序列是n個(gè)x，n個(gè)y的排列，排列中任何前綴的x個(gè)數(shù)不少于y的個(gè)數(shù)，等于從(0,0)到(n,n)的不穿過(guò)對(duì)角線(xiàn)的非降路徑數(shù)37第37頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月輸入：1,

2,

3,

4,

5,輸出

：3,

2,

4,

1,

5進(jìn),進(jìn),進(jìn),出,出,進(jìn),出,出,進(jìn),出

x,x,x,y,y,x,y,y,x,y12534棧輸出的計(jì)數(shù)38第38頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月棧輸出的計(jì)數(shù)從(0,0)到(n,n)的穿過(guò)對(duì)角線(xiàn)的非降路徑從(-1,1)到(n,n)的非降路徑從(0,0)到(n,n)的非降路徑總數(shù)為C(2n,n)條，從(-1,1)到(n,n)的非降路徑數(shù)為C(2n,n-1)條，(n,n)(0,0)(-1,0)(-1,1)39第39頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月A={1,2,…,m},B={1,2,…,n}f:AB函數(shù)計(jì)數(shù)小結(jié)40第40頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月.定理12.6設(shè)n為正整數(shù)，xi為實(shí)數(shù)，i=1,2,…,t.求和是對(duì)滿(mǎn)足方程n1+n2+…+nt=n的一切非負(fù)整數(shù)解求在n個(gè)因式中選n1個(gè)因式貢獻(xiàn)x1,從剩下nn1個(gè)因式選n2個(gè)因式貢獻(xiàn)x2,…,從剩下的nn1n2…nt1個(gè)因式中選nt個(gè)因式貢獻(xiàn)xt.證明展開(kāi)式中的項(xiàng)是如下構(gòu)成的:12.4多項(xiàng)式定理41第41頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月推論推論1多項(xiàng)式展開(kāi)式中不同的項(xiàng)數(shù)為方程的非負(fù)整數(shù)解的個(gè)數(shù)C(n+t1,n)推論2

例9求(2x13x2+5x3)6中x13x2x32的系數(shù).解由多項(xiàng)式定理得42第42頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月多項(xiàng)式系數(shù)組合意義多項(xiàng)式系數(shù)多重集S={n1

a1,n2a2,…,nt

at

}的全排列數(shù)

n個(gè)不同的球放到t個(gè)不同的盒子使得第一個(gè)盒子含n1個(gè)球，第二個(gè)盒子含n2個(gè)球，…，第t個(gè)盒子含nt個(gè)球的方案數(shù)符號(hào)43第43頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月第十二章習(xí)題課主要內(nèi)容基本計(jì)數(shù)計(jì)數(shù)法則：加法法則、乘法法則計(jì)數(shù)模型：選取問(wèn)題、非降路徑問(wèn)題、方程的非負(fù)整數(shù)解問(wèn)題處理方法：分類(lèi)處理、分步處理、一一對(duì)應(yīng)思想計(jì)數(shù)符號(hào)組合數(shù)或二項(xiàng)式系數(shù)C(m,n)：組合恒等式排列數(shù)P(m,n)多項(xiàng)式系數(shù)二項(xiàng)式定理與多項(xiàng)式定理44第44頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月基本要求能夠熟練使用加法法則與乘法法則熟悉和應(yīng)用基本的組合計(jì)數(shù)模型：選取問(wèn)題不等方程的解非降路徑熟悉二項(xiàng)式定理與多項(xiàng)式定理能證明組合恒等式并對(duì)二項(xiàng)式系數(shù)進(jìn)行求和了解多項(xiàng)式系數(shù)及其相關(guān)公式45第45頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月練習(xí)1：基本的組合計(jì)數(shù)1.求1400的不同的正因子個(gè)數(shù).解1400的素因子分解式是

1400=235271400的任何正因子都具有下述形式：2i5j7k

，其中0i3,0j2,0k1.根據(jù)乘法法則，1400的正因子數(shù)是i,j,k的選法數(shù)N=(1+3)(1+2)(1+1)=24.

46第46頁(yè)，課件共52頁(yè)，創(chuàng)作于2023年2月練習(xí)2：基本的組合計(jì)數(shù)2．把10個(gè)不同的球放到6個(gè)不同的盒子里，允許空盒，且前2個(gè)盒子球的總數(shù)至多是4，問(wèn)有多少種方法？解根據(jù)前兩個(gè)盒子含球數(shù)k對(duì)放法分類(lèi)，其中k=0,1,2,3,4.對(duì)于給定的k，再分步處理計(jì)算放球的方法數(shù)：①?gòu)?0個(gè)球中選放入前兩個(gè)盒子的k個(gè)球，有C(10,k)選法；②把選好的k個(gè)球分到2個(gè)盒子里，每個(gè)球可以有2種選擇