級(jí)組合數(shù)學(xué)復(fù)習(xí)題解答PPT學(xué)習(xí)教案

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

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

3、01nnnnn 212212121122201nnnnnn(2) 類似于(1)的分析可知，所以選取的方法數(shù)為第4頁(yè)/共48頁(yè)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頁(yè)/共48頁(yè)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頁(yè)/共48頁(yè)8 4. 用 種顏色去涂 棱錐的n + 1個(gè)頂點(diǎn),每個(gè)頂點(diǎn)涂一種顏色，求使得棱錐的每條棱的兩個(gè)端點(diǎn)異色的涂色方法數(shù) (3)m m (3)n n(, ).K m n 解 設(shè)V是一個(gè)n棱錐,則可依如下兩個(gè)步驟去完成V的n + 1個(gè)頂點(diǎn)的涂色工作: 先涂頂點(diǎn)先涂頂點(diǎn)v0,有有m種涂色方法種

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

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

7、4.nna 所以第12頁(yè)/共48頁(yè)14 7. 由數(shù)字1至9組成的每種數(shù)字至少出現(xiàn)1次的 位數(shù)有多少個(gè)？ (9)n n解 設(shè)所求的數(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頁(yè)/共48頁(yè)15 8. 由字母a,b,c,d,e組成的總字母數(shù)為n的單詞中，要求a與b的個(gè)數(shù)之和為偶數(shù)，求這樣的單詞的個(gè)數(shù). 解 這樣的單詞有兩類：一類包括偶數(shù)個(gè)a與偶數(shù)個(gè)b；另一類包括奇數(shù)個(gè)a與奇數(shù)個(gè)b.設(shè)所求的數(shù)為an

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

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

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

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

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

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

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

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

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

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

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

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

20、單位代表相鄰而坐的方案有多少種？ (3)同一單位的代表不相鄰的方案有多少種? 解 (1) 這是2n個(gè)元的圓排列,故各單位代表入座方式有 (21)!.n 種種 (2) 將同一單位代表看作一個(gè)整體參與排列，有 (1)!.n 種種2 (1)!.nn 種種而同一單位的兩位代表坐法有2種(左或右),故同一單位代表相鄰而坐的方案有第35頁(yè)/共48頁(yè)37(3) 設(shè)這2n個(gè)人入座方式的全體為S，則 | (21)!.SnS中第i個(gè)單位的兩個(gè)人相鄰的入座方式 iA 設(shè)設(shè)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頁(yè)/共48頁(yè)38由容斥原理，所求方案數(shù)為122| (21)!2(22)!1 2 (23)!( 1)2 (1)!2nnnnAAAnnnnnnn 同類問(wèn)題： n對(duì)夫妻圍圓桌而坐，求夫妻不相鄰的入坐方案數(shù).第37頁(yè)/共48頁(yè)39 4.用10 個(gè)球壘成一個(gè)三角陣，使得1個(gè)球在2個(gè)球之上，2個(gè)球在3個(gè)球之上，3個(gè)球在4個(gè)球之上.這個(gè)三角陣可自由旋轉(zhuǎn).用紅色與藍(lán)色對(duì)該陣各球著色，求不等價(jià)著色數(shù).如果再允許翻轉(zhuǎn)該陣，不等價(jià)著色數(shù)又有多少種？ 12345678910 解 將三角陣上的球標(biāo)以110表示，它分別繞其中心逆時(shí)針旋轉(zhuǎn)0 ,120 ,240得置換群第38頁(yè)/共4

22、8頁(yè)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(逆時(shí)轉(zhuǎn) )120 3(1 7 10)(2 8 6)(3 4 9)(5) p(逆時(shí)轉(zhuǎn) )240 由 定理知，所求方案數(shù)為Polya 1 13 3104(222 )352L第39頁(yè)/共48頁(yè)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頁(yè)/共48頁(yè)42 5.將一個(gè)3行3列棋盤的9個(gè)正方形著紅色和藍(lán)色，棋盤可以繞對(duì)稱中心旋轉(zhuǎn)，但不能繞對(duì)稱軸翻轉(zhuǎn)，求不等價(jià)的著色方案數(shù).從而得置換群Q所含的置換為90 ,180 ,270 ，解 棋盤可以分別繞對(duì)稱中心逆時(shí)針旋轉(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頁(yè)/共48頁(yè)43故由 定理知不等價(jià)的著色方案數(shù)為Polya 9351(22 22 )1404L 第42頁(yè)/共48頁(yè)44證證 用用表表示示相相鄰鄰 個(gè)個(gè)數(shù)數(shù)之之和和. . (1,2,10)3iq i注注意意到到這這些些數(shù)數(shù)中中的的每每個(gè)個(gè)數(shù)數(shù)都都在在作作和和數(shù)數(shù)時(shí)時(shí)出出現(xiàn)現(xiàn)了了 次次 故故有有12101,2,10,3,qqq 101 3(1210)165iiq 6.把1到10這10個(gè)數(shù)隨機(jī)地寫成一個(gè)圓圈.證明：