級組合數(shù)學復習題解答PPT學習教案

1、會計學1級組合數(shù)學復習題解答級組合數(shù)學復習題解答2 (2) 所選出的6根木棍實際上可將這20根排成一行的木棍分割成7段(加上首和尾).設所選左邊第1根木棍的左側(cè)有x1根未被選中的木棍；在第1 與第2根所選木棍之間有x2根未被選中的木棍；在第5 與第6根所選木棍之間有x6根未被選中的木棍；在第6根所選木棍的右側(cè)有x7根未被選中的木棍，則由于沒有兩根選出的木棍是相鄰的，所以=， 12345671714001,2,3,6ixxxxxxxxxxi第1頁/共48頁3作變量代換則原方程變成，11771,2,3,6iiyxyxyxi 123456790,1,2,3,7iyyyyyyyyi這個方程的非負整數(shù)解

2、的個數(shù)即為所求的選擇數(shù)97115500599第2頁/共48頁4(3) 同(2)中的分析，此時有不定方程=， 12345671714002,2,3,6ixxxxxxxxxxi4711021044仿照(2)，這個方程的非負整數(shù)解的個數(shù)即為所求的選擇數(shù)第3頁/共48頁5 2. (1) 在2n個物體中有n個是相同的，則從這2n個物體中選取n個的方法有幾種？ (2) 在3n +1個物體中有n個是相同的，則從這3n +1個物體中選取n個的方法有幾種？解 (1) 若選出的物體有 個不 (0,1,2, )k kn相同相同,則其余則其余n - - k個是相同的個是相同的,所以選取的方法數(shù)為所以選取的方法數(shù)為 2

3、01nnnnn 212212121122201nnnnnn(2) 類似于(1)的分析可知，所以選取的方法數(shù)為第4頁/共48頁6 3. 用 種顏色去涂 棋盤，每格涂一種顏色，求使得相鄰格子異色，首末兩格也異色的涂色方法數(shù). (2)m m 1 ()n nm解 用hn表示所求方法數(shù).易知 2(1).hm m用m種顏色去涂 棋盤，每格涂一種顏 1 ()n nm色，使得相鄰格子異色的涂色方法數(shù)有 1(1)nm m種,其中使得首末兩格同色的涂色方法有 種,所以 1nh 11(1) (2)nnnhm mhn從而第5頁/共48頁7 111222(1)(1)(1)( 1)nnnnnnhm mhm mm mh 1

4、2333(1)(1)(1)( 1)nnnnm mm mm mh 12322(1)(1) ( 1)(1)( 1)(1)nnnnm mm mm mm m 2332(1)(1)(1) ( 1)(1)( 1)nnnnm mmmm 12(1)( 1)(1)(1)1nnmm mm (1)( 1) (1)nnmm第6頁/共48頁8 4. 用 種顏色去涂 棱錐的n + 1個頂點,每個頂點涂一種顏色，求使得棱錐的每條棱的兩個端點異色的涂色方法數(shù) (3)m m (3)n n(, ).K m n 解 設V是一個n棱錐,則可依如下兩個步驟去完成V的n + 1個頂點的涂色工作: 先涂頂點先涂頂點v0,有有m種涂色方法種

5、涂色方法;然后用異于然后用異于v0顏色的顏色的m - - 1種顏色種顏色去涂頂點序列去涂頂點序列v1， v2， vn, 使得相鄰頂點異色使得相鄰頂點異色且首末兩個頂點也異色且首末兩個頂點也異色.0v1v2v3vnv第7頁/共48頁9由上題可知,完成此步驟的方法有 (2)( 1) (2)nnmm種，由乘法原理,得所求涂色方法數(shù)為 (, )(2)( 1)(2)nnK m nm mm m第8頁/共48頁10na解解 所所求求種種類類數(shù)數(shù) 的的母母函函數(shù)數(shù)為為32321111(1)111(1)xxxxxx 24236( )(1)(1)(1)(1)G xxxxxxxx 5. 將充分多的蘋果、香蕉、橘子和

6、梨這4種水果裝袋，要求各袋有偶數(shù)個蘋果，最多2個橘子，3的倍數(shù)個香蕉，最多1個梨. 如果每袋裝n個水果，求裝袋的種類數(shù).第9頁/共48頁11001(1)nnnnnxnxn 1.nan 所所以以第10頁/共48頁12 6. 把n個相異的球放到4個相異盒子 中，求使得 含有奇數(shù)個球， 含有偶數(shù)個球的不同的放球方法數(shù).1234,A A A A1A2A則數(shù)列 對應的指母函數(shù)為na解 設滿足條件的放球方法數(shù)為.na3524232( )()(1)3!5!2!4! (1)2!3!exxxxGxxxxx 第11頁/共48頁13222xxxxxeeeee 414xe 1144!nnnxn 114!nnnxn 1

7、4.nna 所以第12頁/共48頁14 7. 由數(shù)字1至9組成的每種數(shù)字至少出現(xiàn)1次的 位數(shù)有多少個？ (9)n n解 設所求的數(shù)為an,則an的指母函數(shù)為 9(9)09( 1)kk xkek 2399( )()(1)2!3!xexxG xxe 9009( 1)(9)!nknknxknk 9009( 1)(9)!nknnkxknk 909( 1)(9)knnkakk所以第13頁/共48頁15 8. 由字母a,b,c,d,e組成的總字母數(shù)為n的單詞中，要求a與b的個數(shù)之和為偶數(shù)，求這樣的單詞的個數(shù). 解 這樣的單詞有兩類：一類包括偶數(shù)個a與偶數(shù)個b；另一類包括奇數(shù)個a與奇數(shù)個b.設所求的數(shù)為an

8、,則an的指母函數(shù)為 242323352323( )(1) (1)2!4!2!3! () (1)3!5!2!3!exxxxG xxxxxxxx第14頁/共48頁16 223322xxxxxxeeeeee故 50011()(5)22!nnxxnnnxxeenn 0512!nnnxn 512nna第15頁/共48頁17 9.有多少個長度為n的0與1串, 在這些串中, 既不包含子串010，也不包含子串101？解 設這種數(shù)串的個數(shù)為 將滿足條件的數(shù)串分為兩類： ,nf1224ff則則，3n 時時， (1) 最后兩位數(shù)字相同. 這種長度為n的數(shù)串可由長度為n-1的串最后一位數(shù)字重復一次而得，故這類數(shù)串的

9、個數(shù) 1nf ； (2) 最后兩位數(shù)字不同. 這種長度為n的數(shù)串可由長度為n-2的串最后一位(設為a)重復一次，再加上與a不同的數(shù)字而得, 故這類數(shù)串的個數(shù)為 2.nf 第16頁/共48頁18于是得遞推關系12122, 4 nnnfffff 由Fibonacci數(shù)列,得通解121515()()22nnnfcc代入初值,得 125555,55cc1121515 ()()225nnnf所所以以第17頁/共48頁19 10. 由0,1,2,3組成的長度為n的序列中，求含偶數(shù)個0的序列個數(shù)和含奇數(shù)個0的序列個數(shù). 解 設an為含偶數(shù)個0的序列個數(shù)，bn為含奇數(shù)個0的序列個數(shù).則有 114 3nnnnn

10、nababa解得1122 4,nnna1144(22 4)nnnnnnba112 42nn第18頁/共48頁20 11. 十個數(shù)字十個數(shù)字(0到到9)和四個運算符和四個運算符( +，- -，*，/ )組成組成14個元素，求由其中的個元素，求由其中的n個元素的排列構(gòu)成一個元素的排列構(gòu)成一形式算術表達式的個數(shù)形式算術表達式的個數(shù). 解 令an表示n個元素排列成算術表達式的數(shù)目，則 1212104010, 120 nnnaaaaa解得133 65133 65(565)(565)5252nnna第19頁/共48頁21 12. 在一圓周上均勻地取2n個點，用n條兩兩不相交的弦把這些點配成對，求所有這種配

11、對的方式數(shù). 解 設所求配對的方式數(shù)為hn,則h1 = 1,則h0 = 1,設2n個點依次為， ， ， ，1222,knvvvv連接，12,kvv12k2(1)n 2配對方式數(shù)為配對方式數(shù)為hk- -1,則將圓周一分為二則將圓周一分為二,一邊有一邊有2(k - -1)個點個點,另一邊有2(n- -k)個點，配對方式數(shù)為個點，配對方式數(shù)為hn- -k.第20頁/共48頁22于是 10112101nnkn knnnkhhhh hh hhh解得 211nnhnn第21頁/共48頁23 13.一個計算機系統(tǒng)把一個十進制數(shù)字串作為一個編碼字，如果它包含偶數(shù)個0，就是有效的.求有效的n位編碼字的個數(shù)an

12、.解 顯然 19.a 若末位數(shù)是1到9中某個數(shù)，則前面n-1位組成的有效數(shù)有an-1個，因此，末位數(shù)不是0的n位有效數(shù)字有 9 an-1個.若末位數(shù)是0，則這樣的n位十進制數(shù)有10n-1個， 而不是有效數(shù)的有 an-1個 (因n-1位的有效數(shù)后面添一個0就不是有效數(shù)了), 所以末位數(shù)是0的有效數(shù)有 第22頁/共48頁241110nna 個.于是得遞推關系 11119(10)9nnnnaaaa 1118109nnnaaa 即 解得通解 185 10,nnnaC 代入初始條件得 1.2C 故所求有效數(shù)字有 114 85 10nnna 個. 第23頁/共48頁25 14.把 件彼此相異的物品分給甲、

13、乙、丙三人，使得甲至少分得兩件物品，乙和丙至少分得一件物品，有多少種不同的分法？(4)n n 解 設有N種不同的分法. 因為把n件彼此相異的物品分給3個人，使得每人至少分得一件物品的方法共有 332033!( , )( 1)33 23innniSn kii 種，其中使得甲恰分得一件物品的分法有 221102( 1)(22)inninini 第24頁/共48頁種，故 11(33 23)(22) 3(6)223nnnnnNnnn 第25頁/共48頁27 15. 令m和n是非負整數(shù)且 , 有m + n 個人站成一排進入劇院，入場費為每人50元.這 m + n 個人中有n個人有50元面額的鈔票，而另外

14、m個人只有100元面額的鈔票.售票處開門時使用一個空的現(xiàn)金收銀機.求能夠使得需要的時候總有零錢可找的隊列方式數(shù). nm 證證 將有將有50元的人用元的人用1標識，有標識，有100元的人用元的人用-1標標識，則該問題為：包括識，則該問題為：包括m個個- -1和和n個個1的的m + n個數(shù)個數(shù) 12,m na aa構(gòu)成的序列，使第26頁/共48頁28120, 1,2,kaaakmn這m + n個數(shù)的排列是集合 的排列， 1,( 1)nm排列數(shù)為 mnm 設A是滿足以上要求的序列全體，稱為可接受排列.設U為不可接受排列的全體，則 |mnAUm第27頁/共48頁29 由于U是不可接受排列的集合，對U中

15、任一個排列，必有最小的k，使120kaaa從而有 1210, 1kkaaaa即即k - -1是偶數(shù)，且是偶數(shù)，且 中有相等個數(shù)的中有相等個數(shù)的1 121,ka aa和和- -1.將將121,kkm na aaaa中前中前k個變號后，可得一個個變號后，可得一個由由n +1個個1和和m - -1個個- -1的序列的序列.第28頁/共48頁30 反反之之n +1個個1和和m - -1個個- -1的序列的序列.由于由于 ,故故必存在必存在k，使，使 中中1的個數(shù)恰比的個數(shù)恰比- -1的個數(shù)的個數(shù)多多1.只要將只要將這這n +1個個1和和m - -1個個- -1的的序列前序列前k項變號，項變號，就可得一

16、就可得一個有個有n個個1和和m個個- -1的的U中中一個排列一個排列.所以所以U是集合是集合 的排列全體，于是的排列全體，于是 nm12,ka aa (1) 1,(1) ( 1)nm |1mnUn所以 |1mnmnAmn 11mnnmnm第29頁/共48頁31組合數(shù)學練習題(二)一一部部由由 樓樓上上升升到到樓樓的的電電梯梯內(nèi)內(nèi)共共有有 個個乘乘客客 他他們們分分別別到到 樓樓至至樓樓去去，該該電電梯梯從從 樓樓開開始始每每層層樓樓都都停停 以以便便讓讓乘乘客客決決定定是是否否離離開開電電梯梯求求 個個乘乘客客離離開開電電梯梯的的不不同同方方法法的的種種數(shù)數(shù)求求 至至樓樓每每層層樓樓都都有有人

17、人離離開開電電梯梯的的不不同同方方法法的的種種數(shù)數(shù) 1. 110, 5105, . (1) . (2) 5 0. 1nn第30頁/共48頁32(1) 5 6 7 8 9 106,6.nn 解解 因因為為每每個個人人可可以以選選擇擇在在 、 樓樓離離開開電電梯梯，即即每每人人離離開開電電梯梯的的方方法法有有 種種由由乘乘法法原原理理 個個乘乘客客離離開開電電梯梯的的不不同同方方法法有有種種(2),|6 .nSnS 令令 表表示示由由 個個乘乘客客離離開開電電梯梯的的全全部部不不同同方方法法所所成成之之集集 則則, , 4 (1,2,6), | 1,2,6iiiaSai iaPAaS aPi 設設

18、若若在在方方法法 之之下下 沒沒有有人人在在第第樓樓離離開開電電梯梯 則則稱稱 具具有有性性質(zhì)質(zhì)令令具具有有性性質(zhì)質(zhì)| (61)5 1,2,6nniAi則則有有 第31頁/共48頁33| (62)4 nnijA Aij同樣 同樣 1212, | (6) (16)kniiikA AAkiii一般地一般地126,666| 6543123666 210456nnnnnnnAAA 由逐步淘汰原理 所求方案數(shù)為由逐步淘汰原理 所求方案數(shù)為506( 1)(6)knkkk 第32頁/共48頁34 2.將4個黑球、3個白球、2個紅球排成一列，但不能讓任何一種同顏色的球全部排在一起，問有多少種排法(假定同色球不

19、加區(qū)別)？ 解 設所求數(shù)為N，以S表示由4個黑球，3個白球，2個紅球作成的全排列之集，A，B，C分別表示S中4個黑球，3個白球，2個紅球排在一起的全排列之集. 則 ，！ ！ ！9!6|1260 |604! 3! 2!1 32SA第33頁/共48頁35，！ ！ ！ ！ ！ ！ ！78|105 |2804 1 243 14!5!|12 |201! 1! 2!1! 3! 1!6!|30 |364 1 1BCABACBCABC所以| | (|) (|)|NABCSABCABACBCABC 871第34頁/共48頁36 3. n個單位各派2名代表出席一個會議，2n名代表圍一圓桌坐下.試問： (1) 同一

20、單位代表相鄰而坐的方案有多少種？ (3)同一單位的代表不相鄰的方案有多少種? 解 (1) 這是2n個元的圓排列,故各單位代表入座方式有 (21)!.n 種種 (2) 將同一單位代表看作一個整體參與排列，有 (1)!.n 種種2 (1)!.nn 種種而同一單位的兩位代表坐法有2種(左或右),故同一單位代表相鄰而坐的方案有第35頁/共48頁37(3) 設這2n個人入座方式的全體為S，則 | (21)!.SnS中第i個單位的兩個人相鄰的入座方式 iA 設設1,2,in ，則 |2(22)!iAn；2|2 (23)!, ijA Anij ；3|2 (24)!, , ,ijkA A Ani j k互互異

21、異；12|2 (1)!nnA AAn第36頁/共48頁38由容斥原理，所求方案數(shù)為122| (21)!2(22)!1 2 (23)!( 1)2 (1)!2nnnnAAAnnnnnnn 同類問題： n對夫妻圍圓桌而坐，求夫妻不相鄰的入坐方案數(shù).第37頁/共48頁39 4.用10 個球壘成一個三角陣，使得1個球在2個球之上，2個球在3個球之上，3個球在4個球之上.這個三角陣可自由旋轉(zhuǎn).用紅色與藍色對該陣各球著色，求不等價著色數(shù).如果再允許翻轉(zhuǎn)該陣，不等價著色數(shù)又有多少種？ 12345678910 解 將三角陣上的球標以110表示，它分別繞其中心逆時針旋轉(zhuǎn)0 ,120 ,240得置換群第38頁/共4

22、8頁40其中 123,Qppp 1(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)p(恒等置換)， 2(1 10 7)(2 6 8)(3 9 4)(5) p(逆時轉(zhuǎn) )120 3(1 7 10)(2 8 6)(3 4 9)(5) p(逆時轉(zhuǎn) )240 由 定理知，所求方案數(shù)為Polya 1 13 3104(222 )352L第39頁/共48頁41如果球陣可以翻轉(zhuǎn)，則置換群為 123456,Qpppppp其中 同前，123,ppp， 456(1)(5)(2 3)(4 6)(7 10)(8 9)(1 10)(2 9)(3 6)(4 8)(5)(7)(1 7)(2 4)(3 8)(6

23、9)(5)(10)ppp1 16 61046(22232 )208L由 定理知，所求方案數(shù)為Polya 第40頁/共48頁42 5.將一個3行3列棋盤的9個正方形著紅色和藍色，棋盤可以繞對稱中心旋轉(zhuǎn)，但不能繞對稱軸翻轉(zhuǎn)，求不等價的著色方案數(shù).從而得置換群Q所含的置換為90 ,180 ,270 ，解 棋盤可以分別繞對稱中心逆時針旋轉(zhuǎn)0 , 1234(1)(2)(3)(4)(5)(6)(7)(8)(9)(1 3 9 7)(2 6 8 4)(5)(1 9)(2 8)(3 7)(4 6)(5)(1 7 9 3)(2 4 8 6)(5)qqqq 123456789第41頁/共48頁43故由 定理知不等價的著色方案數(shù)為Polya 9351(22 22 )1404L 第42頁/共48頁44證證 用用表表示示相相鄰鄰 個個數(shù)數(shù)之之和和. . (1,2,10)3iq i注注意意到到這這些些數(shù)數(shù)中中的的每每個個數(shù)數(shù)都都在在作作和和數(shù)數(shù)時時出出現(xiàn)現(xiàn)了了 次次 故故有有12101,2,10,3,qqq 101 3(1210)165iiq 6.把1到10這10個數(shù)隨機地寫成一個圓圈.證明：