電子科大組合試題及答案09.12(工碩)

組合數(shù)學試題共5頁，第4頁學號姓名學號姓名學院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……（考試時間：至，共2小時）課程名稱組合數(shù)學教師盧光輝、楊國武學時40學分2教學方式講授考核日期2009年12月日成績考核方式：（學生填寫）一、(14分)現(xiàn)安排從星期一至星期五對5個項目A,B,C,D,E進行評審，每個項目安排一天，每天安排一個項目。但要求項目A不安排在星期二評審，項目B不安排在星期三和星期五評審，項目C不安排在星期四評審，項目D不安排在星期一評審，項目E不安排在星期三和星期四評審。問有多少種不同的評審安排方案？解原問題可模型化為一個5元有禁位的排列.其禁區(qū)棋盤C如下圖的陰影部分。4分由圖,可得C的棋盤多項式為12345R(C)=12345ABCDEABCDE=1+7x+17x2+18x3+8x4+x55分所以安排方案數(shù)為5!-7·4!+17·3!-18·2!+8-14分=25即共有25種。1分二、（10分）用2種顏色對下圖的小圓點著色，證明必存在兩列，其著色完全相同。1123456789證明：因每個小圓點有2種顏色可選,故每列恰有8種著色方案,5分現(xiàn)有9列,由鴿籠原理,知必有兩列著色相同.5分三、（16分）求方程的正整數(shù)解的個數(shù)。解等價于求集合S0＝{3.A,4.B,1.C,∞.D}的所有6-組合構(gòu)成的集合。4分令集合S為的所有6-組合構(gòu)成的集合。2分則有|S|=F(4,6)=84。學號姓名學院……密……………封……………線……………以學號姓名學院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……于是,,12分由容斥原理，所求的5-組合數(shù)為3分=84–(10＋4+35)＋1=361分四、（14分）解下列遞歸關(guān)系解對應的齊關(guān)系的特征方程x2-5x-14=03分有根x1=7，x2=-2。1分故齊關(guān)系的通解為=c17n+c2(-2)n1分設(shè)特解=An(-2)n，代入原關(guān)系：An(-2)n-5A(n-1)(-2)n-1-14A(n-2)(-2)n-2=(-2)3分學號姓名學院……密……………封……………線……………以……………內(nèi)學號姓名學院……密……………封……………線……………以……………內(nèi)……………答……………題……………無……………效……∴an=+=c17n+c2(-2)n+1分由初值得2分∴an=7n+(-2)n+1分五、（12分）求1出現(xiàn)奇數(shù)次且2出現(xiàn)偶數(shù)次的n位十進制數(shù)的個數(shù)。解：設(shè)an是由0,1,……,9組成的滿足“1出現(xiàn)奇數(shù)次”且“2出現(xiàn)偶數(shù)次”的長為n的序列的個數(shù)， 2分則an的指數(shù)母函數(shù)為：fe(x)==4分所以an=，n≥13分以0為首項的長為n的序列有an－1個，在上述序列中去掉以0為首項的長為n的序列便可得到1出現(xiàn)奇數(shù)次且2出現(xiàn)偶數(shù)次的n位十進制數(shù)的個數(shù)：2分an－an－1＝1分六、（14分）求由數(shù)字0，1，2，3，4，5，6，7組成的位數(shù)中，1和5都出現(xiàn)偶數(shù)次，2和6至少出現(xiàn)一次的位數(shù)的個數(shù)。解：這是一個排列問題。設(shè)滿足條件的位數(shù)字串的個數(shù)為，則序列對應的指數(shù)母函數(shù)為：3分fe(x)=4分所以＝3分首位取0的位數(shù)字串的個數(shù)為，故所求的位數(shù)的個數(shù)為－＝ 2分2分；如果沒有針對r=0單獨結(jié)果的，只得1分七、（6分）設(shè)表示一個凸n邊形被它的對角線劃分成互不重疊的區(qū)域個數(shù)(沒有三條對角線在該n邊形內(nèi)交于一點)。試建立的遞規(guī)關(guān)系（不需要求解）。解：,n>3.其中：―――――――――――――――――過程4分，結(jié)果2分。八、（14分）若7個人中有3對夫婦，試問從中取出6個人的夫婦均不相鄰的圓排列有多少種？解：分兩種情況。情況1.取出的6個人中恰含3對夫婦。1分計算如下:取全集S為6個人的圓排列的集合。令Ai為S中第i對夫婦相鄰的圓排列的集合，i=1,2,3。有1分|S|=5?。?20,|Ai|=24?。?8，i=1,2,3；|Ai∩Aj|=43?。?4（ij=1,2,3；ij）；|A1∩A2∩A3|＝16。2分由容斥原理1分=120－348＋324－16＝321分情況2.取出的6個人中恰含2對夫婦。1分此時取6人的方式有6種，對取定的每一種取全集S為6個人的圓排列的集合。令Ai為S中第i對夫婦相鄰的圓排列的集合，i=1,2。2分有|S|=5?。?20,|Ai|=24?。?8，i=1,2；|A1∩A2|＝43?。?4。1分由容斥原理