组合数学习题.ppt

1.2排列,1.求在1000和9999之间各位数字不相同的奇数个数.,解由于它们之间的数都是4位数,所以可以先选个位,再选千位、百位和十位.,又所要的数为奇数,所以个位数字只能是1,3,5,7,9中的任何一个,即有5种选法,千位只有8种选法,百位也有8种选法,十位有7种选法.,所以由乘法规则得所求奇数个数为5887=2240个.,2.求在1000和9999之间各位数字不相同且由奇数构成的整数个数.,解由于它们之间的数都是4位数且要求各位都是奇数,故所求整数个数为,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女交替就坐方式数为24120=2880.,1.2排列,解(1)先计算不含数字1的个数.,不考虑10,000,000,000本身,把任何一个小于该数的不含1的正整数看作10位数,但全是0除外.相当于从0,2,3,99个数中选取,共有10个位置,故共有910-1个.,(2)含1的数共有1010-(910-1)+1个.,5.在1和10,000,000,000之间的一百亿个数中,有多少个数含有数字1?又有多少个数不含数字1?,6.单词“MISSISSIPPI”中的字母有多少种不同的排列方法？如果两个S不相邻，又有多少种排列方法？,解这是可重全排列问题.,(1)这相当于重集B=1M,4I,4S,2P的全排列,故全排列数为,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)=20种,又5个有标志的球共有5!=120种排法,故由乘法规则得所求排列数为,20120=240(种).,1.3组合,1.空间中有30个点,这30个点无四个点共面,问它们能确定多少三角形?能确定多少四面体?,解由于任意三点可确定一个三角形,故有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符合,有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,1.3组合,代入原方程得,3.求方程的正整数解的个数.,4.有纪念章4枚,纪念册6本,分送给10位同学,问有多少种分法?如果限制每人得一件物品,则又有多少种分法?,解令,即,上式的非负整数解的个数等于原方程的正整数解的个数,故原方程正整数解的个数为,解(1)由于没有限制每一个同学可得纪念册和纪念章的本数和枚数,故此问题属于可重组合问题.,将4枚纪念章分给10位同学的方法有F(10,4)=C(13,4);,1.3组合,于是由乘法规则得所有的分法数为N=C(13,4)C(15,6).,5.为数众多的一分、二分、五分、一角硬币中有多少种方法选出六枚硬币？,将6本纪念册分给10位同学的方法数为F(10,6)=C(15,6);,(2)由于每个人限制得一件物品,故此问题属于可重全排列问题.,它是重集B=4纪念册,6纪念章的可重全排列,排列数为,解这是属于重集,的6-组合数问题,故有,1.用二项式定理展开2.在展开式中,的系数是什么?的系数是什么?3.用组合分析的方法证明恒等式4.设n为正整数,则的值是(-2)n).5.设n为正整数,则等于(2n-1).6.用组合分析法证明,1.5组合恒等式,3.用组合分析的方法证明恒等式,1.5组合恒等式,6.用组合分析法证明,证明等式左端可看作由n个元素组成的集合中的每个元素“取”与“不取”构成所有状态,由乘法规则可知其总数为2n,等式右端说明这所有状态可分解为从n个元素中分别取0个,1个,n个组合的总和.,证明等式左端是从n个不同的元素组成的集合中先取l个元素,然后再从这l个元素中选取r个元素的方法数.,由此所得的全体,相当于从n个不同元素中直接选取r个元素的组合,但有重复,其重复数为C(n-r,l-r).,即重复数等于从剩下的n-r个元素中取l-r个元素的组合数.,1.5组合恒等式,例如从1,2,3,4,5中取4-组合数得,1234，1235，1245，1345，2345.,再从每个组合中取2-组合数,结果见表,从表中可见,从1,2,3,4,5中取2-组合为12,