組合數(shù)學(xué)作業(yè)答案2016

1、組合數(shù)學(xué)作業(yè)第一章 引言Page 13, ex3,4,7,30ex3. 想象一座有64 個(gè)囚室組成的監(jiān)獄，這些囚室被排列成8 8 棋盤。所有相鄰的囚室間都有門。某角落處意見(jiàn)囚室例的囚犯被告知，如果他能夠經(jīng)過(guò)其它每一個(gè)囚室正好一次之后，達(dá)到對(duì)角線上相對(duì)的另一間囚室，那么他就可以獲釋。他能獲得自由嗎？解：不能獲得自由。方法一：對(duì)64 個(gè)囚室用黑白兩種顏色染色，使得橫和豎方向相鄰的囚室顏色不同。則對(duì)角線上兩個(gè)囚室顏色為同黑或同白。 總共偶數(shù)個(gè)囚室， 若能遍歷且不重復(fù)， 則必然是黑出發(fā)白結(jié)束，矛盾。方法二： 64 個(gè)囚室，若要經(jīng)過(guò)每個(gè)囚室正好一次，需要走63 步，即奇數(shù)步。不妨假設(shè)該囚犯在第 1 行第

2、 1 列， 那么到第 8 行第 8 列， 橫著的方向需要走奇數(shù)步， 豎著的方向需要走奇數(shù)步，即總共需要偶數(shù)步。所以不能恰好經(jīng)過(guò)每個(gè)囚室一次到達(dá)對(duì)角線上的囚室。ex4. (a)設(shè)f(n)是用多米諾牌(2-牌)對(duì)2乂 n棋盤作完美覆蓋的個(gè)數(shù)。估計(jì)一下f(1),f(2),f(3),f(4)和 f(5). 試尋找(或證明)這個(gè)計(jì)數(shù)函數(shù) f 滿足的簡(jiǎn)單關(guān)系。利用這個(gè)關(guān)系計(jì)算f(12) 。(b)設(shè)g(n)是用多米諾牌(2-牌)對(duì)3Xn棋盤作完美覆蓋的個(gè)數(shù)。估計(jì) g(1),g(2),g(6).解： (a)f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n)f(4)=f(3)+

3、f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233(b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2) -g(n), g(5)=0, g(6)=41.ex7.設(shè)a和b是正整數(shù)，且 a是b的因子。證明 mx n棋盤有ax b的完美覆蓋當(dāng)且僅當(dāng)a既是m又是n的因子，而b是m或n的

4、因子。(提示：把a(bǔ)x b牌分割成a個(gè)1 x b牌。) 解：充分性。當(dāng)a既是m又是n的因子，而b是m或n的因子，則mXn棋盤有ax b的平 凡完美覆蓋。必要性。假設(shè)mXn棋盤有ax b牌的完美覆蓋。則mXn棋盤必有b牌的完美覆蓋。根據(jù)書 中的定理， b 是 m 的因子或 n 的因子。下面證明 a 既是 m 的因子又是n 的因子。方法一：因?yàn)閍是b的因子，所以ax b牌可以分割成b/a個(gè)ax a牌。mXn棋盤有axa的 完美覆蓋，則必然有ax a牌的完美覆蓋。而 ax a牌是正方形的，所以只有唯一的一種平凡覆蓋方式。從而m 是 a 的倍數(shù)， n 也是 a 的倍數(shù)。方法二：因?yàn)閍是b的因子，不妨設(shè)

5、b=ka。由mXn棋盤有axb牌的完美覆蓋，可任取一 個(gè)完美覆蓋。設(shè)第一行的n個(gè)方格由p個(gè)ax b牌和q個(gè)bx a牌蓋住，則有n=pb+qa=(pk+q)a , 所以 n 是 a 的倍數(shù)。同理， m 也是 a 的倍數(shù)。ex30.考慮堆的大小分別為 10,20,30,40,50的5堆Nim游戲。這局游戲是平衡的嗎？確定玩 家I的第一次取子方案。解：將10,20,30,40,50用二進(jìn)制表示目標(biāo)取出個(gè)數(shù)10:0101010000X20:101001110110=630:1111010011010=2640:1 01000110010X50:1 100101010001010=10平衡0 11010

6、游戲是不平衡的。從上表可以得到，可從20個(gè)堆中取6個(gè)，從30個(gè)堆中取26個(gè)，從50個(gè)堆中取10個(gè)。第2章排列組合P37: ex5,11,27,32,51ex5.確定作為下列各數(shù)的因子的10的最大哥(等價(jià)于用通常的10進(jìn)制表示時(shí)尾部0的個(gè)數(shù)):(a) 50!,(b) 1000!解：(a) 50/5 =10,即 150 中有 10 個(gè) 5 的倍數(shù)。 50/25 = 10/5 =2,即 150 中有 2 個(gè) 25 的 倍數(shù)。從而50!的因子的5的最大哥是10+2=12。因?yàn)?的最大哥比5大，所以5的因子個(gè) 數(shù)決定10的最大哥。(b)同理，1000/5=200, 200/5=40, 40/5=8, 8

7、/5 =1, 1/5 =0,所以 1000!的因子的 10 的最大哥 等于 200+40+8+1=249.ex11.從數(shù)集1,2,2寸形成3個(gè)數(shù)的集合，如果沒(méi)有2個(gè)相連的數(shù)字在同一個(gè)集合中，那么能形成多少個(gè)3個(gè)數(shù)的集合。解法一：任選3個(gè)數(shù)有C(20,3)種方案。兩數(shù)相鄰另一個(gè)分離：1,2和19,20這兩個(gè)相鄰數(shù)對(duì)， 各對(duì)應(yīng)另一不相鄰數(shù)有 17種選擇；2,3到18,19共17種相鄰數(shù)對(duì)，各對(duì)應(yīng)另一不相鄰數(shù)有 16種選擇。三數(shù)相鄰有 18種選擇。202 17 17 16 18 816.3解法二：任選3個(gè)數(shù)有C(20,3)種方案。取兩個(gè)相鄰數(shù)有19種選擇，另一個(gè)與已取出兩數(shù)不同有18種選擇。每三個(gè)相

8、鄰的數(shù)在前一步被計(jì)數(shù)了兩次，需要補(bǔ)回一次。2019 18 18 816 ;3解法三：先放17個(gè)0排成一排。再在18個(gè)空擋中放3個(gè)1,有C(18,3)種方法。在17個(gè)0 和3個(gè)1形成的排列中，數(shù) 1所在的位置abc,即彳#到3個(gè)不相鄰的1到20中的數(shù)。解法四：令3個(gè)數(shù)從小到大排列為 a,b,d,滿足a+1<b, b+1<d。令B=b-1,D=d-1,則a<B<D 為從1到18中的數(shù)，且無(wú)不相鄰限制。81618ex27. 5個(gè)沒(méi)有區(qū)別的車放在8 8棋盤上，使得沒(méi)有車能夠攻擊別的車并且第一行和第一列都不空的放置方式有多少？解：方法一：5個(gè)橫坐標(biāo)的選擇方案有 C(7,4)種，因

9、為第1列必選；5個(gè)縱坐標(biāo)的選擇方案有C(7,4)種，因?yàn)榈谝恍斜剡x；橫縱坐標(biāo)的配合有5!種，因?yàn)闄M坐標(biāo)固定，縱坐標(biāo)全排列。所以總的方案數(shù)為 C(7,4) C(7,4) 5!=147000.方法二：分兩種情況：一是選第一行第一列， 其它4個(gè)在其它7行7歹U;有C(7,4) C(7,4) 4! 種方案。二是第一行 2至8列中選一個(gè)，第一列 2至8行中選一個(gè)，其它3個(gè)在其它6行6 列；有 7 7 C(6,3) C(6,3) 3!。總方案數(shù)為 C(7,4) C(7,4) 4! + 7 7 C(6,3) C(6,3) 3! = C(7,4) C(7,4) 5! = 147000。ex32.確定下面的多重

10、集合的11排列的數(shù)目：S=3 a,4b,5c。解：多重集S=3 a,4 b,5 c的11排列可分為3個(gè)部分：2 a,4 b,5 c:2!4!5!6930；3 a,3 b,5 c:11!9240；3!3!5!3 a,4 b,4 c:11!11550；3!4!4!共有 6930+9240+11550=27720 個(gè)排列。ex37. 一家面包店銷售 6種不同類型的酥皮糕點(diǎn)。如果該店每種糕點(diǎn)至少有一打，那么可能配置成多少打不同類型的酥皮糕點(diǎn)？如果在一盒中每種糕點(diǎn)至少有一塊，又能有多少打？解：(1) 12個(gè)球與5個(gè)間隔的全排列有 C(12+5,5)個(gè)，所以總共可以配成 C(17,5)種12個(gè)一盒的酥 皮

11、蛋糕盒。(2)每種蛋糕至少一塊，則盒中已有6塊蛋糕。還需要放入 6塊蛋糕。等價(jià)于6個(gè)球與5個(gè)間隔全排列，有 C(6+5,5)種方案。所以總共可以配成C(11,5)種12個(gè)一盒且每種蛋糕至少有一個(gè)的酥皮蛋糕盒。ex51.考慮大小為2n的多重集合n a,1,2,3,n搠定它的n組合數(shù)。解：令 S=n a,1,2,3,n.方法一：1,2,n沖取k個(gè)有C(n,k)種方案，再取n-k個(gè)a得到S的n組合。所以方案數(shù)是C(n,0)+C(n,1)+C(n,n)=2方法二：1,2,n腑全體組合有2n個(gè)，1,2,n胸任何一個(gè)組合配上相應(yīng)個(gè)數(shù)的a可以得到S的一個(gè)n組合。ex52.考慮大小為3n+1的多重集合n a,

12、nb,1,2,3,n+1聊定它的n組合數(shù)。解：在1,2,n+1中取k個(gè)有C(n+1,k)種方案，n個(gè)a和n個(gè)b中取n-k個(gè)組合有C(n-k+1,1)=n -k+1 種方案。方法一 ：C(n+1,k) (n-k+1)=(n+1) C(n,k),對(duì) k 從 1 到 n 求和得到(n+1) 2n種方案。方法二：因?yàn)?x+1) n+1= 2 C(n+1,k)x n-k+1 ,兩邊同時(shí)對(duì) x 求導(dǎo)，得到(n+1)(x+1) n= 2C(n+1,k) (n-k+1)xn-k。令 x=1 ,便得到 2 C(n+1,k) (n-k+1)=(n+1) 2n。第 3 章 鴿巢原理P50: ex4,7,11,13,

13、16ex4.證明：如果從集合1,2,2nf選擇n+1個(gè)整數(shù)，那么總存在兩個(gè)數(shù)它們之間相差1.證明：將2n個(gè)數(shù)分成n個(gè)集合：1,2,3,4, ,2n1,2n。那么任取的n+1個(gè)數(shù)至少有兩個(gè) 在同一個(gè)集合中，它們之間相差1.ex7. 證明：對(duì)任意給定的 52 個(gè)整數(shù)，存在兩個(gè)整數(shù)，要么兩者的和能被 100 整除，要么兩者的差能被100 整除。證明：構(gòu)造51 個(gè)鴿巢：模 100 余 0 的一個(gè)鴿巢；模 100 余 1 和余 99 的一個(gè)鴿巢；模 100余2和余98的一個(gè)鴿巢；模100余3和余97的一個(gè)鴿巢；以此類推 ；模100余49和余51 的一個(gè)鴿巢； 模 100 余 50 的一個(gè)鴿巢。 52 個(gè)

14、數(shù)， 至少有兩個(gè)在同一個(gè)鴿巢。若這兩個(gè)數(shù)模 100 同余，則兩個(gè)數(shù)的差是100 的倍數(shù)；若這兩個(gè)數(shù)模100 不同余，則這兩個(gè)數(shù)的和是100 的倍數(shù)。ex11. 一個(gè)學(xué)生有37 天來(lái)準(zhǔn)備考試。根據(jù)以往經(jīng)驗(yàn)，她知道她需要的學(xué)習(xí)時(shí)間不超過(guò)60 小時(shí)。她還希望每天至少學(xué)習(xí)一個(gè)小時(shí)。證明，無(wú)論她怎么安排學(xué)習(xí)時(shí)間 (每天學(xué)習(xí)的時(shí)間是 整數(shù)小時(shí))，都存在連續(xù)若干天，在此期間她恰好學(xué)習(xí)了13 個(gè)小時(shí)。證明：設(shè) ai 是這名學(xué)生從第1 天到第 i 天學(xué)習(xí)的總小時(shí)數(shù)，那么0<a1<a2< - a36<a37 6013+ a1<13+ a2<- -13+ a36<13+ a

15、37<73于是a1,a2,，§6,a37和13+ a1,13+ a2,，13+ <36,13+ a37共74個(gè)數(shù)取值在1至U 73之間。一定有兩個(gè)數(shù)相同，且這兩數(shù)一定是13+ai=ajo于是從第i+1天到第j天這名學(xué)生學(xué)習(xí)了13小時(shí)。ex13. 設(shè) S 是平面上 6 個(gè)點(diǎn)的集合，其中沒(méi)有3 個(gè)點(diǎn)共線。給由 S 的點(diǎn)所確定的 15 條線段著色，將它們或者著成紅色，或者著成藍(lán)色。證明：至少存在兩個(gè)由 S 的點(diǎn)所確定的三角形或者是紅色三角形或者是藍(lán)色三角形。證法一：六個(gè)點(diǎn) ABCDEF 至少形成一個(gè)同色三角形，設(shè)此三角形為 ABC 且為紅色。(1) 若 DEF 同色，則得到另一

16、同色三角形。(2) 否則 DEF 必有一條藍(lán)色邊，設(shè)為 DE 。考慮從 D,E 兩點(diǎn)分別到 A,B,C 三點(diǎn)的連線。(2.(1) 或E有兩條紅色邊連到A,B或C,將得到另一紅色三角形。(2.(2) 否則 D,E 都至少有兩條藍(lán)色邊連接到 A,B 和 C 上。 D,E 必各有一條藍(lán)色邊連到 A,B 和C三點(diǎn)的同一點(diǎn)(設(shè)為C)上，則DEC是藍(lán)色三角形。證法二：任相鄰兩條邊給一個(gè)數(shù)，若同色則給1 ，否則給 0。(1) 任何一個(gè)同色三角形對(duì)應(yīng)數(shù)1,1,1 ；任何一個(gè)不同色三角形對(duì)應(yīng)數(shù)1,0,0。六點(diǎn)共有C(6,3)=20 個(gè)三角形。(2) 從一個(gè)點(diǎn)出發(fā)的邊有5 條，共 10 對(duì)，至少有4 對(duì)同色，對(duì)應(yīng)

17、數(shù)的和大于等于4，所有點(diǎn)對(duì)應(yīng)數(shù)的和大于等于24 。若沒(méi)有同色三角形，則所有數(shù)的和是20；若只有一個(gè)同色三角形，則所有數(shù)的和是22. 所以至少有兩個(gè)同色三角形。(假設(shè)自己ex16. 證明：在一群 n>1 個(gè)人中，存在兩人，他們?cè)谶@群人中有相同數(shù)目的熟人不是自己的熟人) 。證明：n個(gè)人，每人的熟人數(shù)記為a,即ai,a2,a,取值于0到n-1之間。由于有人認(rèn)識(shí)0個(gè)人和有人認(rèn)識(shí) n-1 個(gè)人不會(huì)同時(shí)出現(xiàn)。所以這n 個(gè)數(shù)的取值只有n-1 種，從而必有兩人熟人數(shù)相同。第 4 章 生成排列和組合ex 6, 7, 23, 24, 33, 52ex6.確定1,2,，8的下列排列的逆序列。(a) 35168

18、274 (b)83476215解： (a) 24040010(b) 65113210ex7.構(gòu)造1,2,，8的排列，使得其逆序列是(a) 25502110 (b) 66142100解： a) 48165723 b) 73658412ex23. 確定下列 9 階反射 Gray 碼中 9 元組的直接后繼(a) 010100110(b) 110001100(c) 111111111解：后繼為(a) 010100111 (b) 110001101 (c) 111111101ex24. 確定下列 9 階反射 Gray 碼中 9 元組的直接前趨(a) 010100110(b) 110001100(c) 1

19、11111111解：前驅(qū)為 (a) 010100010 (b) 110000100 (c) 111111110ex33.子集2489出現(xiàn)在1,2,3,4,5,6,7,8,9的4-子集的字典序的哪個(gè)位置上？解： 2489 的位置為 97581443ex52.驗(yàn)證二進(jìn)制n元組an-1an-2a°位于 Gray碼表的位置 k處，其中 k確定如下：對(duì)i=0,1，,n-1,若 an-1+ ai 是偶數(shù)則 bi=0 ,否則 bi=1,則有 k=(bn-1 b?！?。證明：為方便，記bn-1b0=f(an-1an-2a°),其中對(duì)i=0,1, -n,若an-1+ ai是偶數(shù)則 bi=0 ,

20、 否則bi=1 。數(shù)學(xué)歸納證法一：當(dāng)二進(jìn)制位數(shù)n 1 時(shí)，公式成立；假設(shè)當(dāng)位數(shù)為n 1時(shí)，公式成立，即an-2a0在Gray碼表中位于k'處，k'環(huán)26)2,其中 Cn-2 , C0 = f( an-2a0)?？紤]n位二進(jìn)制碼 an-1an-2- a0o當(dāng)an-1=0時(shí)，根據(jù)定義，bn-1=0 ,且bi=ci (i=n-2,0)再根 據(jù)Gray碼的遞歸構(gòu)造，以及an-1=0 ,可知an-1an-2a0在Gray碼中的位置是(Cn-2C0)2 = (bn-1 b0)2。當(dāng)an-1=1時(shí)，根據(jù)定義，bn-1=1,且bi=1- ci (i=n-2,0)根據(jù)Gray碼的遞歸構(gòu)造，以及a

21、n-1=1 ,可知an-1an-2- a0在Gray碼中的位置是2n - (Cn-2C0)2- 1 = (12l)(Cn-2C0)2= (bn-1 b0)2,其中1-1是n-1個(gè)1。數(shù)學(xué)歸納證法二：考慮 n 階反射 Gray 碼。在n階反射Gray碼中，第一個(gè)n元組是00,對(duì)應(yīng)f(00) = 0 ”蹣足位置關(guān)系，命 題成立。(2)假設(shè) n元組an-ian-2-ao100在 Gray碼中的位置是(bn-ibo)2,其中bn-ibo=f(an-ian-2 ao)。(2.(1) b0=0 時(shí)，(an-ian-2 - a0)=0, an-ian-2aO 的下一個(gè) Gray 碼是將 a0 改為 1-a0

22、,即an1an2Ka0°它的位置是(bn-ibi0)2+i=(bn-ibii)2,f( an1an2Ka0)=bn-ibii,滿足位置關(guān)系，命題成立。(2.(2) 0=1時(shí)，(an-ian-2a0)=1。取j為an-ian-2aO中從右往左若干個(gè)連續(xù)的 0后面的第 一個(gè)1的位置，即 ajaj-r- a0=10 - O o此時(shí)，加=切-仔=b0=1, bj+i=0。注意到an-ian-2 a。下一個(gè) Gray 碼是 an 1K d 1aj K a0,其位置應(yīng)該是(bn-i bO)2+1=(bn-i bj+210 0)2。令 cn-i C0 = f( an iK aj iaj K a&#

23、176;),則 cj=cj-i=-= c0=0, cj+i=1, ck= bk, (k = j+2,n-1),滿足位置關(guān)系。第6章容斥原理ex5, ex13, ex17, ex26, ex305.確定多重集 a,4 b,5c,7d的10-組合個(gè)數(shù)。解：令全集U=(x i ,x2, x3, x4)| xi+x2+x3+x 4=10, xi, x2, x3, x4 0 A=(x 1, x2, x3, x4)| xi+x2+x3+x4=10, xi, x3, x4 0, x2 5 B=(x 1, x2, x3, x4)| xi+x2+x3+x4=10, xi, x2, x4 0, x3 6C=(x

24、1, x2, x3, x4)| xi+x2+x3+x4=10, xi, x2, x3 0, x4 8其中 |U|=10 3,冏=5 3 舊=4 3 ,|C|=2 3, 3333|A B|=|A C|=|B C|=|A B C|=0133本題所求10-組合的個(gè)數(shù)為C |二|U|-|A|-|B|-|C|+|A B|+|A C|+|B C|-|A B C|二=185 13.確定1,2,觸至少有一個(gè)奇數(shù)在它的自然位置上的排列數(shù)。解：方法一對(duì)于i=1,3,5,7,定義Ai=i在位置i上AiU A3UA5U A7U A9 = C(5,1)8! -C(5,2)7!+C(5,3)6! -C(5,4)5!+C(

25、5,5)4! = 157824.方法二將計(jì)算沒(méi)有奇數(shù)在自然位置上的問(wèn)題轉(zhuǎn)化為帶禁止位置的排列，共5個(gè)禁止位置分布在對(duì)角線上。c=C(5,1), r2=C(5,2), r 3=C(5,3), r4=C(5,4), r5=C(5,5),6= - = r9=0.9!-(9!- ri8!+ r27!- r36!+ r45!- r54!)= C(5,1)8! -C(5,2)7!+C(5,3)6! -C(5,4)5!+C(5,5)4!=157824.17.確定多重集 S=3 a,4 b,2 c的排列數(shù)，其中，對(duì)每種類型的字母，同類型的字母不能連 續(xù)出現(xiàn)。(例如，abbbbcaca是不允許的，但 abbba

26、cacb可以。)解：令 U=S的全排列A=3個(gè)a連續(xù)出現(xiàn)的排列B=4個(gè)b連續(xù)出現(xiàn)的排列C=2個(gè)c連續(xù)出現(xiàn)的排列貝 U|U|=9!/(3!4!2!)=1260|A|=(1+4+2)!/(1!4!2!)=105 |B|=(3+1+2)!/(3!1!2!)=60 |C|=(3+4+1)!/(3!4!1!)=280|A B|=(1 + 1+2)!/(1!1!2!)=12 |A C|=(1+4+1)!/(1!4!1!)=30 |B C|=(3+1 + 1)!/(3!1!1!)=20 |A B C|=(1 + 1+1)!/(1!1!1!)=6于是同類型字母不能連續(xù)出現(xiàn)的排列數(shù)有| A B C | =|U|

27、-|A|-|B|-|C|+|A B|+|A C|+|B C|-|A B C|=1260-105-60-280+12+30+20 -6=871.26.計(jì)算1,2,，6排列 i1i2i3i4i5i6 的個(gè)數(shù)，其中 i1 1,2,3, i2 1, i3 1, i5 5,6, i6 5,6。 解：XXXXXXXXX帶禁止位置的排列，放置方法數(shù)是6!-門5!+r24!-r33!+r42!-r51!,由1=9,2=2 2+2+5 4=26,3=4 4+5 2=26,4=4 2, r5=0, r6=0, 得到排列數(shù)為 6!-9 5!+26 4!-26 3!+8 2!-0 1!+0 0!=124.30.多重集

28、3 a,4 b,2 c,1d存在多少循環(huán)排列，對(duì)每種類型的字母，該類型的所有字母不連 續(xù)出現(xiàn)？解：方法一：固定d,其它元素排列與17題相同，所以有871種循環(huán)排列方式。方法二：令U=S的所有循環(huán)排列A=3個(gè)a連續(xù)出現(xiàn)的循環(huán)排列B=4個(gè)b連續(xù)出現(xiàn)的循環(huán)排列C=2個(gè)c連續(xù)出現(xiàn)的循環(huán)排列則 |U| = (3+4+2+1 -1)!/(3!4!2!) = 9!/(3!4!2!) = 1260|A| = (1+4+2+1 -1)!/(1!4!2!) = 7!/(4!2!) = 105|B| = (3+1+2+1 -1)!/(3!1!2!) = 6!/(3!2!) = 60|C| = (3+4+1+1 -1

29、)!/(3!4!1!) = 8!/(3!4!) = 280|A B| = (1 + 1+2+1 -1)!/(1!1!2!) = 4!/2! = 12 |A C| = (1+4+1 + 1 -1)!/(1!4!1!) = 6!/4! = 30|B C| = (3+1+1 + 1 -1)!/(3!1!1!) = 5!/3! = 20|A B C| = (1 + 1 + 1+1 -1)!/(1!1!1!) = 3! = 6于是同類型字母不能連續(xù)出現(xiàn)的排列數(shù)有| A B C | =|U|-|A|-|B|-|C|+|A B|+|A C|+|B C|-|A B C|=1260-105-60-280+12+

30、30+20 -6=871.31.多重集S=2 a,3 b,4 c,5d存在多少循環(huán)排列，對(duì)每種類型的字母，該類型的所有字母不 連續(xù)出現(xiàn)？解：令 U=S的所有循環(huán)排列A=2個(gè)a連續(xù)出現(xiàn)的循環(huán)排列B=3個(gè)b連續(xù)出現(xiàn)的循環(huán)排列C=4個(gè)c連續(xù)出現(xiàn)的循環(huán)排列D=5個(gè)d連續(xù)出現(xiàn)的循環(huán)排列則 |U| = (2+3+4+5 -1)!/(2!3!4!5!) = 13!/(2!3!4!5!) = 180180|A| = (1+3+4+5 -1)!/(1!3!4!5!) = 12!/(1!3!4!5!) = 27720|B| = (2+1+4+5 -1)!/(2!1!4!5!) = 11!/(2!1!4!5!) =

31、 6930|C| = (2+3+1+5 -1)!/(2!3!1!5!) = 10!/(2!3!1!5!) = 2520|D| = (2+3+4+1 -1)!/(2!3!4!1!) = 9!/(2!3!4!1!) = 1260|A B| = (1 + 1+4+5 -1)!/(1!1!4!5!) = 10!/(1!1!4!5!) = 1260|AC| = (1+3+1+5-1)!/(1!3!1!5!)=9!/(1!3!1!5!)=504|AD| = (1+3+4+1-1)!/(1!3!4!1!)=8!/(1!3!4!1!)=280|B C| = (2+1+1+5-1)!/(2!1!1!5!) =

32、8!/(2!1!1!5!) = 168|BD| = (2+1+4+1-1)!/(2!1!4!1!)=7!/(2!1!4!1!)=105|CD| = (2+3+1+1-1)!/(2!3!1!1!)=6!/(2!3!1!1!)=60|ABC|=(1 + 1 + 1+5-1)!/(1!1!1!5!) = 7!/(1!1!1!5!) = 42|ABD|=(1 + 1+4+1-1)!/(1!1!4!1!) = 6!/(1!1!4!1!) = 30|ACD|=(1+3+1+1-1)!/(1!3!1!1!) = 5!/(1!3!1!1!) = 20|BCD|=(2+1 + 1+1-1)!/(2!1!1!1!

33、) = 4!/(2!1!1!1!) = 12|A BCD|=(1+1 + 1 + 1-1)!/(1!1!1!1!) = 3!/(1!1!1!1!) = 6于是同類型字母不能連續(xù)出現(xiàn)的排列數(shù)有=13!/(2! 3! 4! 5!) - 12!/(3! 4! 5!) - 11!/(2! 4! 5!)-10!/(2! 3! 5!) - 9!/(2! 3! 4!) + 10!/(4! 5!) + 9!/(3! 5!) +8!/(3! 4!) + 8!/(2! 5!) + 7!/(2! 4!) + 6!/(2! 3!)- 7!/5! - 6!/4!-5!/3! - 4!/2! + 3!=144029第7章

34、遞推關(guān)系和生成函數(shù)ex. 9,46,47; 13,17,25,9.令hn等于1行n列棋盤的方格能夠用紅、白和藍(lán)色著色并使得沒(méi)有兩個(gè)涂成紅色的方格 相鄰的著色方案數(shù)。求出并驗(yàn)證hn所滿足的遞推關(guān)系。然后找出hn的公式。解：棋盤的第一個(gè)格子有3中著色方法：(1)著紅色，則第二個(gè)格只能著藍(lán)色或者白色，此時(shí)的方案數(shù)為2hn-2；(2)著藍(lán)色或者白色，此時(shí)的方案數(shù)為2hn-i；因此,hn = 2h n-i+ 2h n-2,且 ho = 1, hi = 3.求hn：特征方程：x2-2x-2=0解得：xi=1+ 3 , x2=1-.3則有：hn = C1(1+ ./3)n+ C2(1- , 3)n代入初始條

35、件，ho = C1 + C2=1h1 =C1(1 + ,3 )+C2(1- -.3 )=3解得，=1 立 =1 立1-2 T ,c2- 2 號(hào)因此，hn = (1 4)(13)n (1 -)(13)n.46 .求解非齊次遞推關(guān)系hn = 6hn-1- 9hn-2+2n, (n 2), ho = 1, h1 = 0.解：對(duì)于齊次遞推關(guān)系：hn = 6hn-1- 9hn-2特征方程：x2-6x+9=0解得：x1=x2=3一般解：hn = C13n+ C2 n 3n對(duì)于非齊次遞推關(guān)系，其特解為：hn = a n + b代回遞推關(guān)系，比較系數(shù)得a=1/2, b=3/2,此時(shí)特解 hn = (1/2)n

36、+3/2因此，hn = C1 3n+ C2 n 3n+(1/2)n+3/2代入初始條件，ho = C1+3/2=1h1 =3c1+3c2+1/2+3/2=0解得，C1=-1/2C2=-1/6所以，hn = (-1/2-n/6)*3 n+n/2+3/2.47 .求解非齊次遞推關(guān)系hn = 4hn-1- 4hn-2+3n+1, (n 2), ho = 1, h1 = 2.解：對(duì)于齊次遞推關(guān)系：hn = 4hn-1- 4hn-2特征方程：x2-4x+4=o解得：x1=x2=2一般解：hn = C12n+ c2n2n對(duì)于非齊次遞推關(guān)系，其特解為：hn = an + b代回方程，比較系數(shù)得a=3, b=

37、13,此時(shí)特解 hn= 3n+13因此，hn =(C1+C2n)2 n+3n+13代入初始條件，h0 = ci+13=1hi =2(C1+C2)+3+13=2解得，C1=-12C2=5所以，hn = (5n-12) *2n+3n+13.13.確定下列每個(gè)序列的生成函數(shù)J )/-a o 111In-，(a i5 a real number)解：(a) g(x) = 1+Cx+C2x2+-.+Cnxn+.=1+cx+(cx) 2+(Cx)n+ .=1/(1 -Cx)(b) g(x) = 1-x+x2-x3+ +(-1)nxn+=1+(-x)+(-x)2+(-x)3+(-x)n+ x x2 L (

38、1)nxn L12n=1/(1+x)(C)g(x)=01 ( x) 2 x2 L n ( x)n L-0=(1 -x)(d) g(x) = 1+1/1!*x+1/2!*x 2+ - +1/n!*x n+ =ex(e) g(x) = 1- x/1! +x 2/2! + +()n xn/n! +=1+(-x)/1! +(-x)2/2! + +x)n/n! +=e-x17.確定蘋果、橘子、香蕉和梨的袋裝水果的袋數(shù) hn的生成函數(shù)，其中各袋要有偶數(shù)個(gè)蘋果, 最多兩個(gè)橘子，3的倍數(shù)個(gè)香蕉，最多一個(gè)梨。然后從該生成函數(shù)求出hn的公式。解：序列ho,h1, 的生成函數(shù)是g(x) = (1+x 2+x4+ -

39、 ) (1+x+x 2) (1+x 3+x6+ - ) (1+x)=1/(1-x2)*(1+x+x 2)*(1+x)*1/(1 -x3)=1/(1 -x)2=(n 1)xn .n 0因此，hn =n+1.17確定蘋果、橘子、香蕉和梨的袋裝水果的袋數(shù)hn的生成函數(shù)，其中各袋要有偶數(shù)個(gè)蘋果，至少兩個(gè)橘子，3的倍數(shù)個(gè)香蕉，最多一個(gè)梨。然后從該生成函數(shù)求出hn的公式。解：序列h0,hi, 的生成函數(shù)是g(x) = (1+x 2+X4+ ) (x2+x3+- -) (1+x 3+x6+ - ) (1+x)=1/(1-x2) * x2/(1 -x) * 1/(1 -x3) * (1 -x2)/(1-x)2

40、x=32(1 x) (1 x x )11331二239 1 x (1 x) (1 x) x1 nn=-x 1 3(n 1) 39n 02其中1n 2n 1 n 213(n1) 3,驗(yàn)證(ho, h1, h2, h3)=(0,0,1,2).9225.如果偶數(shù)個(gè)方格被涂成紅色以及奇數(shù)個(gè)方格被涂成白色，試確定用紅、白、藍(lán)和綠為1行n列棋盤的方格著色的方案數(shù)hn。解：設(shè)滿足如題要求的 1行n列棋盤的方格著色的方案數(shù)為hn.則序列h0,h1,的指數(shù)生成函數(shù)是g(x尸(1+x2/2!+x4/4!+ )(x/1!+x/3!+x5/5!+)(1+x/1!+x 2/2!+ -) (1+x/1!+x2/2!+ )

41、=1/4*(ex+e-x) (ex-e-x)ex ex=1/4(e4x - 1) nn1 n xn 1 x=41=44 n 0 n! n 1 n!因此，hn = 4n-1(n 1), h0 = 0.26.如果偶數(shù)個(gè)方格被涂成紅色以及偶數(shù)個(gè)方格被涂成綠色，試確定用紅、藍(lán)、綠和橘黃為1行n列棋盤的方格著色的方案數(shù)。解：設(shè)滿足如題要求的1行n列棋盤的方格著色的方案數(shù)為hn.則序列h0,h1,的指數(shù)生成函數(shù)是g(x尸(1+x2/2!+x4/4!+ ) (1+X/2!+x4/4!.) (1+x/1!+x 2/2!+ )(1+x/1!+x2/2!+ )=1/4*(ex+e-x) (ex+e-x)ex ex

42、=1/4(e4x+2e2x+1)n1 n x4 4 n o n!n2 2nx- =1 1(4n 0 n!44 n 0n2 2n). n!因此，hn = 4n-1+2n-1(n 1), h0 = 1.第14章Polya計(jì)數(shù)Ex22.用兩種顏色對(duì)一個(gè)非正方形矩形的頂點(diǎn)進(jìn)行著色，求不等價(jià)的著色數(shù). 如果用p種顏色染色有多少種方案.解：不考慮翻轉(zhuǎn)變換群： 20,21。其中20是恒等變換，21旋轉(zhuǎn)180度的變換。給矩形的4個(gè)頂點(diǎn)順時(shí)針依次標(biāo)號(hào)1,2,3,4。則有20=1234,21=1324。從而用兩種顏色染色不等價(jià)的著色數(shù)是(24+22)/2=10考慮翻轉(zhuǎn)變換群：20, 21, x, y。其中20是恒

43、等變換，21旋車專180度的變換，x是沿X軸翻轉(zhuǎn)，y是沿y軸翻轉(zhuǎn)。給矩形的4個(gè)頂點(diǎn)順時(shí)針依次標(biāo)號(hào)1,2,3,4。則有20=1234,21=1324,x =1423, y=1234。從而用兩種顏色染色不等價(jià)的著色數(shù)是(24+22+22+22)/4=7如果用p中顏色，則只需將上面的2換成p。Ex26.用4個(gè)紅色珠子與3個(gè)藍(lán)色珠子鑲成項(xiàng)鏈，有多少種不同項(xiàng)鏈？解：項(xiàng)鏈需要考慮翻轉(zhuǎn)。 70, 71,，76, 1,2，7 。給項(xiàng)鏈上均勻分布的7個(gè)頂點(diǎn)順時(shí)針依次標(biāo)號(hào) 1,2,3,4,5,6,7。則有 70=1234567,7i=1234567, i=1,2,3,4,5,6,1=1273645,|C( 70)

44、|二C(7,3), |C( 7i)|=0, |C( i)|=C(3,2)從而不等價(jià)的著色數(shù)是(C(7,3)+6 0+7 3)/14=4Ex32.用3種顏色對(duì)正六邊形頂點(diǎn)著色，求不等價(jià)著色數(shù).(只考慮旋轉(zhuǎn))解：61 = 012345 , 62= 024135 , 63 = 031425不等價(jià)著色方案數(shù)：(36+31+32+33+32+31)/6=130.第10章組合設(shè)計(jì)Ex17.證明x3+x+1不能在域Z2中分解(具有Z2中系數(shù)的多項(xiàng)式的乘積),然后利用該多項(xiàng)式構(gòu)造具有23=8個(gè)元素的域.令i為該多項(xiàng)式添加到 Z2中的根，然后做下列計(jì)算：(1) (1+i)+(1 + i+i2),(2) (1 + i2)+(1+i2),(3) i-1,(4) i2 (1+i+i2),(5) (1+i)(1+i+i2),(6) (1 + i)-1.注：i 滿足 i3+i+1=0。解：(1)由于域Z2中只有兩個(gè)元素 0和1,而03+0+1=1, 13+0+1=1,所以x3+x+1在Z2中沒(méi) 有根，即x3+x+1不能以非平凡的方法分解；(2)令i為該多項(xiàng)式添加到 Z2中的根，則有i3=-i-1= i+1。在集合a+bi+ci 2: a