组合数学考试题附答案2

组合数学试题共4页，第1页电子科技大学研究生试卷（考试时间：14：30至16：30，共2小时）课程名称组合数学教师卢光辉，张先迪学时40学分2教学方式讲授考核日期2006年12月2日成绩考核方式：（学生填写）一．填空题（每空2分，共22分）1．食品店有三种不同的月饼（同种月饼不加区分），第一种有5个，第二种有6个，第三种有7个，(1)从中取出4个装成一盒（盒内无序），则不同的装法数有种；(2)从中取出6个装成一盒（盒内无序），则不同的装法数有种；（3）若将所有的月饼排在一个货架上，则排法数有种（给出表达式，不必算出数值结果）。（4）若将所有的月饼装在三个不同的盒子中，盒内有序（即盒内作线排列），盒子不空，则不同的装法数又有种（给出表达式，不必算出数值结果）。2．棋盘C如图1所示，则棋子多项式R(C)=3．设有足够多的红球、黄球和绿球，同色球不加区分，设从中无序地取出n个球的方式数为an，有序地取出n个球的方式数为bn，但均需满足红球的数量为偶，黄球的数量为奇，则(1)由组合意义写出的{an}的普通母函数为；求和后的母函数为。(2)由组合意义写出的{bn}的指数母函数为；求和后的母函数为。4．（1）将6个无区别的球放入3个无区别的盒子中且盒子不空的放法数为。学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………图1学号姓名学院……………………密……………封……………线……………以……………内……………答……………题……………无……………效……………………组合数学试题共4页，第2页（2）将6个有区别的球放入3个无区别的盒子中且盒子不空的放法数为。（已知将5个有区别的球放入3个无区别的盒子中且盒子不空的放法数为25）二、（14分）给定重集B={3·A,3·B,4·C,10·D}。求B的8-组合数。三、（14分）解下列递归关系87,7)1(761021aaaaannnn四、（10分）用三种颜色对下图的小圆点着色，证明必存在两列，其着色完全相同。五、（16分）设长为n的三元序列（即用0,1,2组成序列）中1与2的个数之和为奇的序列个数为an。1．试建立{an}的递归关系（不要求解出）。2．用另一方法（即不用解递归关系的方法）求出an。六、（14分）对下图中的7个小方格用红、黄、绿和黑四种颜色着色，问:着红、黄和绿色的小方格的个数均不为2的着色方案数是多少？七、（共10分）1.现有7个人，其中恰有一对夫妇。试问从中取出6个人的夫妇不相邻的线排列有多少种？2.若7个人中有三对夫妇，试问从中取出6个人的夫妇均不相邻的圆排列又有多少种？一．填空题（每空2分，共20分）1．（1）F(3,4)=C(6,4)=15；（2）F(3,6)-1=C(8,2)-1=27；（3）!7!6!5!18；（4）217!7!6!5!182．R(C)=(1+3x+x2)(1+2x)=1+5x+7x2+2x312345678910组合数学试题共4页，第3页3．（1）(1+x2+x4+…)(x+x3+…)(1+x2+…);2322)1()1(11111xxxxxxx（2）2432(1)()(1)2!4!1!3!1!2!xxxxxx;4223xxxxxxxeeeeeee4．（1）3；（2）90二、（14分）给定重集B={3·A,3·B,4·C,10·D}。求B的8-组合数。解令集合S为{,,,}ABCD的所有8-组合构成的集合。则有|S|=F(4,8)=165令A1表示S中至少含有4个A的元素构成的集合,A2表示S中至少含有4个B的元素构成的集合,A3表示S中至少含有5个C的元素构成的集合,于是1231213231234,435,4,3201,0AAFAFAAAAAAAAA由容斥原理，所求的8-组合数为31231231iijiijAAASAAAAAA=165–(35+35+20)+1=76三.（14分）解x2-6x-7=0有根x1=-1，x2=7，所以an*=c1(-1)n+c27n设na=An(-1)n，代入原关系An(-1)n-6A(n-1)(-1)n-1-7A(n-2)(-1)n-2=(-1)nAn+6A(n-1)-7A(n-2)=1令n=2：2A+6A=1A=81所以na=8n(-1)n，an=c1(-1)n+c27n+8n(-1)n8781772121ccccc1=6，c2=1∴an=6(-1)n+7n+8n(-1)n四、（10分）证明因每点有3种颜色可选,故每列恰有9种着色方案,现有10列,由鸽笼原理,知必有两列着色相同.组合数学试题共4页，第4页五、（16分）解(1)111232nnnaaa或者4,232221221aaaaannnn（2）fe(x)＝22432(1)()(1)2!4!1!3!1!2!xxxxxx＝222xxxxxeeeee=32xxee=!2])1(3[0nxnnnn所以2)1(3nnna六、（14分）解取全集S为用4种色对7个小方格的着色方案构成的集合。设A1为S中着红色的小方格的个数为2的着色方案的集合，A2为S中着黄色的小方格的个数为2的着色方案的集合，A3为S中着绿色的小方格的个数为2的着色方案的集合。有74S＝16384iA=C(7,2)35=5103,i＝1,2,3jiAA=C(7,2)C(5,2)23=1680，i,j∈{1,2,3},ij；321AAA=630∴所求数=321AAA=16384-3×5103+3×1680-630=5485七、（10分）解1.总数＝取到夫妇两人＋没有取到夫妇两人＝C(5,4)[6!-25!]+26!=5480+1440=2400+1440=3840或总数＝总的排列数－夫妇相邻的排列方式数＝P(7,6)-525!=5040-1200=38402.分两种情况。情况1.取出的6个人中恰含3对夫妇。计算如下取全集S为6个人的圆排列的集合。令Ai为S中第i对夫妇相邻的圆排列的集合，i=1,2,3。有|S|=5！＝120,|Ai|=24！＝48，i=1,2,3；|Ai∩Aj|=43！＝24（ij=1,2,3；ij）；|A1∩A2∩A3|＝16。由容斥原理321AAA=120－348＋324－16＝32情况2.取出的6个人中恰含2对夫妇。此时取6人的方式有6种，对取定的每一种取全集S为6个人的圆排列的集合。令Ai为S中第i对夫妇相邻的圆排列的集合，i=1,2。有|S|=5！＝120,|Ai|=24！＝48，i=1,2；|A1∩A2|＝43！＝24。由容斥原理21AA=120－248＋24＝48所以此类总数为648＝288最终结果为:32＋288＝320