组合_chapt2_16排列与组合.ppt

组合数学第2章排列与组合,主要内容：1.基本的计数原理及其应用2.集合的排列与组合3.多重集的排列与组合,基本计数原理(P16-17),加法原理:设S=S1Sm,且SiSj=(ij)则|S|=|S1|+|Sm|.乘法原理:设S是由(a,b)组成的集合,其中a有p种选择,且对a的每种选择,b有q种选择,则|S|=pq.,乘法原理应用(P17),例:确定3452117138的正整数因子的个数.解:其正整数因子的形式为3i5j11m13n,其中0i4,0j2,0m7,0n8.i有5种选择;对i的每种选择,j有3种选择;对j的每种选择,m有8种选择;所以根据乘法原理,正整数因子的个数是5389=1080.,例(P19),例.求10009999之间具有不同数字的奇数的个数解:1.个位有|1,3,5,7,9|=5种选择2.千位有|1,9|-1=8种选择3.百位有|0,1,9|-2=8种选择4.十位有|0,1,9|-3=7种选择总个数=5887=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,ba,b多重集的记法:M=a,a,a,b,c,c,d,d,d,d:=3a,b,2c,4dN=a,2b,c,4d,集合的排列与组合(P21,24),令S是集合,|S|=n,r0,S的一个r-排列是S中r个元素的有序摆放.S的一个r-组合是S中r个元素的无序选择,或者说是S的r个元素的子集.,例:S=a,b,cS的1-排列:a,b,c,1-组合:a,b,cS的2-排列:ab,ca,2-组合:a,b,b,c,a,cS的3-排列:cab,3-组合:a,b,cS的4-排列:?4-组合:?S的0-排列:?0-组合:,1个,排列数与组合数(P21-27),用P(n,r)表示n元素集合的r-排列的个数用C(n,r)表示n元素集合的r-组合的个数定理1:0rn,P(n,r)=n!/(n-r)!(乘法原理)定理2:0rn,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.,例(P22-25),例1:平面上25个点,无3点共线,求他们所确定的直线数和三角形数.例2:排列26个字母,a,e,i,o,u两两不相邻,求方案数.定义:循环排列,即沿圆圈排列.定理:n元素集合的循环r-排列的个数是P(n,r)/r.例3.8个不同颜色念珠穿成一条项链,求方案数.例4.10人围坐一圆桌,其中两个不相邻,求方案数.与例2比较.,多重集的排列和组合(P28),特点:每个元素可以出现0到多次.例:S=2a,b,3cS的4-排列有abac,cacc等S的4-组合有2a,b,c,a,3c等S的6-排列有abccac等S的6-组合有2a,b,3cS的7-排列无,S的7-组合无.,两个简单情况(P28,32),定理1:设S=n1a1,n2a2,nkak,且|S|=n1+nk=n,则S的全排列数是=C(n,n1)C(n-n1,n2)定理2:设S=a1,a2,ak,r0,则S的r-排列个数是kr,S的r-组合个数是C(r+k-1,r).r-排列:等价于r个位置,每个位置k种选择r-组合数依次等价于1.不定方程x1+x2+xk=r的非负整数解个数2.将r个相同球放入k个不同盒子的方案数3.将r个相同球(0)与k-1个相同间隔(1)全排列的方案数,例(P29,31,34),例1.求MISSISSIPPI中字母的排列数.例2.S=3a,2b,4c,求S的8排列的个数.例3.一面包房生产8种炸面包圈,若一打面包一盒,求不同盒数.例4.不定方程x1+x2+x3+x4=20,其中x13,x21,x30,x45,求其整数解的数目.,本章小结与作业,集合:排列组合容易多重集:无个数限制的排列组合容易有限多重集的全排列容易有限多重集的部分排列组合困难作业:第2章P37:ex5,11,27,32,37,51.编程题:crazyteaparty,作业,P37:ex5.确定作为下列各数的因子的10的最大幂(等价于用通常的10进制表示时尾部0的个数)：(a)50!,(b)1000!ex11.从数集1,2,20中形成3个数的集合，如果没有2个相连的数字在同一个集合中，那么能形成多少个3个数的集合。ex27.5个没有区别的车放在88棋盘上，使得没有车能够攻击别的车并且第一行和第一列都不空的放置方式有多少？ex32.确定下面的多重集合的11排列的数目：S=3a,4b,5c。ex37.一家面包店销售6种不同类型的酥