離散數(shù)學(xué)組合數(shù)學(xué)

離散數(shù)學(xué)組合數(shù)學(xué)第1頁(yè)，共19頁(yè)，2023年，2月20日，星期一§10.1加法法則和乘法法則加法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A或B”有

m+n

種產(chǎn)生方式.使用條件：事件A與B產(chǎn)生方式不重疊適用問(wèn)題：分類選取推廣：事件A1有p1種產(chǎn)生方式，事件A2有p2

種產(chǎn)生方式，…,事件Ak

有pk

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

種產(chǎn)生的方式.

第2頁(yè)，共19頁(yè)，2023年，2月20日，星期一乘法法則：事件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”有p1+p2+…+pk

種產(chǎn)生的方式.

乘法法則第3頁(yè)，共19頁(yè)，2023年，2月20日，星期一例1

由數(shù)字1、2、3、4、5構(gòu)成3位數(shù).(1)如果3位數(shù)的各位數(shù)字都不相同，那么有多少種方法？(2)如果這些3位數(shù)必須是偶數(shù)，則有多少種方法？(3)這些3位數(shù)中可以被5整除的有多少個(gè)？(4)這些3位數(shù)中比300大的有多少個(gè)？解:(1)

N=5

4

3=60(2)N=2

5

5=50(3)N=1

5

5=25(4)N=3

5

5=75例10.1.1：第4頁(yè)，共19頁(yè)，2023年，2月20日，星期一例設(shè)A,B,C是3個(gè)城市，從A到B有3條道路，從B到C有2條道路，從A直接到C有2條道路，問(wèn):(1)從A到C有多少種不同的方式？(2)從A到C最后又回到A有多少種不同的方式？其中經(jīng)過(guò)B的有多少種？解：

（1）

N=3

2+2=8

（2）甲->乙->丙->乙->甲3

223=36

例10.1.2：甲->乙->丙->甲3

22=12

甲->丙->乙->甲2

23=12

甲->丙->甲2

2

=4

由加法法則，總分法數(shù)是36+12+12+4=64其中經(jīng)過(guò)乙城的有64-4=60種第5頁(yè)，共19頁(yè)，2023年，2月20日，星期一§10.2排列與組合設(shè)n元集合S，從S中選取

r個(gè)元素.根據(jù)是否有序，是否允許重復(fù)可以將該問(wèn)題分為四個(gè)子類型.不重復(fù)選取重復(fù)選取有序選取集合的排列多重集的排列無(wú)序選取集合的組合多重集的組合第6頁(yè)，共19頁(yè)，2023年，2月20日，星期一7定義

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

排列的數(shù)目記作

P(n,r)，或

,當(dāng)n=r時(shí)，叫做S的全排列，簡(jiǎn)稱S的一個(gè)排列。定理10.1證明使用乘法法則當(dāng)n=r時(shí)，P(n,r)=n!集合的排列第7頁(yè)，共19頁(yè)，2023年，2月20日，星期一例

在5天內(nèi)安排3門課程的考試(1)若每天只允許考1門，有多少種方法？(2)若不限制每天考試的門數(shù)，有多少種方法？

解：

（1）

從5天中有序選取3天，不允許重復(fù)，其選法數(shù)是N==543=60

（2）每門考試都有5種獨(dú)立的選法.由乘法法則總選法數(shù)為：

N=

5

55=125例10.2.1：第8頁(yè)，共19頁(yè)，2023年，2月20日，星期一例

排列26個(gè)字母，使得在a和b之間正好有7個(gè)字母，問(wèn)有多少種排法？解：以a排頭、b排尾、中間恰含7個(gè)字母的排列有P(24,7)種.同理以b排頭、a排尾、中間恰含7個(gè)字母的排列也有P(24,7)種.剩余18個(gè)字母為全排列.N=2

18！=3624！例10.2.2：捆綁法第9頁(yè)，共19頁(yè)，2023年，2月20日，星期一定理10.2一個(gè)n元素S的環(huán)形r排列數(shù)是=n!/(r(n-r)!)

當(dāng)n=r時(shí)，S的環(huán)排列數(shù)是(n-1)!第10頁(yè)，共19頁(yè)，2023年，2月20日，星期一(1):10個(gè)男孩與5個(gè)女孩站成一排，如果沒(méi)有兩個(gè)女孩相鄰，問(wèn)有多少種方法？(2):10個(gè)男孩與5個(gè)女孩站成一個(gè)圓圈，如果沒(méi)有兩個(gè)女孩相鄰，問(wèn)有多少種方法？解（1）：男孩子為全排列，剩余11個(gè)空可以插5個(gè)女生，即11個(gè)空位有序地選5個(gè)，則（2）：男孩圍成一圈的方法為，剩余10個(gè)空插5個(gè)女生，為，則例10.2.3：插空法第11頁(yè)，共19頁(yè)，2023年，2月20日，星期一12集合的組合定義

從n元集S中無(wú)序、不重復(fù)選取的r個(gè)元素稱為S

的一個(gè)r

組合，S的所有r組合的數(shù)目記作C(n,r)或定理12.2推論設(shè)n,r為正整數(shù)，則(1)(2)(3)第12頁(yè)，共19頁(yè)，2023年，2月20日，星期一13多重集的排列（有序，可重復(fù)）證明：

對(duì)與n個(gè)元素的全排列為n!種其中同類元素之間是無(wú)序的，且有n1個(gè)a1,n2個(gè)a2,…,nk個(gè)ak，則最終的全排列為：多重集S={n1a1,n2a2,…,nkak}，0<ni

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

(2)若rni

時(shí)，每個(gè)位置都有k種選法，得kr.(3)若r>n,N=0.第13頁(yè)，共19頁(yè)，2023年，2月20日，星期一

例（1）：有10種畫冊(cè)，每種數(shù)量不限，現(xiàn)在要取3本送給3位朋友，問(wèn)有多少種方法？解：此題為求多重集的3排列數(shù)問(wèn)題，根據(jù)定義得，N=103=1000例（2）：有2面紅旗、3面黃旗一次懸掛在一根旗桿上，問(wèn)可以組成多少種不同的標(biāo)志？解：此題為求多重集的全排列數(shù)問(wèn)題，根據(jù)定義得:例10.2.4：第14頁(yè)，共19頁(yè)，2023年，2月20日，星期一多重集的組合（無(wú)序，可重復(fù)）當(dāng)r

ni

，

多重集S={n1a1,n2a2,…,nkak}的r組合數(shù)為

證明一個(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，k-1個(gè)0的全排列數(shù)為第15頁(yè)，共19頁(yè)，2023年，2月20日，星期一性質(zhì)：設(shè)n,r為正整數(shù)，則(1)當(dāng)r>n時(shí),N=0(2)當(dāng)r=n時(shí),N=1(3)當(dāng)r

ni

時(shí),(4)當(dāng)r=1時(shí),N=k推論：若r

ni

，則每個(gè)元素至少取一個(gè)的r組合數(shù)為證明：若每個(gè)元素至少取一個(gè)，則去掉k個(gè)元素，還需選取r-k個(gè)元素，即求多重集的r-k組合問(wèn)題。則第16頁(yè)，共19頁(yè)，2023年，2月20日，星期一

例：一個(gè)學(xué)生要在相繼的5天內(nèi)安排15個(gè)小時(shí)的學(xué)習(xí)時(shí)間，問(wèn)有多少種方法？如果要求每天至少學(xué)習(xí)1小時(shí)，又有多少種方法？解：將這相繼的5天記為a1、a2、a3、a4、a5,則第一種安排相當(dāng)于求多重集的15集合問(wèn)題，則根據(jù)定義得：當(dāng)每天至少選擇1小時(shí)時(shí)，即每天24小時(shí)中至少選擇一小時(shí)，則根據(jù)推論得：例10.2.5：第17頁(yè)，共19頁(yè)，2023年，2月20日，星期一

例：求x1+x2+…+xk=m的正整數(shù)解的個(gè)數(shù)？解：將xi(i=1,2,…,k)可以理解為若干個(gè)1的和，則2為兩個(gè)1的和，3為3個(gè)1的和，因xi為正整數(shù)，因此xi至少為1個(gè)1的和，則問(wèn)題轉(zhuǎn)化為求多重集