组合数学习题.pptx

《组合数学习题.pptx》由会员分享，可在线阅读，更多相关《组合数学习题.pptx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1.2 排列 解 这是全排列问题.(1)所有就坐方式为:P(10,10)=10!所以由乘法规则得所求奇数个数为 5887=2240个.4.10个人围园桌而坐,若两人不愿坐在一起,问有多少种就坐方式?若10人是5男5女且交替就坐,有多少种就坐方式?(2)所有就坐方式为:P(10,10)-2P(9,9)=89!解 这显然是园排列问题.3.10个人坐在一排看戏有多少种就坐方式?如果其中有两个人不愿坐在一起,又有多种就坐方式?(1)所有就坐方式为:10!/10-29!/9=9!-28!=78!.(2)先让5男围围桌就坐有 5!/5=4!=24;再让5女人就坐共有 5!=120;故由乘法规则得5男5女

2、交替就坐方式数为 24120=2880.第1页/共11页 1.2 排列 解 (1)先计算不含数字1的个数.不考虑10,000,000,000本身,把任何一个小于该数的不含1的正整数看作10位数,但全是0除外.相当于从0,2,3,9 9个数中选取,共有10个位置,故共有 910-1个.(2)含1的数共有 1010-(910-1)+1 个.5.在1和10,000,000,000之间的一百亿个数中,有多少个数含有数字1?又有多少个数不含数字1?6.单词“MISSISSIPPI”中的字母有多少种不同的排列方法？如果两个S不相邻，又有多少种排列方法？解 这是可重全排列问题.(1)这相当于重集B=1M,4

3、I,4S,2P的全排列,故全排列数为第2页/共11页 1.2 排列7.有多少种方法把字母a,a,a,a,b,c,d,e排成无两a相邻？(2)先对重集B=1M,4I,2P的做全排列,故全排列数为然后将4个S插入8个位置当中共有 C(8,4)=140种,故由乘法规则得排列数为 8.8个盒子排成一列，5个有标志的球放到盒子里，每个盒子最多放一个球，要求空盒不相邻，问有多少种排列方案?解 先让b,c,d,e做全排列共有4!=24种,再让4个a插入5个间隔中共有C(5,4)=5,故由乘法规则得所求排列数为245=120(种).解 如果_O_O_O_O_O_,3个空盒可插在两个球之间,共有C(6,3)=2

4、0种,又5个有标志的球共有 5!=120种排法,故由乘法规则得所求排列数为 20120=24 0(种).第3页/共11页 1.3 组合 1 1.空间中有3030个点,这3030个点无四个点共面,问它们能确定多少三角形?能确定多少四面体?解 由于任意三点可确定一个三角形,故有C(30,3)=4060个.2.从整数1,2,1000中选取三个数使得它们的和是4的倍数,求这样的选法有多少种?解 依据余数分别为0,1,2,3把1000个数的集合分成四个子集B,C,D,E,且各为250个数.又由于无四点共面每四点可确定唯一一个四面体,故有 C(30,4)=22405个.(1)从同一集合中选三个数只有B符合

5、,有C(250,3)种;(2)从两个集合中选三个数,C或E中选2个数,D中选1个数,或B中1个,D中2个共有3C(250,2)C(250,1)种;(3)从三个集合中各选1个数,从B,C和E中各选三个数,有故由加法规则得符合条件的选法共有C(250,1)C(250,1)C(250,1)=2503种;C(250,3)+3C(250,2)C(250,1)+2503第4页/共11页 1.3 组合代入原方程得3.求方程 的正整数解的个数.4.有纪念章4枚,纪念册6本,分送给10位同学,问有多少种分法?如果限制每人得一件物品,则又有多少种分法?解 令 即上式的非负整数解的个数等于原方程的正整数解的个数,故

6、原方程正整数解的个数为 解 (1)由于没有限制每一个同学可得纪念册和纪念章的本数和枚数,故此问题属于可重组合问题.将4枚纪念章分给10位同学的方法有F(10,4)=C(13,4);第5页/共11页 1.3 组合于是由乘法规则得所有的分法数为 N=C(13,4)C(15,6).5.为数众多的一分、二分、五分、一角硬币中有多少种方法选出六枚硬币？将6本纪念册分给10位同学的方法数为 F(10,6)=C(15,6);(2)由于每个人限制得一件物品,故此问题属于可重全排列问题.它是重集B=4纪念册,6 纪念章的可重全排列,排列数为解 这是属于重集的6-组合数问题,故有第6页/共11页1.用二项式定理展

7、开用二项式定理展开 2.在在 展开式中展开式中,的系数是什么的系数是什么?的系数是的系数是什么什么?3.用组合分析的方法证明恒等式用组合分析的方法证明恒等式4.设设n为正整数为正整数,则则 的值是的值是(-2)n ).5.设设n为正整数为正整数,则则 等于等于(2n-1 ).6.用组合分析法证明用组合分析法证明 1.5 组合恒等式 第7页/共11页3.用组合分析的方法证明恒等式用组合分析的方法证明恒等式 1.5 组合恒等式 6.用组合分析法证明 证明 等式左端可看作由n个元素组成的集合中的每个元素“取”与“不取”构成所有状态,由乘法规则可知其总数为2n 等式右端说明这所有状态可分解为从n个元素

8、中分别取0个,1个,n个组合的总和.证明 等式左端是从n个不同的元素组成的集合中先取l个元素,然后再从这l个元素中选取r个元素的方法数.由此所得的全体,相当于从n个不同元素中直接选取r个元素的组合,但有重复,其重复数为C(n-r,l-r).即重复数等于从剩下的n-r个元素中取l-r个元素的组合数.第8页/共11页 1.5 组合恒等式 例如 从1,2,3,4,5中取4-组合数得1234，1235，1245，1345，2345.再从每个组合中取2-组合数,结果见表从表中可见,从1,2,3,4,5中取2-组合为12,13,14,15,23,24,25,34,35,45.以12为例,由余下的3,4,5中取2-组合得34,35,45与12合并得1234,1235,1245.这些都有构成12的可能,12的重复是由此产生的.取2组合取4组合1213141523242534354512341213142324341235121315232535124512141524254513451314153435452345232425343545第9页/共11页The class is over.Goodbye!第10页/共11页感谢您的观看！第11页/共11页