(完整word版)組合數(shù)學(xué)課后答案

1、證明： 在一個至少有2 人的小組中， 總存在兩個人， 他們在組內(nèi)所認(rèn)識的人數(shù)相同。證明： 假設(shè)沒有人誰都不認(rèn)識：那么每個人認(rèn)識的人數(shù)都為 1,n-1 ，由鴿巢原理知， n 個人認(rèn)識的人數(shù)有n-1 種，那么至少有2 個人認(rèn)識的人數(shù)相同。 假設(shè)有 1 人誰都不認(rèn)識：那么其他 n-1 人認(rèn)識的人數(shù)都為 1,n-2 ，由鴿巢原理知， n-1 個人認(rèn)識的人數(shù)有n-2 種，那么至少有2 個人認(rèn)識的人數(shù)相同。 假設(shè)至少有兩人誰都不認(rèn)識， 則認(rèn)識的人數(shù)為 0 的至少有兩人。任取 11 個整數(shù)，求證其中至少有兩個數(shù)的差是10 的整數(shù)倍。 證明：對于任意的一個整數(shù)， 它除以10的余數(shù)只能有10種情況：0,1 ,，

2、9。現(xiàn)在有11個整數(shù)，由鴿巢原理知，至少有 2 個整數(shù)的余數(shù)相同，則這兩個整數(shù)的差必是10 的整數(shù)倍。 證明：平面上任取5 個坐標(biāo)為整數(shù)的點，則其中至少有兩個點，由它們所連線段的中點的坐標(biāo)也是整數(shù)。 2.3 證明：有 5 個坐標(biāo)，每個坐標(biāo)只有4 種可能的情況：（奇數(shù)，偶數(shù)）；（奇數(shù)，奇數(shù)）；（偶數(shù)，偶數(shù)）；（偶數(shù)，奇數(shù)）。由鴿巢原理知，至少有2 個坐標(biāo)的情況相同。又要想使中點的坐標(biāo)也是整數(shù)，則其兩點連線的坐標(biāo)之和為偶數(shù)。因為 奇數(shù) + 奇數(shù) = 偶數(shù) ； 偶數(shù) + 偶數(shù) =偶數(shù)。因此只需找以上2 個情況相同的點。而已證明：存在至少2 個坐標(biāo)的情況相同。證明成立。一次選秀活動，每個人表演后可能得

3、到的結(jié)果分別為“通過”、“淘汰”和“待定”，至少有多少人參加才能保證必有100 個人得到相同的結(jié)果？ 證明： 根據(jù)推論 2.2.1 ，若將 3* （100-1 ） +1=298 個人得到 3 種結(jié)果，必有100 人得到相同結(jié)果。 一個袋子里裝了 100 個蘋果、 100 個香蕉、 100 個橘子和 100 個梨。那么至少取出多少水果后能夠保證已經(jīng)拿出 20 個相同種類的水果？ 證明：根據(jù)推論2.2.1 ，若將 4* （20-1 ） + 1 =77 個水果取出，必有20 個相同種類的水果。證明：在任意選取的 n +2 個正整數(shù)中存在兩個正整數(shù)，其差或和能被2 n 整除。（書上例題2.1.3 ）證

4、明：對于任意一個整數(shù)，它除以2n的余數(shù)顯然只有2n種情況，即：0, 1 , 2, 2n-2 ， 2n-1 。而現(xiàn)在有任意給定的 n+2 個整數(shù)，我們需要構(gòu)造n+1 個盒子，即對上面2n個余數(shù)進(jìn)行分組，共 n+1 組：0,1 , 2n-1,2 , 2n-2,3,2n-3,，n-1,n+1 , n。根據(jù)鴿巢原理， n+2 個整數(shù)， 必有兩個整數(shù)除以 2n 落入上面 n+1 個盒子里中的一個， 若是 0 或 n 則說明它們的和及差都能被2n 整除； 若是剩下 n-1 組， 因為一組有兩個余數(shù)，余數(shù)相同則它們的差能被2n 整除，不同則它們的和能被 2n 整除。證明成立。一個網(wǎng)站在9 天中被訪問了 18

5、00 次， 證明： 存在連續(xù)的 3 天， 這個網(wǎng)站的訪問量超多 600次。 證明： 設(shè)網(wǎng)站在 9 天中訪問數(shù)分別為 a1 ， a2， .， a9 其中a1+a2+.+a9 = 1800， 令 a1+a2+a3 = b1 ， a4+a5+a6 = b2 ， a7+a8+a9 = b3 因為( b1+b2+b3 ) /3 >= 6002.2.2 知， b1 ， b2 ， b3 中至少有一個數(shù)大于等于600 。 所以存在有連續(xù)的三天，訪問量大于等于600 次。 將一個矩形分成5 行 41 列的網(wǎng)格，每個格子涂1 種顏色，有4種顏色可以選擇，證明： 無論怎樣涂色， 其中必有一個由格子構(gòu)成的矩形的

6、 4 個角上的格子被涂上同一種顏色。 證明：首先對一列而言，因為有5 行，只有 4 只顏色選擇，根據(jù)鴿巢原理， 則必有兩個單元格的顏色相同。 另外， 每列中兩個單元格的不同位置組合有(25)=10 種，這樣一列中兩個同色單元格的位置組合共有10*4=40 種情況。而現(xiàn)在共有41 列，根據(jù)鴿巢原理，無論怎樣涂色，則必有兩列相同，也就是必有一個由格子構(gòu)成的矩形的上的格子是同一顏色。 將一個矩形分成(m+1) 行 m列的網(wǎng)格每個格子涂1 種顏色，4 個角4 個角上有 m 種顏色可以選擇，證明：無論怎么涂色，其中必有一個由格子構(gòu)成的矩形的證明： ( 1 )對每一列而言，有( m+1 )行， m 種顏色

7、，有鴿巢原理， 則必有兩個單元格顏色相同。 (2) 每列中兩個單元格的不同位置組合有(m2+ 1)種，這樣一列中兩個同色單元格的位置組合共有(m+ 1種情況(3)現(xiàn)在有m(m+ 1)+ 1列, 根據(jù)鴿巢原理，必有兩列相同。證明結(jié)論成立。 一名實驗員在50天里每天至少做一次實驗，而實驗總次數(shù)不超過75。證明一定存在連續(xù)的若干天，她正好做了 24次實驗。證明：令b1 , b2 ,，b50分別為這50天中他每天的實 驗數(shù)，并做部分和a1 = b1 , a2 = b1+b2 ,。a50 = b1+b2+.+b50.由題，bi>=1(1<=i<=50) 且 a50V=75 所以 1&l

8、t;=a1<a2<a3< <a50<=75(*)考慮數(shù)列 a1 ,a2,a50 , a1+24 , a2+24 , a50+24 ,它們都在 1 與 75+24=99 之間。由鴿巢原理知，其中必有兩項相等。由(*)知，a1 , a2,a50互不相等，從而a 1+24 , .a50+24 也互不相等，所以一定存在 1v=ivjv=50, 使得 aj =ai+24 ,即24=aj-ai=(b1+b2+b3+-+bi+ -+bj)-(b1+b2+-+bi)= bi+1 + t + 2 + .+ bj 所以從第i+1天到第j天這連續(xù)j-i天中，她正好做了 24次實驗。證明

9、：從$=1,3,5, ,599這300個奇數(shù)中任意選取101個數(shù)，在所選出的數(shù)中一定存在2個數(shù)，它們之間最多差4。證明：將S劃分為1,3,5, 7,9,11595,597,599共100組， 由鴿巢原理知任意選取101 個數(shù)中必存在2個數(shù)來自同一組， 即其差最多為 4.證明：從1200 中任意選取70個數(shù)，總有兩個數(shù)的差是4 ， 5或9 。 證明：設(shè)這70個數(shù)為a1,a2,，a70,a1+4,a2+4,，a70+4,a1+9,a2+9,，a7209, flMOKW證明：對于任意大于等于2的正整數(shù)n,都有R(2, n尸n。2.13證明：要證R (2,n) = n,用紅藍(lán)兩色涂色 Kn的邊。當(dāng)n=

10、2時，R(2,2)=2 ,因為不管用紅還 是藍(lán)色都是完全二邊形。假設(shè)當(dāng) n=k時成立,即存在R(2,k)=k (沒有一條紅 邊，只有藍(lán)邊)，當(dāng)n=k+1時，R (2, k+1 )若無紅邊，要想有完全k+1邊 形，必得有k+1個點，即R (2, k+1 ) =k+1。證明成立。習(xí)題三有10名大學(xué) 生被通知參加用人單位的面試，如果5個人被安排在上午面試，5個人被安排在 下午面試，則有多少種不同的安排面試的順序？解：上午的 5個人全排列為5! 下午的5個人全排列為5!所以有C1 *5!*5! =10!,共14400種不同的安排方 法。某個單位內(nèi)部的電話號碼是4位數(shù)字，如果要求數(shù)字不能重復(fù)，那么最多可

11、有多少個號碼？如果第一位數(shù)字不能是0,那么最多能有多少個電話號碼？解：由于數(shù)字不能重復(fù)，0-9共10個數(shù)字，所以最多有10*9*8*7=5040 種號 碼；若第一位不能是0,則最多有9*9*8*7=4536種號碼。18名排球運動員被分成A,B,C三個組，使得每組有6名運動員，那么有多少種分法？如果是分成 三個組(不可區(qū)別)，使得每組仍有6名運動員，那么有多少種分法？解：1)竦*如"6種 2) GrCrC；/?!教室有兩排，每排8個座位。現(xiàn)有學(xué)生 14人，其中的5個人總坐在前排，4個人總坐在后排，求有多少種方法將學(xué)生 安排在座位上？解：前排8個座位，5人固定，共C5*5!種方法；后排8

12、個座位， 4人固定，共C84 *4!種方法；前排和后排還剩7個座位，由剩下的5人挑選5 個座位，共C75 *5!種方法；則一共有C：*C；*C5*5!*5!*4!種安排方法。將英文 字母表中的26個字母排序，要求任意兩個元音字母不能相鄰，則有多少種排序 方法？解：先排21個輔音字母，共有21 ! 再將5個元音插入到22個空隙 中，P22故所求為21!MP22(插入法)有6名先生和6名女士圍坐一個圓桌就餐，要求男女交替就坐，則有多少種不同的排坐方式？解： 6 男全排列 6! ； 6 女全排列6 ??；6 女插入 6 男的前 6 個空或者后6 個空，即女打頭或男打頭6!*6!*2 ；再除以圍圈重復(fù)得

13、（6!*6!*2）/12=6!*5! 或男 6 的圓排列為5！，對每個男的排列，女要在他們之間的 6 個位置，進(jìn)行線性排列 6 ?。ǘ皇? ?。?。（圓排列可以通過線性排列來解決）15個人圍坐一個圓桌開會，如果先生A拒絕和先生B和C相鄰，那么有多少種排坐方式？解：15人圓排列14 ! ; A與B相鄰有2*14!/14=2*13!; A與C相鄰有2*14!/14=2*13!; A與BC同時相鄰有2*13!/13=2*12!;于是A不與B、C相鄰的坐法共14!- 2*13!- 2*13!+ 2*12!（用到了容斥原理）確定多重集M =3 a,4匕,5 c的11-排列數(shù)？解：M的11排列=M-a的1

14、1排列 +M-b的 11 排歹U +M-c的 11 排歹U,即 11! + 11! + 11! =27720 2!4!5!3!3!5!3!4!4!當(dāng)然了，容斥原理，生成函數(shù)也可以做。求方程x1 +x2 +x3 +x4 =20 ,滿足x1 22, x2之0,x3 >5,x4> -1的整數(shù)解的個數(shù)。解:6 171門7)=680U4/ <3；令yi 二x1 一2 20, y2 =x2 占 0,y3 =x35之0,丫4 =刈+1 占0 則 有V1+V+y2+y =14,3由定理3.3.3 ,解個數(shù)為：勺4*4114書架上有20卷百科全書，從中選出4卷使得任意兩本的卷號都不相鄰的選法有

15、多少種？解:n=20r+1) /20-4 + 1)? =八 4 J17 = 2380證明見38頁若卷號差為2 , 3 , 0 0 0 0 0 ,公式為?確定(2x-3y)5展開式中 x4y 和 x2y4 的系數(shù)。解：1 ) x4y ： C；*(2 x)4*( 3y)1 , 系數(shù)為-2402 ) x2y4 :系數(shù)為0。確定(1+ x)-5展開式中x4的系數(shù)。解： (1+x)=J (一1尸一Dxr，n=5 , r=4 ,則系數(shù)為(.1)4 5 *4 一1= 70 確衛(wèi) ' r J<4 J定(x +2y+3z)8 展開式中 x4y2x2 的系數(shù)。解： 8!*2 2 *3 2 =1512

16、04!*2!*2!證明組合等式:數(shù)。解：右邊n k 1n kn_kn .k MU （n+k+1 ）元集合 S=a1,a2,. ank1JJ k元子集中不A a1n+2、2 J+的個數(shù)，這些集3分%以下 k+1類：第1類:k+1),其中n,k為正整"n十"一幻年元第子集k-2集有個;第2類：k元子集中含a1而不含a2的子集是個;第3類：k元子集中含ai和a2，而不含a3的子集是第k+1類：k元子集中含a1尸2,ak,而不含ak+1的子集是由加法原理得證。根據(jù)組合意義進(jìn)行證明0;利用k2 =2<212 +22 +- +n2。解： 首先有：n +1卜+1n -1< k

17、+(p51的(3)根據(jù)已知條件代入以上等式得:% i2 C (2i 4 i 4二2.2二22、.+2=2(2)2)2、=2 1 In 12(n -1)n(n 1) n(n 1)I =+=1J1J1Jn(n 1)(2n 1)X'在一局排球比賽中，雙方最終的比分是25:11 ,在比賽過程中沒有出現(xiàn) 5平的比分，求有多少種可能的比分記錄？解：根據(jù)題意，相當(dāng)于求從點（0,0）到點 （25,11） 且不經(jīng)過（5,5） 的非降路徑數(shù)，即為3.17在一局乒乓球比賽中，運動25+1儲/5 + 5丫25-5+11-5、/36、什0丫26、""-入11-5 1 I11) I5 人6 J

18、員甲以11:7戰(zhàn)勝運動員乙，若在比賽過程中甲從來沒有落后過，求有多少種可能的比分記錄？解：根據(jù)題意，相當(dāng)于求從點（0,0）到點（11,7）且從下方不穿過y=x的非降路徑數(shù)，見58頁，即為：品+7-11+1+7-213.18把20個蘋果和 11-111+120個橘子一次一個的分發(fā)給40個幼兒園的小朋友，如果要求分發(fā)過程中任意時刻籃子中余下的兩種水果數(shù)目都不相同（開始和結(jié)束時除外），求有多少種分 法方法？解：根據(jù)題意，相當(dāng)于求從點（0,0）到點（20,20）且不接觸y=x的非降路徑數(shù)，即為：2J2n 一2'2n一2；=:一'2n'n=20 ，則方法數(shù)為： kn1 J <

19、; n ） n+1 <n J38)/38) 2(-J9J <20/7 I (61161(51 H5115 一 3- ? - 23 < -33 2 3 1 2 2 33.18計算，和彳。解：1)515"1廣4】)()=1+5< J，94J = 1+5 乙卜2« +9 « J+31 J2J司II1 JPJJU2J13JJ133-6 19*727*6個遞推公式，啟'2n -1,n -1二 301卜1=211 2 )2訃Bl1+5；2M5 闿= 1+11，51+30 5 12 3阱4m哪用= 1111業(yè)2 JJ=1 11(1 4*11) 3

20、0(11 4* C42) =15463.19 （1 ） 證明 S（n,3）= 方法一： 先 考慮 3 個盒子不同， 要保證每個盒子非空： 總數(shù)為 3n ， 排除到一個盒子為空和兩個盒子為空的情況， 即： 一個盒子為空 （放到兩個盒子去），例如第一個盒子為空,第二和第三不空： 3 （ 2n-2 ）兩個盒子為空，例如第一個和第二盒子為空： 3*1（3n-3 （ 2n-2 ） -3 ）/3! 還可以直接考慮盒子相同。（ 2 ）證明：相當(dāng)于n 個不同球放到相同的 n-2個盒子，每個盒子非空，至少為 1 個，這樣使得剩余的 2 個球要到 n-2 個盒子，即使得一個盒子有3 個，或有二個盒子都裝 2 個球

21、：使得一個盒子有3 個球：C（n,3） 有二個盒子都裝 2 個球： C（ n,4 ） C（4,2）/2!3.21 (1)會議室中有2n+ 1個座位，現(xiàn)擺成3排，要求任意兩排的座位都占大多數(shù)，求有多少種擺法？解：如果沒有附加限制則相當(dāng)于把2n個相同的小人f2n+3_1) + 2、球放到3個不同的盒子里，有.八 = c 種方案，而不符合題意的擺I 2n 八 2 J法是有一排至少有n+1個座位。這相當(dāng)于將n+1個座位先放到3排中的某一排，再將剩下的 2n-(n+1)=n-1 個座位任意分到 3排中，這樣的擺法共有-(n 1) 3-12種方案，所以符合題意的擺法有：攵n+2、2n +1.2可以用代數(shù)法

22、(2)會議室中有2n個座位，現(xiàn)擺成3排，要求任意兩排的座位都占大多數(shù)，求有多少種擺法?習(xí)題四4.1在1到1000之間不能被2, 5和11整除的整數(shù)有多少個？解：設(shè)S是這1000個數(shù)的集合，性質(zhì)R是可被2整除，性質(zhì)P2是可被5整除， 性 質(zhì)P3是 可 被 11 整 除。A =x|xw Sax具有性質(zhì) P,( i =1,2,3) | A1 |= 1000/2 = 500 , |A |= 1000/5 = 200,|A3|= 11000/11 j=90|AAJ= 1000/10= 100,|A1cA3 |= 1000/22=45 , |A2cA3|= 11000/55=18 , | A1A2 A3

23、|- 111000/110 = 9| A1 一 A2 A31= 1000 一(500 200 90) (100 45 18) - 9 = 364 4.3 一項對于A,B,C三個頻道的收視調(diào)查表明，有20%的用戶收看A, 16% 的用戶收看B, 14%的用戶收看C, 8%的用戶收看A和B, 5%的用戶收看 A和C, 4%的用戶收看B和C, 2%的用戶都看。求不收看A,B,C任何頻道 的 用 戶 百 分 比？ 解|A1 - A2 ' A3 |=1 -(20% 16% 14%) (8% 5% 4%) - 2% = 65%4.2求1到1000之間的非完全平方，非完全立方，更不是非完全四次方的數(shù)

24、有多少個？解：設(shè)S是1000個數(shù)的集合，性質(zhì)p是某數(shù)的完全平方，性質(zhì)P2是某數(shù)的完全立方，性質(zhì)p3是某數(shù)的完全四次方。 A =x|xw Sax具有性質(zhì) p,( i =1,2,3) |A 卜斤布卜 31 , |A2|=廿1000 卜 10/A3 卜.1000卜 5|A2|= .1000卜 3,|A1cA3|=也000卜 5,| A2cA3 |=惶1000卜 1,| A1cA2cA3 卜1號1000 卜 1| A1 - A2 - A3|= 1000-(31 10 5) (3 5 1)-1 = 9624.4某雜志對100名大學(xué)新生的愛好進(jìn)行調(diào)查，結(jié)果發(fā)現(xiàn)他們都喜歡看球賽和 電影、戲劇。其中58人喜歡

25、看球賽，38人喜歡看戲劇，52人喜歡看電影，既喜歡看球賽又喜歡看戲劇的有18人，既喜歡看電影又喜歡看戲劇的有16 人，三種都喜歡看的有12人，求有多少人只喜歡看電影？解：由題意可得，P1,P2,P3分別表示喜歡看球賽、電影和戲劇的學(xué)生，相應(yīng)的學(xué)生集合分別為A1,A2,A3 ,依題意，這100名大學(xué)生中每人至少有三種興趣中的一種，則|A1oA2A3| =0所以可得既喜歡看球賽有喜歡看電影的人有IA c AJ = (58 + 38 + 52) 100 (18 +16) + 12 = 26 因此只喜歡看電影的人有 A2 A1A2 - A2cA3 + A1C a2cA3 =52-(26+16)+12=

26、22 人 4.5某人有六位朋友，他跟這些朋友每一個都一起吃過晚餐12次，跟他們中任二位一起吃過6次晚餐，和任意三位一起吃過4次晚餐，和任意四位一起吃 過3次晚餐，任意五位一起吃過2次晚餐，跟六位朋友全部一起吃過一次晚 餐，另外，他自己在外吃過8次晚餐而沒碰見任何一位朋友，問他共在外面 吃過幾次晚餐?c6 父 12 - C；父 6 + C3 M 4 - C> 3 + C65 M 2- C66 父 1+ 8= 364.6計算多重集S=4 ?a, 3?b, 4?c,6?d 的12-組合的個數(shù)？解：令T十1A = A4卜|Ai 一|A2 -IA| A,a戶.b ,如c中，d的所有12合構(gòu)成W =

27、 4 + 12 1 = 455 具 12 J2+5儲A4 | =4+8 1) 陷=|08二 165 A3 =2 + 7 1、= 56,4+0-1、0;4+111A/ A3 卜 0二 120 ，IA - 21=4+3 1、= 20，I A - AI =4 + 21、= 10，二4 ，|A2 - A3 卜'4+3-1、l 3；I 人 一 A4 |二=204 + 01、- A2 - A3 - A4 卜 455- (120 120 165 56) (20 10 1 20 4)504.7計算多重集S=8?a, 4?b, 5?c,6?d 的10-組合的個數(shù)？解：將。0 a ,其4 10-1他思想同

28、上題。W=|= 286其中|A=|0I 10 J45-144-143-1|4|=| 廣=56,|A3|=|， 廣 35,|A4|=|° 廣20,15；14；13；|AM|=0 ，公2|=0 ，4人|=0 ， |廿%|二0 ， 叱人|=0,|飛飛|=0,| A1A2-A3 b 0| A1-A2 -A3-A4 |= 286 - (56 35 20) = 1754.8 用容斥原理確定如下兩個方程的整數(shù)解的個數(shù)。1 ) X1 + X2+X3 = 15 ,其中X1, X2, X3都是非負(fù)整數(shù)具都不大于7 ； X1+X2+X3+X4=20 ,其中X1, X2, X3, X4都是正整數(shù)其都不大于9

29、；解：1 )x1+x2+x3=15 (0 工 X1 w 7,0 w x2 w 7,0 w x3 M 7 )與7a,7b,7c的 15 組 合 數(shù) 相 等， 為 282)X1 +x2+x3+x4=20(1 M X1M9,1 M X2 <9,1 M X3M 9,1mX4M 9),因此用y1+1代替 ,y2+1代替x2,y3+1代替x3,y4+1代替x4有VJWV 16 (0 w y1 M 8,0 W y2 W 8,0 w y3 M 8,0 w y4 M 8)與8a,8b,8c,8d 的16組合數(shù)相等為4894.9定義Do=1，證明：n!的全排列包含錯位排列和非錯排,n其中11 | Ik JD

30、k表示在n個數(shù)中任選k個，這個k個數(shù)構(gòu)成了一個錯排，而剩余的n-k個數(shù)還在原來的位置。顯然 n! =D0 ' | D1 |00112nD2 + .JIin JDnpn =(n_1)(Dq D _) n D1 W =1-(n -1)!(1 (-1)1! 2!1(n-1)!（另一種方法：組合分析法）4.10證明：Dn滿足:n 為整數(shù)且3 證明：由定理 4.3.1 得= (n-1)!(1)(-1廣 ) (-1尸 1! 2!(n-2)!11n 21Dn工=(n -2)!(1. (-1)n)1! 2!(n- 2)!11n 21n 1Dn.Dn =(1-！-. (-1)、)(n-2)! n (-1

31、) -I IIIt 11n 21n 1(n-1)(DnDn)= n!(1-1亓.(-1)-) (-1)(n-1)I IIIt =(1 -1 2(-1廣一1 (-1)n-1 1(-1)n-)1! 2!(n - 2)!(n-1)! n!4.11有10名女士參加一個宴會，每人都寄存了一頂帽子和一把雨傘，而且帽子、雨傘都是互不相同的，當(dāng)宴會結(jié)束的離開的時候，如果帽子和雨傘都是隨機(jī)的還回的，那么有多少種方法使得每位女士拿到的物品都不是自己的？解：由于帽子全部拿錯和雨傘全部拿錯是兩個相互獨立的事件，設(shè)帽子全錯為d1111111111、H 人人出 4D10 = 10!(1 + )雨傘全錯為101! 2! 3

32、! 4! 5! 6! 7! 8! 9! 10!21M1210! 10!D120 = D110 解，DlD；。鋪= e4.算棋盤多項式=x*(1+3x+x2)+(1+x)*R(解：R()x*R( -LJ)+R(x3+3x 2+x+(1+x)xR()+R()x3+3x 2+x+(1+x)x(1+x)+(1+4x+2x2)=5x 3+12x 2+7x+14.14有A,B,C,D,E五種型號的轎車，用紅、白、藍(lán)、綠、 黑五種顏色進(jìn)行涂裝。要求 A型車不能涂成黑色；B型車 不能涂成紅色和白色；C型車不能涂成白色和綠色；D型車不能涂綠色和藍(lán)色；E型號車不能涂成藍(lán)色，求有多少種涂裝方案？解：A B C D

33、E紅白藍(lán)綠黑1.若未規(guī)定不同車型必須涂不同顏色，則：涂裝方案4父3父3父3父4 = 4322.若不同車型必須涂不同顏色，則：禁區(qū)的 棋盤多項式為：1+8x+22x 2+25x 3+11x 4+x 5 所以：5 ! -8*4 !+22*3 ! -25*2 ! +11*1 ! -1=204.15 計算 W210)，陽05).(舍)4.16 計算 T=OO?1, oo?2, oo?3, oo?4的長度為 4的圓排列數(shù)。（舍）補(bǔ)：（ 1 ）在12000中能被7整除，但不能被6 110整除的個數(shù)。明：A1,A2,A3 表示被6、7和10整除的數(shù)的子集，所A1CA2C73 ; A2 c A1。|A3求:=

34、A2 -A2 - (A 1 一 A 3 )=A2 -(A2 - A1 ) _. A 2 A 3)= A2 -( A 2 - A 1 A 2 - A 3 (A 2 - A 1 ) A 2 A 3)二219(中至少被 2、3 和 5 兩個數(shù)整除的數(shù)的個數(shù)？A2CA11A2cA3 +A1CA3 -2 A1A2cA3 =534 習(xí)題五5.1 求如下數(shù)歹!J的生成函數(shù)。(1) ak =(1)k(k+1); (2) ak=(1)kk2k； (3)ak = k+6；ak=k(k+2)； (5) ak =(6) ak;解：（1）由已知得bk = k 1B(x) =1 故 A(x) =(1-x)2(x 1)2(

35、2)設(shè) bk=(-2k 則 G =1-2x又因為ak=kbk 故 GaJ =x(Gbk)1-2xbk = kGaJ =Gbk =k GCk =6=_2(1-2x)或者>、B(x) =(1-x)222(1-x)21-x (1-x)2n 1 k -1一 一一 1Gak =x(Gbk =k 2)x(3 - x)(1-x)3(5)<k(6)G ak二 7a(1-x)ak 二bk =4,4+k儲與+k、1k5.2求如下數(shù)列的指數(shù)生成函數(shù)。（1） ak=（-1）k；x3Gak =-4 (1 -x) ak =2kk!;1二 xkak'W；解：GE七（一/代刈QOGea- 2kxkk與1二

36、 1= Gbk=2=(3) Geak=巳碇x =f(x)則1xf(x)-k©(1 k)!xk1xe -10G故 Ge ak=kx=1x -1 = e-1k=o k!5.3已知數(shù)列生成函數(shù)是一、2 3x -9x2 A(x),1 -3x求ak|解:A(x)=2 一2+3x 而 A(x) = 2Z 3 x 故1 - 3x1 - 3xk z0kak寸93，=54求（1+x4+x8）100展開式中一的系數(shù)是多少？若x8取0,則x4取5個，這種情況有C500種；（2）若x8取1,則x4取3個, 這種情況有CM C39或CM C；7； （3）若x8取2,則x4取1個，這種情況有C100 C99；故

37、系數(shù)為 C500 +C；00 c99+C100 C29 = 91457520。其他方法 5.5 三個人每個人投一次骰子，有多少種方法使得總點數(shù)為9?p：這相當(dāng)于有9個球，用隔板將其分成3組，共有C2 =28種方法。又因為這次點數(shù)小于等于6,即711 ,171和117三種情況不符，故共有25種方法23456 3(x -x -x -x -x -x )(x_x7產(chǎn)2 kxk k(2)5.6求在102和104之間的各位數(shù)字之和等于5?解:因此:由 k=0bk=4k,+2k，所以有4n+2n種方案5.8有4個紅球，3(1)三位數(shù)時，相當(dāng)于 +*2+*3=5(1£% E5,0Ex2E5,0Ex3

38、E5)的非負(fù)整數(shù)解的個數(shù)。故G(x) =(x +x2 +x3 +x4 +x5)(1 + x+x2 +x3 +x4 + x5)1+x + x2 +x3 +x4 +x5) 中C5為G(x)展開式x5的系數(shù)。(2)四位數(shù)時，相當(dāng)于 xi +x2 +x3 +x4 =5 (iwxi <5, 0<x2 <5,0 < x3 <5,0 <x4 <5)的非負(fù)整數(shù)解的個 數(shù)。5.7 一個1 xn的方格圖形用紅、藍(lán)、綠和橙四種顏色涂色，如果有偶數(shù)個方格被涂成紅色，還有偶數(shù)個方格被涂成綠色，求有多少種方案？解:涂 色 方 案 數(shù) 為bk則1 /d xr+ x 4 +2|/1+

39、 _x_2+_x_+ 2 _ e ex2/axe x -42ex 邛Gebk 一(1 "2!Ti I(1 "2r 手 一(2)(e )一 4_ 1一 4個黃球，3個藍(lán)球，每次從中取出5個排成一行，求排列的方案數(shù)？解：設(shè)每次取出的k個球的排列數(shù)為bk ,數(shù)列bk的指數(shù)型生成函數(shù)為Gebk則有Gb =(1 +貯+衛(wèi)+的)(1 +3 + W + W) (1+丘+ W)而我們所求的是 武 的kJe M ( 1 1! 2! 3! 4! AA 1 1! 2! 3!)( 1 1! 2!3!)4D <|v|-l5! 口 J系數(shù)b5。故有b5 =220。5.9計算用3個A, 3個G,

40、2個C和1個U構(gòu)成長度為2不同的RNA鏈的22數(shù)量。解：(1+x+')2|_(1+x+土)(1+x)中 X2的系數(shù) C2 ,有 C2=15.5.10 計 22算和37?。解：(1)構(gòu)造多項式 x(x1)(x2)(x3)(x4)(x5)(x 6)則，“即L3J30x3 的系數(shù) b3,則 b3 =1524,故11=1524。(2) 01= 工1nllJ2 n213n3均刊3 =41133/的非負(fù)整數(shù)解為(0,0,4), (1,2,3), (0,2,2), (0,3,1), (0,4,0), (1,0,3), (1,1,2),(1,2,1), (1,3,0),(2,0,2),(2,1,1),

41、 (2,2,0), (3,0,1),(3,1,0),.71=3- 21332232H 24/匕31，_32 11J2312_32(4,0,0)35.12 23 12 2213_21 1321 14 =30111設(shè)Bn表示把n元集劃分成非空子集的方法數(shù)，我們稱Bn為Bell數(shù)。證明：B =；，+ «2*,：>。證明：當(dāng)有1個盒子時，方法數(shù)匕=；，當(dāng)有2個盒子時，方法數(shù)b2 =/1,； 當(dāng)有k個盒子時，方法數(shù)2bk=n當(dāng)有n個盒子時，方法數(shù)bn=?!當(dāng)有n+1個盒子時，至少有一 kn人一人 一n nilniln . n-,個仝盒，不符。故Bn=£> + W >

42、 + W>+川 + W >5.12有重為1 gy 123 n的整碼重為1g的3個，重為2g的4個，重為4g的2個，求能稱出多少種重事？解：即求多項式(1+x + x +x)U(1 + x +x +x +x)_(1 + x +x)中展開式有多 少 項(除 1 外)， 原 多 項 式x)=(x1+2 x + 3 x + 4 x + 5 x+6 xt7 x)8 x+f 故共有 x +19種重量。5.13已知數(shù)列Ok1的指數(shù)生成函數(shù)是Ge(x)= x2+5ex,求a.解：ak=5, k 不等于 2ak=7, k =2f (x) = x2 5ex設(shè) 2x2 x3二 x 5(1 x .) 2!

43、 3!補(bǔ)：3個l, 2個2, 5個3這十個數(shù)，能構(gòu)成多少個4位數(shù)偶數(shù)。解 問題是求多重集S=3個1 , 2個2 , 5個3的4排列數(shù)，且要求排列的末尾為2 (偶Ge(X)=1+X+ .2!3!；數(shù))?？梢园褑栴}轉(zhuǎn)化成求多重集 S=3個1 , 1個2 , 5個3,其指數(shù)生成函數(shù)(1+x) 1 + x + + + + 、工 2!3!4!5!,43!3!3!3!3!3!3!x3x3 ”奧為 =|l|+ , - +一+ - + | 展開后東于的系數(shù)為3! 1!2! 1!2! 3! 1!2! 1!1!1! 2!1! 3!3!3X=卜204小 3!20 ,所以能組成20個4位數(shù)的偶數(shù)。習(xí)題六6.1設(shè)f(n

44、)=12+22+n2 ,建r _2J(n) = f(n-1) + n , (n >2)J (1)=1齊次特征方程：x-1=0特征根：x = 1非齊次特解：立f(n)的遞推關(guān)系并求解。解：f*(n) = (bofn+b2n2)n時 求解代入遞推關(guān)系得：,1.1,1b0 = 1，b1 =b2 623111 2f (n) = ( n n )n6 23遞推關(guān)系:f一 7f(戶12f5-2)=0,叱 2)解 f(0) =4, f(1) =6;齊次特征方程：x2 -7x , 12 =0,f(n) + f(n-2)=°g2) /(0)=0,“1)=2;特征根：x1 =4,x2 =3齊次通解：

45、f #(n) = c14n c23n代入遞推關(guān)系得：Ci=6 c2 =10f (n) -6 4n 10 3n力=0 ,八.一 . (3)xi - T,x2 二 if(n) =5f (ni) -6f (n-2)-4f (n -3) +8f (n 4),(n ")解:/(0)=0,“1)=1, f(2)=1, f(3)=2,;|_ 次特征方程：x4-5x3 +6 x2 +4x-8 =0 特征根：x1 =x2 =x3 =2,x4 =-1次通解：f#(n) =g 2n 02 n2n c3n2 2 c4 (-1)n代入|_推_系得：(4)f (n) -3f (n -1) 2f(n-2) =1,

46、(n _ 2) f(0) =4,f(1)=6;8718? C2 =? C3 =? C4 =27362427f(n)二2277 cn 12cn2 - n 23624-統(tǒng) 1)n齊次特征為2地x：+2 = 0特征根x1三2,x2 =1非齊次特解：解：代f * (n) =b°n入遞推關(guān)系得6.3 求解遞推關(guān)系bo = -1#Fl !f (n) = 0,2c2 - n0) 3, C2 1f(n) =3 2n 1 -nf (n) =4f (n -1) -4f (n -2) 3n 1, (n -2) f(0) =1, f(1) =2;齊次特征方程：x2 -4x , 4 = 0特征根：x1 = x

47、2 =2,非齊次特解：(2)f * (n) = b0 b1n代入遞推關(guān)系得：b0 =13,b1 =3f #(n) =c12n 02n2n 3n 13c1 = -12, c2 =10f (n) = -12 2n 10 n2n 3n 13f (n) =6f (n -1) -9f (n -2) 2n,(n -2) f(0) =1, f(1) =0；齊次特征方程：x2 _6x 9 = 0特征根：x1 = x2 =3,非齊次特解：f * (n) = b0 b1n代入遞推關(guān)系得：bo =12,6 =4f #(n) =G3n c2n3n 4n 12(3)r_ _ nf(n)=4f(n-1)+3x2 ,(n&

48、gt;1)斛 .f(0)=1,一 11c -"C1 一 II, C2 一3f (n) = -11 3n 17 n3n，4n 12齊次特征方程：x-4 = 0 特征根：x = 4, 非齊次特解：f *(n)二二 2n代入遞推關(guān)系得：f(n) = 2f (n-1) + n,(n>1)J(0)=1,-3#nnf (n) =c14 -3 2c1 = 4,n -1nf (n) =4-3 2齊次特征方程：x - 2 = 0 特征根：x=2, 非齊次特解：f * (n) = b0 b1n 代入遞推關(guān)系得：6.4 求解遞推關(guān)系：b0 =-2,b1 =-1f #(n) =G2n -n-2c1 =3,f(n)=32n-n-2；nf (n) +(n-1)f (n1) =2n,(n >1),2)jf 2(n) - 2f (n-1) = 0 (n>1),J (0)=273If (0)=4;f2(n) 22 f (n 1) =1 f (n),(n >1),f (n)