组合原理及其应用习题.doc

1.有8个人围圆桌就餐，（1）问有多少种就坐方式？（2）如果甲乙两人不愿坐在一起，又有多少种就坐方式？
解：（1）Q（8，8）=(8-1)!=7!
(2)若甲和乙坐在一起，有6！种就坐方式，而甲和乙坐在一起时，分甲在乙前和甲在乙后两种情况，所以甲和乙在一起有2×6！中就坐方式，故甲和乙不坐在一起的方式为：7!-2×6！=3600种

2.给出等式的组合意义
解：表示从2n个元素中取n个元素的组合数，设A为这2n个元素的集合，把A分成两个子集A1和A2，使得|A1|=|A2|=n，则取A的每个n-组合数可理解为：从集合A1中选取k(0≤k≤n)个元素，（方案数为），其余的n-k个元素从A2中选取，（方案数为），由乘法原理：种方案，
再根据加法法则，得，原等式成立
3.利用多项式定理求(x1-2x2+3x3)5的展开式中项的系数。
解：
4.有三个黑球，三个白球和四个红球，同色球不区分，现将10个球排成一行,试问
（1）黑色球均不相邻的排法有多少种？
（2）存在两黑球相邻的排法（包括三个黑球排在一起的情况）有多少种？
解(1)先排白球和红球，再插入黑球：
(2)此题为10个球的排列结果总数减去（1）的结果：
10！/(3!3!4!)-1960=2240
5.求解递推方程：
解对应的齐次递推关系的通解为，因为1不是递推关系的特征根，故设其特解为，带入递推式得
An+B+2[A(n-1)+B]=n+3
比较同次幂系数得A=1/3,B=11/9
所以原递推关系的通解为
由初始条件a0=3得C=16/9。所以

6.求不定方程的整数解个数。
解：令y1=3-x1,y2=4-x2,y3=5-x3则
原方程等价于的整数解个数
即多重集S={∞.y1,∞.y2,∞.y3}的2-组合数，为C(3+2-1,2)=6
法二，法三分别使用容斥定理或生成函数来求解.
8.利用指数生成函数求数字1，3，5，7组成的r位数的个数,其中要求7出现的次数为偶数。
解：该问题等价于求多重集S={∞.1,∞.3,∞.5,∞.7}的r-排列数，其中7出现偶数次
设所求的r-排列数为ar，则序列{ar}的指数母函数为

9.在边长为1的正三角形里任选10个点，证明存在两点，其距离不超过1/3.
证明：以三角形的三条中线互联，把三角形划分为9个边长为1/3的小正三角形，10个点至少有两个点落在同一个小三角形中，所以距离不超过1/3.
9.有4名旅客甲、乙、丙、丁要去4个不同地方A,B,C,D。其中，甲不愿意去C,D；乙不愿意去A，B，丙和丁都不愿意去C，问有多少种让每个人都满意的方案（每个人只能去一个地方）？
解：有禁区的（阴影部分）的棋盘多项式为
R(C)=(1+2x)(x+(1+2x)(1+x))=(1+2x)(2x2+4x+1)=1+6x+10x2+4x3
所以方案数为N=4!-6.3!+10.2!-4=4种。

10.用红、蓝、绿三种颜色对正三角形的顶点及其中心着色。(如图所示)求不同的方案数，经旋转或翻转能使之重合的方案算一种。

解：使正方形重合的运动及对应的置换有：
（1）不动(1)(2)(3)(4),格式为(1)4
(2)绕中心旋转120。和240。,对应的置换为(123)(4),(132)(4)格式均为(1)1(3)1。
(3)绕中线旋转，对应的置换有三个(1)(4)(23),(2)(4)(13),(3)(4)(12)
格式均为(1)2(2)1
共6个置换，构成6阶置换群，由polya定理，着色方案数为
m=1/6(34+2.32+3.33)=180/6=30

第二套
1.由m个0，n个1组成的m+n位符号串中，求至少存在两个1相邻的符号串的数目。（其中n≤m+1）
解：(m+n)!/m!n!-C(m+1,n)
2.有12个人分两桌就餐，每桌6个人，围着圆桌而坐，有多少种方案？（2）若有12对夫妻平分为两桌，每对夫妻相邻而坐，有多少种方案？
解：（1）C（12,6）5！5！
(2)C(12,6)(5！26)2
3.利用组合分析法证明：
解：右边为从m+n个元素中取m个元素的组合数，设A为这m+n个元素的集合，把A分成两个子集A1和A2，使得|A1|=m，|A2|=n，则取A的每个m-组合数可理解为：从集合A2中选取k(0≤k≤n)个元素，（方案数为），其余的m-k个元素从A1中选取，（方案数为），由乘法原理，原等式成立
4.利用多项式定理求(x1-2x2+3x3-4x4)5的展开式中项的系数。
解：
5.求a,b,c,d,e,f这6个字母的全排列中不允许出现ace和df的排列数。（提示：使用容斥定理）
解：6!-(4!+5!)+(3!)=582
6.由数字0,1,2组成的长为n的字符串在通信信道上传输，要求满足条件：传输的每个字符串中，0和1不能相邻，