2014年组合数学试题及答案

1、一、 （10分）用组合意义证明恒等式：n+3k=nk+3nk-1+3nk-2+nk-3证明：考虑对集合a1,a2,an,b1,b2,b3的k-组合计数可以表示为n+3k，同时该K-组合可以分成如下四类：第一类：从 a1,a2,an 中取k个，再从 b1,b2,b3中取0个；计数为nk 第二类：从 a1,a2,an 中取k-1个，再从 b1,b2,b3中取1个；计数为3nk-1第三类：从 a1,a2,an 中取k-2个，再从 b1,b2,b3中取2个；计数为3nk-2第四类：从 a1,a2,an 中取k-3个，再从 b1,b2,b3中取3个；计数为nk-3 因此，根据加法原则该恒等式成立。二、（

2、10分）由2n个人围成一个圆圈，问有多少种围法？若从中抽出n个人围成一圆圈有多少种围法？(1) (2n-1)!(2) 2n!/n n! 或 2n (2n-1) (n+1)/n三、（10分）设计从格路平面（0,0）走到（10,5）点，只能沿格路走水平或垂直方向，不可回退，且途径道路上会有若干萝卜坑（如图所示），请问恰巧只经过2个坑的格路数是多少？ 从左到右依次编号为1,2, 3, 4。分类考虑如下： 经过1、2的：C(4,2)*(C(7,2)+C(5,2)=186； 经过2、3的：(C(6,2)-C(4,2)*C(6,2)=135； 经过2、4的：(C(6,2)-C(4,2)*C(5,2)=90

3、； 共有：186+135+90=411四、（10分）有5对父子（共10人）参加“爸爸去哪儿”节目。一期节目是“交换爸爸”，即每位父亲在节目中的孩子不是自己的孩子。请问一共有多少种不同的安排方法？解：此题为n=5的错排问题，也可看做是n=5的有限制排列问题，棋盘多项式如下： RC=1+x5=n=055nxn所以，排列方法数 ：D5=r05!-r14!+r23!-r32!+r4.1!-r5 =5!-54!+103!-102!+5.1!-1 =44五、（10分）设有两个队Q1和Q2，每队都是30人，其中Q1队有15名男孩和15名女孩组成，Q2队男、女孩的人数不限。这两队按序号面对面地站好，如图所示，

4、然后，Q1队不动，Q2队迂回往右错动，每次依序错动一个位置。试证明当Q2错动到某一位置上时，Q1和Q2在对应位置上的两个小孩至少有15对是性别相同的。a 1a2a 3a 29a 30b1b2b 3b 29b 30a 1a2a 3a 29a 30b30b1b 2b 28b 29证明：Q2队迂回错动一圈再回到初始状态时，每个小孩无论是男孩还是女孩，在对应位置上都与Q1队的15个小孩同性别。故同性别的总对数为15*30=450。因此，每个错动位置上同性别的平均对数为450/30=15。根据鸽巢原理，必存在某一位置，当Q2错动到这个位置上时，则性别相同的小孩至少有15对。六（10分）设有N条封闭曲线画

5、在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。解：令an为n条封闭曲线把平面分割成的区域个数。若n-1条封闭曲线把平面分割成的区域个数为an-1,则第n条封闭曲线与这n-1条封闭曲线相交于2（n-1）个点，这2（n-1）个点把第n条封闭曲线截成2（n-1）段弧，这些弧把原来的2（n-1）个区域中的每个区域一分为二，故新增加的区域个数为2（n-1）。所以，满足如下的递归关系： an=an-1+2n-1,a1=2, 解该递归关系得：an=n2-n+2七（10分）面包店出售豆沙馅、椰蓉馅，果酱馅三种面包，小红到面包店时刚好有3个豆

6、沙馅，2个椰蓉馅，2个果酱馅面包出炉，小红带的食品袋正好可以装下5个面包，那么小红购买5个面包共有多少种不同的购买方案呢？解：该组合问题的母函数为Gx=1+x+x2+x3.(1+x+x2)2对上述母函数进行展开合并，得到x5的系数为6故，共有6种购买方案。八（10分）今安排5位女士和17位男士围圆桌而坐（22个座位均已编号），使得任何两位女士之间至少有3位男士，求有多少种不同的安排座位的方案？解：先任选一位女士，记为，则可依如下步骤安排座位：1 安排入座，有22种方法； 2 安排其他4位女士入座，使得任何两位女士之间至少有3个空座位。设由开始按逆时针顺序，5位女士依次为，且与之间有个空位，与之

7、间有个空位，则且 ，设为该式中满足条件的整数解个数，则完成本步骤的方法共有种。 因为是 展开式中的系数，而 所以完成本步骤的方法有：种。3 安排17位男士入座共有17！种方法； 综合上述三个步骤，由乘法法则得：不同的安排座位的方法数共有： 九（10分）用红、白、蓝三色珠子穿成一条长度为n的珠串，要求蓝色珠子的个数为偶数，问满足条件的长度为n的珠串有多少种穿法？（用母函数法）解：该排列问题的母函数为：Gx=(1+x+x22!+x33!+)2.1+x22!+x44!+ =e2xex+e-x2=e3x+ex2=123n+1xnn! 所以方法数为：an=(3n+1)/2十.（10分）设用三种颜色对一个五角星的五个区域着色，求在允许旋转和翻转的情况下,有多少种不同的染色方案？解：该问题可以用波利亚定理求解，共