1

組合分析2第8章組合分析初步8.1加法法則與乘法法則8.2基本排列組合的計數(shù)方法8.3遞推方程的求解與應用38.1加法法則和乘法法則加法法則與乘法法則應用實例4加法法則使用條件：事件A與B產(chǎn)生方式不重疊適用問題：分類選取.各方式分別計數(shù)，再相加.推廣：事件A1有n1種產(chǎn)生方式，事件A2有n2種產(chǎn)生方式，…,事件Ak

有nk

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

種.

事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A或B”有m+n種產(chǎn)生方式.5乘法法則使用條件：事件A與B產(chǎn)生方式相互獨立適用問題：分步選取.方式是連續(xù)的步驟，各步相互獨立，分別計數(shù)，然后相乘.推廣：事件A1有n1種產(chǎn)生方式，事件A2有n2種產(chǎn)生方式，…,事件Ak

有nk

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

種.

事件A有m種產(chǎn)生方式，事件B有n種產(chǎn)生方式，則“事件A與B”有mn種產(chǎn)生方式.6應用實例例1由數(shù)字1、2、3、4、5構(gòu)成3位數(shù).(1)如果各位數(shù)字都不相同，那么有多少種方法?(2)如果必須是偶數(shù)，則有多少種方法?(3)其中可以被5整除的有多少個?(4)其中比300大的有多少個?解(1)5×4×3=60.(2)個位為2,4，十位、百位各5種：2×5×5=50.(3)個位為5，十位和百位同(2)：1×5×5=25.(4)百位取3,4或5，十位和個位各5種:3×5×5=75.7應用實例解：1400=23527正因子為：2i5j7k，

0

i

3,0

j

2,0

k

1N=4×3×2=24例2求1400的不同的正因子個數(shù)88.2基本排列組合的計數(shù)方法排列組合的分類集合的排列集合的組合多重集的排列多重集的組合9排列組合的分類選取問題：設n元集合S，從S中選取r個元素.根據(jù)是否有序，是否允許重復可將該問題分為四個子類型不重復重復有序集合排列P(n,r)多重集排列無序集合組合C(n,r)多重集組合10集合的排列從n元集S中有序、不重復選取的r個元素稱為S的一個r-排列，S的所有r排列的數(shù)目記作

S

的r-環(huán)排列數(shù)=

11集合的組合從n元集S中無序、不重復選取的

r個元素稱為S的一個r組合，S的所有r

組合的數(shù)目記作應用方法：

公式代入

組合證明（一一對應）(例如定理8.7推論2)12組合公式的應用（I）解令

A={1,4,…,298}，B={2,5,…,299}

C={3,6,…,300}將方法分類：分別取自A,B,C:各

A,B,C各取1個：例1從1—300中任取3個數(shù)使得其和能被3整除有多少種方法？13解1000!=1000

999

998

…

2

1

將上面的每個因子分解，若分解式中共有

i

個5,j個2，那么min{i,j}就是0的個數(shù).1,…,1000中有

500個是2的倍數(shù)，j>500;200個是5的倍數(shù)，

40個是25的倍數(shù)（多加40個5），

8個是125的倍數(shù)（再多加8個5），

1個是625的倍數(shù)（再多加1個5）

i=200+40+8+1=249.min{i,j}=249.

例2求1000！的末尾有多少個0？14多重集S={n1

a1,n2

a2,…,

nk

ak}，0<ni

+∞(1)全排列:r=n,n1+n2+…+nk=n（占位模型）(定理8.6)證明：分步選取，先放a1,有種方法；再放a2,有種方法，...,放ak有種方法

(2)若r

ni

時，等價于每個位置都有k種選法，得kr.(定理8.5及推論)多重集的排列15多重集的組合

當r

ni

，

多重集S={n1

a1,n2

a2,…,

nk

ak

}不同的r-組合數(shù)為

(定理8.7及推論1）

證明：一個

r-組合形如

{x1

a1,x2

a2,…,

xk

ak

}，其中x1+x2+…+

xk

=r且xi≥0.

此不定方程的非負整數(shù)解個數(shù)就是組合數(shù)，對應于下述排列（插空法）

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

x1個

x2個

x3個

xk個r個1，k-1個0的全排列數(shù)為多重集排列和組合小結(jié)S的

r-排列

數(shù)N

計算方法，若r>n,則N=0若r=n,則若r<n,且對一切i=1,2,…,k有ni≧r,則N=kr若r<n,且存在某ni<r，N要具體分析計算16設多重集S={n1

a1,n2

a2,…,nk

ak}，

n1+n2+…+nk=nS的

r-組合

數(shù)N

計算方法，若r>n,則N=0若r=n,則N=1若r<n,且對一切i=1,2,…,k有

ni≧r,則若r<n,且存在某ni<r，N要具體分析計算17實例解：問題等價于從含k種不同元素的多重集中取出r個元素的問題，所以按定理有例3r個相同的球放到k個不同的盒子里，每個盒子裝球數(shù)不限，求放球方法數(shù).18實例解：先固定a

和b,中間選入7個其它字母，有種方法；然后將整組看作一個字母與其余17個全排列有18！種，例4排列26個字母，使得a與b之間恰有7個字母，求方法數(shù).19實例（續(xù)）解:(1)

(2)例5(1)10個男孩，5個女孩站成一排，若無女孩相鄰，有多少種方法？

(2)如果站成一個圓圈，又有多少種方法？20實例（續(xù)）解：相當于2n不同的球放到n個相同的盒子，每個盒子2個，放法為例6把2n個人分成n

組，每組2人，有多少分法？21實例（續(xù)）例79本不同的書，其中4本紅皮，5本白皮.(1)9本書的排列方式數(shù)有多少？

(2)若白皮書必須放在一起，那么有多少方法？

(3)若白皮書必須放在一起，紅皮書也必須放在一起，那么有多少方法？

(4)若白皮和紅皮書必須相間，有多少方法？解：

(1)9!(2)5！5！

(3)5！4！2！(4)5！4！例題：關系計數(shù)22設A為n元集，（1）A上可定義多少個不同的二元關系？其中有

(2)多少個自反的二元關系?(3)多少個對稱的二元關系?(4)多少個反對稱的二元關系?二元關系個數(shù)：自反關系個數(shù)：對稱關系個數(shù)：反對稱關系個數(shù)：例題：函數(shù)計數(shù)23設A、B分別為m元集和n元集，m和n為正整數(shù)，則從A到B有多少個函數(shù)？

(1)當m與n滿足什么條件時存在單射函數(shù)？有多少個?(2)當m與n滿足什么條件時存在雙射函數(shù)？有多少個?有nm個從A到B的函數(shù)，其中

(1)當m

n時存在單射函數(shù).單射函數(shù)有個(2)當m=n時存在雙射函數(shù).雙射函數(shù)有n!個