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

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

m+n

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

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

有pk

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

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

第2頁，共19頁，2023年，2月20日，星期一乘法法則：事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與B”有

mn種產(chǎn)生方式.使用條件：事件A與B產(chǎn)生方式彼此獨立適用問題：分步選取推廣：事件A1有p1種產(chǎn)生方式，事件A2有p2

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

有pk

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

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

乘法法則第3頁，共19頁，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整除的有多少個？(4)這些3位數(shù)中比300大的有多少個？解:(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頁，共19頁，2023年，2月20日，星期一例設(shè)A,B,C是3個城市，從A到B有3條道路，從B到C有2條道路，從A直接到C有2條道路，問:(1)從A到C有多少種不同的方式？(2)從A到C最后又回到A有多少種不同的方式？其中經(jīng)過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)過乙城的有64-4=60種第5頁，共19頁，2023年，2月20日，星期一§10.2排列與組合設(shè)n元集合S，從S中選取

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

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

排列的數(shù)目記作

P(n,r)，或

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

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

解：

（1）

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

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

N=

5

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

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

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

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

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

的一個r

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

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

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

(2)若rni

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

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

ni

，

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

證明一個

r組合為{x1a1,x2a2,…,xkak}，其中

x1+x2+…+xk

=r,xi為非負整數(shù).這個不定方程的非負整數(shù)解對應(yīng)于下述排列

1…101…101…10……01…1

x1個

x2個

x3個

xk個r個1，k-1個0的全排列數(shù)為第15頁，共19頁，2023年，2月20日，星期一性質(zhì)：設(shè)n,r為正整數(shù)，則(1)當r>n時,N=0(2)當r=n時,N=1(3)當r

ni

時,(4)當r=1時,N=k推論：若r

ni

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

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

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