发布时间 : 星期三 文章组合数学复习题 - 图文更新完毕开始阅读
例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}.
(1) 先求不含5的整数的个数. 这时候个位数字,十位数字和百位数字各有9种选择, 而千位数字只有8种选择, 所以不含5的整数的个数=8*9*9*9=5832, 从1000到9999共有9000个整数, 所以含有5的的整数=9000-5832=3168.
(2) 当个位数字为0,2,4,6,8的时候对应的该整数为偶数, 因此个位数有5种选择, 十位数字和百位数字各有5种选择,而千位数字有9种选择, 故含有个百位和十位数均为奇数的偶数=9*5*5*5=1125.
(3) (3)当个位数字为1,3,5,7,9的时候对应数字为奇数. 如果要求各位数都不相同, 则个位数有5种选择, 当个位数选定之后, 千位数只有8种选择, 而当千位数选择之后, 百位数可以有8种选择, 以上三位数都选定之后,剩下的十位数就只有7种选择了. 所以, 从1000到9999的整数中, 各位数字都不相同的奇数=8*8*7*5 =2240.
设有排列(p) =26385741, 按照字典式排序, 它的下一个排列是谁? 26385741->26387541->26387145
例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枚.问能称出哪些重量？各有几种方案？
G(x)?(1?x?x2?x3)
(1?x2?x4?x6?x8)(1?x4?x8)
?1?x?2x2?2x3?3x4?3x5?4x6?4x7
8910111213?5x?5x?5x?5x?4x?4x
?3x14?3x15?2x16?2x17?x18?x19.已经母函数
3-9x，求对应的序列{an}
1-x?56x2G(x)?3?9xAB(A?B)?(7A?8B)x???
(1?8x)(1?7x)1?8x1?7x(1?8x)(1?7x)A+B=3，7A-8B=-9, A=1, B=2
G(x)?12 ?1?8x1?7xan?8n?2(?7)n
丢掷四颗骰子，求出现的点数和为15的丢掷结果的种数。 解：以an记点数和为n的丢掷结果种数，则{an}的母函数为：
62345644234544?1?x?46121824f(x)?(x?x?x?x?x?x)?x(1?x?x?x?x?x)?x??1?x???x(1?4x?6x?4x?x)??4(C(3,0)?C(4,1)x?C(5,2)x2?C(6,3)x3?...) a15?C(14,11)?4C(8,5)
指数性母函数
由1，2，3，4，5 ，6六个数字组成的n位数，求其中4，5出现偶数次，1，2，3，6出现次数不限的数的个数an。
24 ????x2x4x2x3??? Ge(x)???1?2!?4!????1?x?2!?3!???????2
?ex?e?x?4x12x4x6x?e???e?2e?e ??24??
n1?nnnx ??(2?2*4?6)4n?0n!??所以an?1n(2?2*4n?6n)4例1 由1，2，3，4，5五个数字组成的n位数，求其中4，5出现偶数次，1，2，3出现次数不限的数的个数an。 解：{an}的指数型母函数为
23 2423????xxxx G(x)??1???????1?x????e????2!4!2!3! ????2
?ex?e?x?3x1x3x5x? ??e?e?2e?e?2?4?? 1nnn?a?1?2?3?5 1nnnx4?1?2?3?5
4n?0n!
一个凸6边形, 通过不相交于6边形内部的对角线, 把6边形拆分成若干三角形, 不同拆分的数目用h6表之.
hn+1=(1/n)C(2n-2, n-1) h6=14
五边形有如下五种拆分方案, 故h5=5.
容斥原理(1)
8)证明:对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。
答：用100分别除这52个整数，得到的余数必为0, 1,?, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则ba100整除。若a和b被100除余数之和是100，则ba100整除。
求在1到1000的整数中不能被5,6,8中任何一个整除的整数的个数.
?1000??1000? A5||???200,|A?A|??3356????5??5?6?
?1000???1000|A?A|??25,|A?A?A|??88568?5*8??[5,? 58]?120????6, |?166,|A8|?125,|A6?A8|?41 A6|例：求在1到10000的整数中不能被4,5,6中任何一个整除的整数的个数. 解：令Ai(i=4,5,6)表示1到10000的整数中能被i整除的数的个数，则 ?10000??10000?|A|??2500,|A?A|??500445????
?4??4?5?
?10000??10000? |A4?A6|???833,|A?A?A|??166456????[4,6]?12??[4,5,6]?60?
|A5|?2000,|A6|?1666,|A5?A6|?333
|A4A5A6|?10000?(|A4|?|A5|?|A6|)
A5|?|A4A6|?|A5A6|?|A4A5A6| ?|A4????????5334求由a,b,c,d四个字符构成的n位符号串中a,b,c,d至少出现一次的符号串的数目。 n|A?A???A|?4?A1?A2???A4124
nnn n?4?Ai?Ai?Aj?Ai?Aj?Ak??
i?1i?1j?ii?1j?ik?j
n ?(?1)A1?A2???An欧拉函数
例如n=60=2*2*3*5，则ψ（60）=60（1-1/2)(1-1/3)(1-1/5)=16 即比60小且与60互素的数有16个：
1，7，11，13，17, 19, 23，29，31，37，41，43，47，49，53，59。
棋盘多项式
??????
有张、王、李、赵四位教师, 有数学、物理、化学、英语四门课程. 已知张不能教数学, 王不能教物理和化学, 李不能教化学和英语, 赵不能教英语. 若使每位教师教各自承担力所能及的一门课程, 问有多少种安排方案？
解 这个问题实际上是有禁位的排列, 其禁区就是刚才图中的阴影部分. 由上面的计算知道图6.5中的禁区棋盘多项式为
1+6x+10x2+4x3 故有 r1=6, r2=10, r3=4, r4=0.
因此, 由公式(6.5), 所求安排方案数为: Q4=4!-63!+102!-41!+00!=4. 鸽巢原理
令S是由6个正整数组成的集合，其中最大的数不超过14，试说明如果将S的所有非空子集中的元素分别加起来，则所得到的和不可能彼此不同的。 S={a1,a2,a3,a4,a5,a6} {a1},{a2},…{a6},
{a1,a2},{a1,a3},…,{a5,a6}
{a1,a2,a3},{a1,a2,a4},…,{a4,a5,a6}