组合_chapt2_16排列与组合.ppt

《组合_chapt2_16排列与组合.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、组合数学第2章排列与组合主要内容：1.基本的计数原理及其应用2.集合的排列与组合3.多重集的排列与组合基本计数原理(P16-17)加法原理:设S=S1…Sm,且SiSj=(ij)则

2、S

3、=

4、S1

5、+…+

6、Sm

7、.乘法原理:设S是由(a,b)组成的集合,其中a有p种选择,且对a的每种选择,b有q种选择,则

8、S

9、=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种选择;…所以根据

10、乘法原理,正整数因子的个数是5389=1080.例(P19)例.求1000~9999之间具有不同数字的奇数的个数解:1.个位有

11、{1,3,5,7,9}

12、=5种选择2.千位有

13、{1,…,9}

14、-1=8种选择3.百位有

15、{0,1,…,9}

16、-2=8种选择4.十位有

17、{0,1,…,9}

18、-3=7种选择总个数=5887=2240.换次序:1.百位有

19、{0,1,…,9}

20、=10种选择2.个位有

21、{1,3,5,7,9}

22、-?种选择当百位是偶数时,个位有5种选择;当百位是奇数时,个位有4种选择.不能直接用乘法原理集合与多重集的记法(P19)集合:不能重复,没有次序{a,b,b}={a,b}多重集

23、:可以重复,没有次序{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是集合,

24、S

25、=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-组

26、合:?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.例(P22-25)例1:平面上25个点,无3点共线,求他们所确定的直线数和三角形数.例2:排列26个字母,a,e,i,o,u两两不相邻,求方案数.定义:循环排列,即沿圆圈排列.定理:n元素集

27、合的循环r-排列的个数是P(n,r)/r.例3.8个不同颜色念珠穿成一条项链,求方案数.例4.10人围坐一圆桌,其中两个不相邻,求方案数.与例2比较.多重集的排列和组合(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},且

28、S

29、=n1+…+nk=n,则S的全排列数是=C(n,n1)C(n-n1,n2)…定理

30、2:设S={a1,a2,…,ak},r0,则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={3a,2b,4c},求S的8排列的个数.例3.一面包房生产8种炸面包圈,若一打面包一盒,求不同盒数.例4.不定方程x1+x2+x3+x4=20,其中x13,x21,x3

31、0,x45,求其整数解的数目.本章小结与作业集合:排列组合容易多重集:无个数限制的排列组合容易有限多重集的全排列容易有限多重集的部分排列组合困难作业:第2章P37:ex5,11,27,32,37,51.编程题:crazyteaparty作业P37:ex5.确定作为下列各数的因子的10的最大幂(等价于用通常的10进制表示时尾部0的个数)：(a)50!,(b)1000!ex11.从数集{1,2,…