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

1.有8个人围圆桌就餐，（1）问有多少种就坐方式？（2）如果甲乙两人不愿坐在一起，又有多少种就坐方式？解：（1）Q（8，8）=(8-1)!=7!(2) 若甲和乙坐在一起，有6！种就坐方式，而甲和乙坐在一起时，分甲在乙前和甲在乙后两种情况，所以甲和乙在一起有26！中就坐方式，故甲和乙不坐在一起的方式为：7!-26！=3600种2. 给出等式的组合意义解：表示从2n个元素中取n个元素的组合数，设A为这2n个元素的集合，把A分成两个子集A1和A2，使得|A1|=|A2|=n，则取A的每个n-组合数可理解为：从集合A1中选取k(0kn)个元素，（方案数为），其余的n-k个元素从A2中选取，（方案数为），由乘法原理：种方案，再根据加法法则，得，原等式成立3.利用多项式定理求(x1-2x2+3x3)5的展开式中项的系数。解：4.有三个黑球，三个白球和四个红球，同色球不区分，现将10个球排成一行,试问（1）黑色球均不相邻的排法有多少种？（2）存在两黑球相邻的排法（包括三个黑球排在一起的情况）有多少种？解(1)先排白球和红球，再插入黑球：(2)此题为10个球的排列结果总数减去（1）的结果：10！/(3!3!4!)-1960=22405.求解递推方程：解对应的齐次递推关系的通解为，因为1不是递推关系的特征根，故设其特解为，带入递推式得An+B+2A(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相邻的符号串的数目。（其中nm+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(0kn)个元素，（方案数为），其余的m-k个元素从A1中选取，（方案数为），由乘法原理，原等式成立4.利用多项式定理求(x1-2x2+3x3-4x4)5的展开式中项的系数。解：5. 求a,b,c,d,e,f这6个字母的全排列中不允许出现ace和df的排列数。（提示：使用容斥定理）解：6!-(4!+5!)+(3!)=5826.由数字0,1,2组成的长为n的字符串在通信信道上传输，要求满足条件：传输的每个字符串中，0和1不能相邻，确定通信信道允许传输的字符串个数an（a0=1）解：an=an-1+2an-2（n2）a0=1, a1=3特征方程：x2-x-2=0特征根：2，-1通解：c1(-1)n+c22n带入初始条件：c1+c2=1,-c1+2c2=3 求得c1=-1/3,c2=4/3所以an=-1/3(-1)n+4/3(2n)7.求解递推方程：解对应的齐次递推关系的通解为，因为1是递推关系的特征根，故设其特解为，带入递推式得An2+Bn=A(n-1)2+B(n-1)+2(n-1)比较同次幂系数得A=1,B=-1所以原递推关系的通解为由初始条件a1=2得C=2。所以8.利用指数生成函数求用红色、白色、蓝色对1n棋盘的方格涂色的方法数hn，其中红色方格的个数为偶数。解：所求的hn的指数母函数为9.证明单位圆周上任意7个不相同的点中，至少存在两点其间距离不超过1.证明：将单位圆分为6个同样长度的弧，每个弧的圆心角对应为60o，由鸽笼原理，至少两个点存在于同一段弧上，因为圆心角为60o，所以最大的弦长为1，所以这两点的距离不会超过110由红、黄两种颜色的珠子穿成五个珠子的项链，问不同的项链有几种？ 解：相当于正五边形的顶点用两种颜色着色，对应的置换有：（1）不动 (1)(2)(3)(4)(5式为(1)4(2)绕中心旋转72o,144o,216o,288o对应的置换，其中一个为(12345)格式为(5)1