组合数学复习题.doc

例1 染色问题: 设A、B、C、D为正方形的四个顶点（如图1.1）所示. 用r(红)，b(蓝)，g(绿)三种颜色对它们染色，问有多少种染色方式及其方案数？ 设P是染色对象的集合，R是颜色的集合，一种染色方式就是对P中每一对象安排一种色. 所谓方案数是指某种染色方式的方案个数. 分析方法：因为每个顶点都有三种染色方案：或是红色，或是蓝色，或是绿色. 共有四个顶点，所以染色方案总数为34=81. 各种染色方式及其方案数为:(r+b+g)4 =r4+b4+g4+6r2b2+6r2g2+6b2g2+4r3b+4r3g+4rb3+4b3g+4rg3+4bg3+12r2bg+12rb2g+12rbg2 展开式各项系数之和为81，刚好等于染色方案总数. 该展开式共有15项，说明有15种染色方式，每一项中的字母部分就是具体的染色方式，其前面的系数是属于这种染色方式的方案数. 例2 求在1000到9000之间各位数字都不相同，而且由奇数构成的整数个数？ 例1.3 从1000到9999的整数中, 问(1)含有5的数有多少个? (2)含有多少个百位和十位数均为奇数的偶数? (3)各位数都不相同的奇数有多少个? 解 设有数字集合{0,1,2,3,4,5,6,7,8,9}. 先求不含5的整数的个数. 这时候个位数字,十位数字和百位数字各有9种选择, 而千位数字只有8种选择, 所以不含5的整数的个数=8*9*9*9=5832, 从1000到9999共有9000个整数, 所以含有5的的整数=9000-5832=3168. 当个位数字为0,2,4,6,8的时候对应的该整数为偶数, 因此个位数有5种选择, 十位数字和百位数字各有5种选择,而千位数字有9种选择, 故含有个百位和十位数均为奇数的偶数=9*5*5*5=1125. (3)当个位数字为1,3,5,7,9的时候对应数字为奇数. 如果要求各位数都不相同, 则个位数有5种选择, 当个位数选定之后, 千位数只有8种选择, 而当千位数选择之后, 百位数可以有8种选择, 以上三位数都选定之后,剩下的十位数就只有7种选择了. 所以, 从1000到9999的整数中, 各位数字都不相同的奇数=8*8*7*5 =2240. 设有排列(p) 按照字典式排序, 它的下一个排列是谁? 26387541例2.3 设有排列(p) =2763541, 按照字典式排序, 它的下一个排列是谁? (q) =2764135. (1) 2763541 [找最后一个正序35] (2) 2763541 [找3后面比3大的最后一个数] (3) 2764531 [交换3,4的位置] (4) 2764135 [把4后面的531反序排列为 135即得到最后的排列(q)] 母函数 若有1克的砝码3枚, 2克的4枚, 4克的2枚.问能称出哪些重量？各有几种方案？ 已经母函数，求对应的序列{} A+B=3，7A-8B=-9, A=1, B=2 丢掷四颗骰子，求出现的点数和为15的丢掷结果的种数。 解：以an记点数和为n的丢掷结果种数，则{an}的母函数为： 指数性母函数 由1，2，3，4，5 ，6六个数字组成的n位数，求其中4，5出现偶数次，1，2，3，6出现次数不限的数的个数an。 例1 由1，2，3，4，5五个数字组成的n位数，求其中4，5出现偶数次，1，2，3出现次数不限的数的个数an。 解：{an}的指数型母函数为 一个凸6边形, 通过不相交于6边形内部的对角线, 把6边形拆分成若干三角形, 不同拆分的数目用h6表之. hn+1=(1/n)C(2n-2, n-1) h6=14 五边形有如下五种拆分方案, 故h5=5. 容斥原理(1) 证明:对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 答：用100分别除这52个整数，得到的余数必为0,?1,?,?99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则ba?能被100整除。若a和b被100除余数之和是100，则ba?能被100整除。 求在1到1000的整数中不能被5,6,8中任何一个整除的整数的个数. 例：求在1到10000的整数中不能被4,5,6中任何一个整除的整数的个数. 解：令Ai(i=4,5,6)表示1到10000的整数中能被i整除的数的个数，则 求由a,b,c,d四个字符构成的n位符号串中a,b,c,d至少出