《组合数学》.doc

一、(每题5分，共15分) 1、在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？解：该题相当于从“1，3，5，7，9”五个数字中分别选出1，2，3，4作排列的方案数； （1）选1个，即构成1位数，共有个； （2）选2个，即构成两位数，共有个； （3）选3个，即构成3位数，共有个； （4）选4个，即构成4位数，共有个； 由加法法则可知，所求的整数共有：个。2、若某两人拒绝相邻而坐，问12个人围圆周就坐有多少种方式？解：12个人围圆周就坐的方式有：种，设不愿坐在一起的两人为甲和乙，将这两个人相邻而坐，可看为1人，则这样的就坐方式有：种；由于甲乙相邻而坐，可能是“甲乙”也可能是“乙甲”；所以则满足条件的就坐方式有：种。3、对夫妻围圆桌而坐，求夫妻不相邻的方案数。4、求小于10000的正整数中含有数字9的数的个数。5、设 ，求除尽的整数个数。6、求在1000和9999之间各位数字都不相同的奇数个数。7、6男6女围圆桌交替就坐有多少种就坐方式？8、4对夫妻围圆桌而坐，求夫妻不相邻的方案数。二、（每题5分，共10分）1、写出容斥原理的两个公式。及证明2、叙述鸽巢原理并举一个例子加以说明。所谓鸽巢原理，即只鸽子，只有个巢，则至少有一个鸽巢内至少有两只鸽子。如：366个人中必然至少存在两人有相同的生日。三、解下列递推关系：（每题5分，共15分）1、对应的特征方程为：，解得。 所以齐次递推方程的通解为：， 代入初始条件，得：， 解得：， 故 。2、对应的特征方程为：，解得：， 所以，齐次递推方程的通解为：， 代入初始条件， 解得：，故。3、对应的特征方程为：，解得：， 所以，齐次递推方程的通解为：， 代入初始条件， 解得：，故 。4、对应的特征方程为：，解得：， 所以，齐次递推方程的通解为：， 代入初始条件，解得，故 四、求下列数列的母函数 （每题5分，共10分）（1）； 母函数为：（2）；母函数为：（3）；母函数为：五、（15分）1、红、黄、蓝三色的球各8个，从中取出9个，要求每种颜色的球至少一个，问有多少种不同的取法？解：对应的母函数为： 从中取9个对应的组合数为的系数，即 （种） 2、试求由a，b，c三个字母组成的n位符号串中不出现aa图像的符号串的数目。解：假设符合条件的符合串的数目为，考虑第1位数的数值，有两种情况： （1）第1位为a，则第2位只能是b或c，余下的位满足条件的有个； 根据乘法法则，这类情况总共有个； （2）第1位为b或c，则余下的满足条件的有个； 根据加法法则，可得递推关系，且； 对应的特征方程为：，解得：， 因此，通解为，代入初始条件， ，解得，故 3、试求由0，1，2三个数字组成的n位三进制数中不出现00的三进制数的数目。六、（15分）1、求从1到500的整数中能被3和5整除但不能被7整除的数的个数。解：设为1到500的整数中能被i整除的数的集合， 则， ， ， 满足条件的整数个数为：，根据容斥原理有： 2、由这四个字符取5个作允许重复的排列，要求出现次数不超过2次，但不能不出现；不超过1个；不超过3个；出现的次数为偶数。求满足以上条件的排列数。必须将上式转化成指数型母函数得由此可见满足上述条件取5个进行排列的排列数为215.七、（10分）1、某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次。问该人共参加几次会议？解：设S为该人参加的所有会议组成的集合，设表示该人与第i个朋友相遇的所有会议构成的子集，则 ， ， ， 则， 则该人共参加会议次数为： （次）。2、有1克砝码2枚，2克砝码3枚，5克砝码3枚，问能称出哪些重量，又各有几种称法。解：所以能称123克等23种重量的物品。总共的称法为母函数的各项系数之和，再减去常数项，即总共有（种）不同的称法。其中，称1、3、20、22、23克重量各有1种称法；称2、4、5、8、9、10、13、14、15、18、19、21克重量各有2种称法；称6、7、11、12、16、17克重量各有3种乘法；3、8台计算机分给3个单位，第一个单位的分配量不超过3台，第二个单位不超过4台，第三个单位不超过5台，问共有几种分配方案？解：对应的母函数为： 所求的分配方案数即的系数，即分配方案数为： （种）八、（10分）在格路问题中，从点到点的路径中，求不通过AB,CD,EF,GH的路径数，已知,.解：设 : 从点到点的路径经AB， : 从点到点的路径经CD，: 从点到点的路径经EF，: 从点到点的路径经GH， 则, , , 例13 某校有12个教师，已知教数学的有8位，教物理的有6位，教化学的5位；数理5位，数化4位，理、化3位；数理化3位。问教其他课的有几位？只教一门的有几位？只教两门的有几位？令A1, A2, A3分别表示教数学物理化学的教师的集合。则有：a(0)12，a(1)|A1|+|A2|+|A3|8+6+519; a(2)|A1A2|+ |A1A3|+|A2A3|12； a(3)|A1A2A3|3； 因此教其他课，只教一门，只教两门的分别为：b(0)=a(0)-a(1)+a(2)-a(3)=2；b(1)=a(1)-2a(2)+3a(3)=4；b(2)=a(2)-3a(3)=3。例4 求由abcdef这六个字符组成的全排列中不允许出现ace和df图象的排列数。令A、B分别表示出现ace、df图象的排列的集合。A中是出现ace图象的排列，即ace作为一个元素参加排列，因此有|A|=4!。类似有|B|=5!，|AB|=3！。而全集的元素个数为|U|=6!，因此满足条件的排列数为：例5 求4个x，3个y，2个z组成的全排列中不允许出现xxxx，yyy和zz图象的排列数。令ABC表示出现xxxx、yyy、zz图象的排列的集合。A中的排列是把xxxx作为一个元素参加排列，注意有3个y和2个z，因此|A|=6!/(3!2!)=60。类似有|B|=7!/(4!2!)=105， |C|=8!/(4!3!)=280， |AB|=4!/2!=12，|BC|=6!/4!=30，|AC|=5!/3!=20, |AB C |=3!=6，|U|=9!/(4!3!2!)=1260。因此满足条件的排列数为：例7 用26个英文字母作不允许重复的全排列，要求排除dog，god，gum，depth，thing字样的出现，求满足这些条件的排列数。令Ai (i=1,2,3,4,5)分别表示出现以上五个单词之一的排列的集合。A1中的集合是把dog作为一个元素参加排列，因此有|A1|=24!。类似有：|A2|=|A3|=24!， |A4|=|A5|=22! 。由于dog和god不能同时出现，所以|A1A2|=