组合-chapt2-16排列与组合.pptxVIP

组合数学

第2章排列与组合主要内容：1.基本的计数原理及其应用2.集合的排列与组合3.多重集的排列与组合

基本计数原理(P16-17)加法原理:设S=S1?…?Sm,且Si?Sj=?(i?j)则|S|=|S1|+…+|Sm|.乘法原理:设S是由(a,b)组成的集合,其中a有p种选择,且对a的每种选择,b有q种选择,则|S|=p?q.

乘法原理应用(P17)例:确定34?52?117?138的正整数因子的个数.解:其正整数因子的形式为3i?5j?11m?13n,其中0?i?4,0?j?2,

0?m?7,0?n?8.i有5种选择;对i的每种选择,j有3种选择;对j的每种选择,m有8种选择;…所以根据乘法原理,正整数因子的个数是5?3?8?9=1080.

例(P19)例.求1000~9999之间具有不同数字的奇数的个数解:1.个位有|{1,3,5,7,9}|=5种选择2.千位有|{1,…,9}|-1=8种选择3.百位有|{0,1,…,9}|-2=8种选择4.十位有|{0,1,…,9}|-3=7种选择总个数=5?8?8?7=2240.换次序:1.百位有|{0,1,…,9}|=10种选择2.个位有|{1,3,5,7,9}|-?种选择当百位是偶数时,个位有5种选择;当百位是奇数时,个位有4种选择.不能直接用乘法原理

集合与多重集的记法(P19)集合:不能重复,没有次序

{a,b,b}={a,b}多重集:可以重复,没有次序

{a,b,b}={b,a,b}?{a,b}多重集的记法:

M={a,a,a,b,c,c,d,d,d,d}:={3?a,b,2?c,4?d}

N={??a,2?b,??c,4?d}

集合的排列与组合(P21,24)令S是集合,|S|=n,r?0,S的一个r-排列是S中r个元素的有序摆放.S的一个r-组合是S中r个元素的无序选择,或者说是S的r个元素的子集.例:S={a,b,c}S的1-排列:a,b,c,1-组合:{a},{b},{c}S的2-排列:ab,ca,…,2-组合:{a,b},{b,c},{a,c}S的3-排列:cab,…,3-组合:{a,b,c}S的4-排列:?4-组合:?S的0-排列:?0-组合:?,1个

排列数与组合数(P21-27)用P(n,r)表示n元素集合的r-排列的个数用C(n,r)表示n元素集合的r-组合的个数定理1:0?r?n,P(n,r)=n!/(n-r)!(乘法原理)定理2:0?r?n,C(n,r)=n!/(n-r)!/r!(双计数)通常记C(n,r)为定理3:C(n,r)=C(n,n-r).定理4:C(n,0)+C(n,1)+…+C(n,n)=2n.

例1:平面上25个点,无3点共线,1求他们所确定的直线数和三角形数.2例2:排列26个字母,a,e,i,o,u两两不相邻,求方案数.3定义:循环排列,即沿圆圈排列.4定理:n元素集合的循环r-排列的个数是5P(n,r)/r.6例3.8个不同颜色念珠穿成一条项链,求方案数.7例4.10人围坐一圆桌,其中两个不相邻,求方案数.8与例2比较.9例(P22-25)

多重集的排列和组合(P28)特点:每个元素可以出现0到多次.例:S={2?a,b,3?c}S的4-排列有abac,cacc等S的4-组合有{2?a,b,c},{a,3?c}等S的6-排列有abccac等S的6-组合有{2?a,b,3?c}S的7-排列无,S的7-组合无.

两个简单情况(P28,32)定理1:设S={n1?a1,n2?a2,…,nk?ak},且|S|=n1+…+nk=n,则S的全排列数是?=C(n,n1)?C(n-n1,n2)?…定理2