组合数学复习题.ppt

《组合数学复习题.ppt》由会员分享，可在线阅读，更多相关《组合数学复习题.ppt（51页珍藏版）》请在课桌文档上搜索。

1、1,组合数学,第十四讲,总复习,2,第一部分 组合数学基本要求,3,1.两个基本计数原理:会正确使用加法原理和乘法原理.2.排列与组合类型的问题:普通排列组合、允许重复的排列组合、圆排列、有限制的排列等,这些问题可能用到不同地方的知识.因此希望把全书关于排列组合的有关问题集中总结一下,掌握不同问题的不同求解方法.,4,3.路径问题*:路径问题是一类很广泛的问题.其基本模型是在一个网格中,确定从一格点到另外一格点满足一定条件的路径的个数.但是许多许多类型的问题都可以化成网格路径问题,要掌握这种转化问题的思想方法,例如排队买票找零钱的问题等.4差分表方法及其应用5建立递归关系并求通项公式,5,6.

2、利用特征值方法求解递归关系7.掌握用整数拆分问题的思想求解砝码称重问题的思想方法.8.熟练掌握容斥原理,及其在整除问题中的应用.9.鸽巢原理与Ramsey理论的基本方法、性质、具体应用实例.,6,10.对于置换群：(1)熟悉置换的轮换分解、类型；(2)会决定一些简单几何图形的置换群和简单置换群的轮换指标公式.11.会利用Burnside引理求置换群的轨道数目12.会应用Polya计数定理来求解一些与对象对称性有的染色问题,7,第二部分例题选讲,8,例1.从1,2,30中选取3个不同的数字,使得它们的和能被3整除,有多少种选取方法?解 用Ai表示130中除以3余数为i的整数的集合,|Ai|=10

3、,i=0,1,2.选法有两类:(1)3个数属于同一个Ai:3C(10,3)=360(2)3个数分别选自3个不同的Ai:101010=1000根据加法原理,总数为:1360.,9,例2.5只白色的棋子和3只红色的棋子摆方在88棋盘上,要求每行每列只有一个棋子,问共有多少种不同摆法?解 设N种放法.可如下完成摆放.(1)设想把8个白棋子摆放在棋盘上,使得任意两个不在同一行也不在同一列,共有摆法:8!=40320种.(2)把已经摆好的8个白棋子中的3个白棋换为3个红棋,可有C(8,3)=56种.由乘法法则:N=4032056=2257920.,10,例3.从整数1,2,2n中任选n+1个数,证明在所

4、选的数中间必然存在两个整数,其中之一可以被另一个整除.证明 对于任何一个整数x,总可以把x写成x=2ka形式,其中a是奇数,k0.,1到2n之间一共有n个奇数,由所选的n+1个数利用上述方式可以得到n+1个奇数,其中必然有两个相同,设这两个数为:x=2ra,y=2sa,如果rs,那么x|y;如果rs,那么y|x.,11,例4.设a1,a2,an+1为n+1个正整数其和为2n,且满足ain,i=1,2,n,则这n+1个整数一定可以分成两组,使得每一组数的和恰好为n.解 令,由假设,显然有1b1b2bnbn+1,且bn2n-1.设bj=qjn+rj,qj=0或1,0rjn-1.若某个rj=0,则b

5、j=n,则结论得证.因此不妨设1rjn-1，j=1,2,n.,12,这时由鸽巢原理,n个余数r1,r2,rn中必然有两个相同.可设rk=rj,而kj.这时候bkbj,而bk-bj=(qk-qj)n.必然有qk=1,qj=0.这样bk-bj=n,即 aj+1+aj+2+ak=n,自然,其余数的和也正好是n.例5.如果有1克的砝码2枚,2克的砝码2枚,4克的砝码2枚,问能称出哪些重量?12克的重量有几种称法方案?,13,所以可以称14种重量.由于x12的系数为2,所以12克的重量有两种称法方案.,14,例6.设有1,2,4,8,16,32克砝码各一枚,那么对1到63之间的每个正整数k,用这些砝码不

6、仅可以称出k克的重量而且称法是唯一的.解,由xk系数的含义即可得到结论.,15,例7.建立下列问题的递归关系(1)由数0和数1组成的长度为n的数串中,使得两个1不相邻的数串有多少个?解 设有an个这样的数串.这样的数串可以分为两类:第一类:数串第一个数为0.这类数串的个数为an-1个.第二类:数串第一个数为1.第2个数只能是0,所以这类数串的个数为an-2个.,16,因此,我们得到递归关系:an=an-1+an-2,n3可以直接通过列举,得到:a1=2,a2=3.上述递归关系特征方程为:x2-x-1=0,特征根为:,17,其通解可设为:,利用初值通过解方程组可以求出待定参数A,B的值.从而得到

7、解.这个递归关系与Fibonacci数列相同,但是初值不相同.(请自己得出具体结果).,18,(2)如果用k种颜色对n边形的n个不同的顶点染色,使得任何两个相邻顶点染不同颜色,问有多少种不同的染色方案?解 设有an种染色方案.显然有a2=k(k-1),k2;a3=k(k-1)(k-2),k3.对于n边形而言,染色方案可以分成两类.第一类:v1与vn-1染同样的颜色,这时的染色方案数相当于n-2边形的染色方案数.由于vn有k-1种颜色可供选择,这类染色方案数为(k-1)an-2.,19,v1,v2,v3,vn-1,vn,合并v1,vn-1,20,第二类:v1与vn-1染不同的颜色,这时的染色方案

8、数相当于n-1边形的染色方案数.由于vn有k-2种颜色可供选择,这类染色方案数为(k-2)an-1.因此,我们有 an=(k-2)an-1+(k-1)an-2,n3而a2=k(k-1),k2;a3=k(k-1)(k-2),k3.特征方程:x2-(k-2)x-(k-1)=0.可以求出特征根并利用初值得到通项.,21,v1,v2,v3,vn-1,vn,22,例8.甲,乙两人竞选厂长,甲得票a张,乙得票b张,ab,问点票过程中甲得票恒领先于乙的情形有多少种?解 把该问题化为网格中两点间有条件限制的路径数目.曾有专门的例题.过程从略.结果为:,请参阅第4讲关于路径问题的例题.,23,例9.用差分方法给

9、出求和公式:,解 令f(n)=(n+1)(n+2)2,构造差分表如下:4 18 48 100 180 14 30 52 80 16 22 28 6 6 0,24,利用下述公式:,25,解 差分表为 1 1 3 19 0 2 16 2 14 12,例10.已知f(n)是n的一个3次多项式,且f(0)=1,f(1)=1,f(2)=3,f(3)=19,确定f(n)并求,26,根据公式:,27,例11.用特征值方法求解下列递归关系：,解(a)特征方程:x2-4x+3=0 特征根:x1=1,x2=3,所以可设:hn=c1+c23n,n=0,1,2.,28,根据初始条件解得 c1=2,c2=1,所以 hn

10、=2+3n,n=0,1,2,.(b)特征方程:x3-5x2+8x-4=0 特征根:x1=1,x2=x3=2,所以可设 hn=c11n+c22n+c3n2n,n=0,1,2.根据初始条件解得:c1=3,c2=-1,c3=1,所以 hn=3-2n+n2n,n=0,1,2,.,29,例12.求1至250间能被4,5或6中某个数整除的数的个数.解 设A1,A2,A3分别是1250之间能被4、5、6整除的整数的集合,则有|A1|=250/4=62|A2|=250/5=50|A3|=250/6=41|A1A2|=250/20=12|A1A3|=250/12=20|A2A3|=250/30=8,30,|A1

11、A2A3|=250/60=4.根据容斥原理,我们有:|A1A2A3|=|A1|+|A2|+|A3|-|A1A2|-|A1A3|-|A2A3|+|A1A2A3|=62+50+41-12-20-8+4=117.,31,例13 若集合S由10人组成,那么S中存在至少4个人互相认识,或存在至少3个人互不认识.证明 在这10个人当中任意固定一个人A,则其余人可以分成两类：,F：与A相互认识的人的集合 T:与A相互不认识的人的集合 由鸽巢原理,至少有一类含有不少于5个的人.证明可以分情况得到.,32,若|T|3,则|F|6,由引理2,F中有3个互相认识的或者互相不认识的.如果有3个互相不认识的,引理得证;

12、如果有3个互相认识的,再加上A就是4个互相认识的,结论.,(2)若|T|4,如果T中所有人都是互相认识的,引理得证;如果T中至少有两个人互相不认识,再加上A就是3个互相不认识的,结论也成立.,33,例14(1)用3种颜色对正三角形的顶点进行染色,如果考虑平面的旋转等价性,那么有多少种不等价的染色方案?如果还要再考虑轴对称,有多少种不等价的染色方案?(2)对正四边形讨论类似问题.,解法:(i)决定相应置换群与轮换指标公式:,34,(ii)再利用Plya定理中的公式得到结果,其中PG(x1,x2,xn)为置换群G的轮换指标,c(g)是置换g中不相交轮换总数.若g的类型为(c1,c2,cn),则c(

13、g)=c1+c2+cn.下面是我们曾经讲过的例题,希望熟练掌握.,35,例15 在下图中v1v2v3是一个等边三角形上的三个顶点.把红、蓝、绿3种颜色的珠子镶上.试问有几种不同的方案？,1,2,3,解:这个图形置换群为：G=(1)(2)(3),(123),(321),(1)(23),(2)(13),(3)(21).,36,其轮换指标公式为:,此时m=3.由Plya定理,不同的染色方案数为:,37,例16 有3种不同颜色的珠子,用它们串成4个珠子的项链.问一共能串成多少种不同类型的项链?列举出全部不同类型的方案.,解 先要确定保持图形与原来位置重合的置换群G.,1,2,3,4,38,容易看出来使

14、得项链运动前后重合的置换群G含有以下8个置换:(1)(2)(3)(4),(2)(4)(13),(1)(3)(24),(13)(24),(12)(34),(14)(23),(1234),(4321),共有4种类型的置换,容易写出其轮换指标公式:,39,总方案数,例17.求字母a,b,c,d,e,f和g具有下列性质的排列个数：在这些排列中,模式ace和df都不出现.解 设A1,A2分别为出现模式ace和模式df的排列的集合,则有|A1|=5!(=ace,A1为,b,d,f,g的排列);|A2|=6!(=df,A2为,a,b,c,e,g的排列);,40,|A1A2=4!(A1A2为,b,g的全部排列

15、).由容斥原理,模式ace和模式df都不出现的排列个数为:,41,第三部分 以前考试题选讲,42,1.如果从北京到石家庄有2条道路可供选择,从石家庄到太原有3条道路可供选择,从太原到西安有4条道路可供选择,那么从北京经石家庄、太原再到西安有 24 条不同的道路可供选择.2.从400到999的整数中既不含数字5又不含数字6的整数有 256 个.3.如果一次羽毛球单打比赛共有40名选手参加,如果比赛采用淘汰制,最后只需要产生一名冠军,那么共需要安排39 场比赛.,43,4.从1到600的整数中既不能被3整除也不能被5整除的整数有320个.5.三只白色的棋子和两只红色的棋子摆放在 55棋盘上,要求每

16、行每列只放置一个棋子,则共1200种不同的摆放方法.6.n个变量的布尔函数共有 个互不相同的.7.从3n个连续正整数中选取三个不同的数使 得它们的和能被3整除,共有 n(3n2-3n+2)/2=n3+3C(n,3)种选取方法.8*.n个顶点有标号的树的数目为 nn-2,n2.,44,9.设平面上有n条不同直线,其中任意两条不平行,任意三条不相交于同一点,则这n条直线交点总数为 n(n-1)/2;这n条直线把平面分割成(n2+n+2)/2个不同的区域.,10.如果把6个人分成两组，每组至少2人，则共有 25 种不同的分组方式.11.若n为大于1的正整数,则满足条件x+y n的有序正整数对(x,y

17、)的个数为 n(n-1)/2.12.从1到100不重复地选取两个数,组成有序数 对(x,y),使得x与y的积xy不能被3整除,则共可组成 4422 个不同的有序对.,45,13.要举办一场晚会,共有10个节目,其中有6个演唱节目,4个舞蹈节目.现在要编排节目单,要求任意两个舞蹈节目之间至少要安排一个演唱节目,则共可写出 604800 种不同的节目单.6!C(7,3)4!14.如果要从1,2,30中选取三个不同的数,使得它们的和能被3整除,总共有 1360 种选取方法.15.凸n边形对角线的数目为 n(n-3)/2 条,其中n 4.,46,16.学校要给某系一年级学生统一开设三门外语:英语,法语

18、和日语.要求每个学生至少要选一门外语.已知选修英语、法语、日语的人数分别为256,168和 118,同时选修英语和法语的有68人,同时选修英语和日语的38人,同时选修法语和日语的28人,同时选修这三门外语的10人.试计算出该系一年级学生总人数、只选英语的人数、恰好选修两门外语的人数.,47,解 设选修英语、法语、日语的人所组成的集合分为A,B,C.根据容斥原理:总人数=|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|=256+168+118-68-38-28+10=418只学英语的人数=|ABC|-|BC|=|ABC|-(|B|+|C|-|BC|)=418-(168

19、+118)+28=160,48,恰好选修两门外语的人数=|AB-ABC|+|AC-ABC|+|BC-ABC|=(68-10)+(38-10)+(28-10)=104 所以,总人数、只选英语的人数、恰好选修两门语的人数分别是:418,160,104.,49,17.在信道上传输仅用5个字母a,b,c,d,e组成并且长度为n的词.规定连续出现两个a的词不能传输.如果用h(n)来表示这个信道允许传输的长为n的词的个数,试建立关于h(n)的递归关系并求解.解 令h(n)表示允许传输且长度为n的词的个数,n=1,2,3,.通过统计易知,h(1)=5,h(2)=24.设n3,则第一个字母是b,c,d或e的词后面n-1位的组成方式为h(n-1);第一个字母是a的词,其第二个字母是b,c,d或e,而后面的n-2位的组成方式为h(n-2).,50,利用乘法原理,我们有以下递归关系,且h(1)=5,h(2)=24.该递归关系的特征方程为,其特征根为：,故一般解为:,51,由边界条件h(1)=5,h(2)=24.解联立方程组：,由此解出：,因此,该递归关系的解为:,