《組合數(shù)學(xué)練習(xí)題(一)數(shù)學(xué)教學(xué)課件PPT》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)練習(xí)題(一)數(shù)學(xué)教學(xué)課件PPT（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1組合數(shù)學(xué)練習(xí)題組合數(shù)學(xué)練習(xí)題(一一) 1. 有有20根完全相同的木棍從左至右豎立成一行，根完全相同的木棍從左至右豎立成一行，占占 據(jù)據(jù)20個(gè)位置個(gè)位置. 要從中選出要從中選出6根根. (1) 有多少種選擇？有多少種選擇？ (2) 如果選出的木棍中沒(méi)有兩根是位置相鄰的，如果選出的木棍中沒(méi)有兩根是位置相鄰的，又有多少種選擇？又有多少種選擇？ (3) 如果選出的每一對(duì)木棍之間必須至少有兩如果選出的每一對(duì)木棍之間必須至少有兩根木棍，又有多少種選擇？根木棍，又有多少種選擇？解解 (1) 有有 種種. 2062 (2) 所選出的所選出的6根木棍實(shí)際上可將這根木棍實(shí)際上可將這20根排成根排成一行的木棍分割

2、成一行的木棍分割成7段段(加上首和尾加上首和尾).設(shè)所選左邊第設(shè)所選左邊第1根木棍的左側(cè)有根木棍的左側(cè)有x1根未被選中的木棍；在第根未被選中的木棍；在第1 與與第第2根所選木棍之間有根所選木棍之間有x2根未被選中的木棍；根未被選中的木棍；在第在第5 與第與第6根所選木棍之間有根所選木棍之間有x6根未被選中的木根未被選中的木棍；在第棍；在第6根所選木棍的右側(cè)有根所選木棍的右側(cè)有x7根未被選中的木根未被選中的木棍，則由于沒(méi)有兩根選出的木棍是相鄰的，所以棍，則由于沒(méi)有兩根選出的木棍是相鄰的，所以=， 12345671714001,2,3,6ixxxxxxxxxxi3作變量代換作變量代換則原方程變成則

3、原方程變成，11771,2,3,6iiyxyxyxi 123456790,1,2,3,7iyyyyyyyyi這個(gè)方程的非負(fù)整數(shù)解的個(gè)數(shù)即為所求的選擇數(shù)這個(gè)方程的非負(fù)整數(shù)解的個(gè)數(shù)即為所求的選擇數(shù)971155005994(3) 同同(2)中的分析，此時(shí)有不定方程中的分析，此時(shí)有不定方程=， 12345671714002,2,3,6ixxxxxxxxxxi4711021044仿照仿照(2)，這個(gè)方程的非負(fù)整數(shù)解的個(gè)數(shù)即為所求這個(gè)方程的非負(fù)整數(shù)解的個(gè)數(shù)即為所求的選擇數(shù)的選擇數(shù)5 2. (1) 在在2n個(gè)物體中有個(gè)物體中有n個(gè)是相同的，則從這個(gè)是相同的，則從這2n個(gè)物體中選取個(gè)物體中選取n個(gè)的方法有幾種

4、？個(gè)的方法有幾種？ (2) 在在3n +1個(gè)物體中有個(gè)物體中有n個(gè)是相同的，則從這個(gè)是相同的，則從這3n +1個(gè)物體中選取個(gè)物體中選取n個(gè)的方法有幾種？個(gè)的方法有幾種？解解 (1) 若選出的物體有若選出的物體有 個(gè)不個(gè)不 (0,1,2, )k kn相同相同,則其余則其余n - - k個(gè)是相同的個(gè)是相同的,所以選取的方法數(shù)為所以選取的方法數(shù)為 201nnnnn 212212121122201nnnnnn(2) 類(lèi)似于類(lèi)似于(1)的分析可知，所以選取的方法數(shù)為的分析可知，所以選取的方法數(shù)為6 3. 用用 種顏色去涂種顏色去涂 棋盤(pán)，棋盤(pán)，每格涂一種顏色，求使得相鄰格子異色，首末兩格每格涂一種顏色，

5、求使得相鄰格子異色，首末兩格也異色的涂色方法數(shù)也異色的涂色方法數(shù). (2)m m 1 ()n nm解解 用用hn表示所求方法數(shù)表示所求方法數(shù).易知易知 2(1).hm m用用m種顏色去涂種顏色去涂 棋盤(pán)，每格涂一種顏棋盤(pán)，每格涂一種顏 1 ()n nm色，色，使得相鄰格子異色的涂色方法數(shù)有使得相鄰格子異色的涂色方法數(shù)有 1(1)nm m種種,其中使得首末兩格同色的涂色方法有其中使得首末兩格同色的涂色方法有 種種,所以所以 1nh 11(1) (2)nnnhm mhn從而從而7 111222(1)(1)(1)( 1)nnnnnnhm mhm mm mh 12333(1)(1)(1)( 1)nnn

6、nm 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)nnmm8 4. 用用 種顏色去涂種顏色去涂 棱錐的棱錐的n + 1個(gè)頂點(diǎn)個(gè)頂點(diǎn),每個(gè)頂點(diǎn)涂一種顏色，求使得棱錐的每個(gè)頂點(diǎn)涂一種顏色，求使得棱錐的每條棱的兩個(gè)端點(diǎn)異色的涂色方法數(shù)每條棱的兩個(gè)端點(diǎn)異色的涂色方法數(shù) (3)m m (3)n n(, ).K m n 解解 設(shè)設(shè)V是一個(gè)是一個(gè)n棱錐棱錐,則可依則可依如下兩個(gè)步驟去完成如下兩個(gè)步驟去完成V的

7、的n + 1個(gè)頂點(diǎn)的涂色工作個(gè)頂點(diǎn)的涂色工作: 先涂頂點(diǎn)先涂頂點(diǎn)v0,有有m種涂色方法種涂色方法;然后用異于然后用異于v0顏色的顏色的m - - 1種顏色種顏色去涂頂點(diǎn)序列去涂頂點(diǎn)序列v1， v2， vn, 使得相鄰頂點(diǎn)異色使得相鄰頂點(diǎn)異色且首末兩個(gè)頂點(diǎn)也異色且首末兩個(gè)頂點(diǎn)也異色.0v1v2v3vnv9由上題可知由上題可知,完成此步驟的方法有完成此步驟的方法有 (2)( 1) (2)nnmm種，種，由乘法原理由乘法原理,得所求涂色方法數(shù)為得所求涂色方法數(shù)為 (, )(2)( 1)(2)nnK m nm mm m10na解解 所所求求種種類(lèi)類(lèi)數(shù)數(shù) 的的母母函函數(shù)數(shù)為為32321111(1)111

8、(1)xxxxxx 24236( )(1)(1)(1)(1)G xxxxxxxx 5. 將充分多的蘋(píng)果、香蕉、橘子和梨這將充分多的蘋(píng)果、香蕉、橘子和梨這4種水果種水果裝袋，要求各袋有偶數(shù)個(gè)蘋(píng)果，最多裝袋，要求各袋有偶數(shù)個(gè)蘋(píng)果，最多2個(gè)橘子，個(gè)橘子，3的的倍數(shù)個(gè)香蕉，最多倍數(shù)個(gè)香蕉，最多1個(gè)梨?zhèn)€梨. 如果每袋裝如果每袋裝n個(gè)水果，求裝個(gè)水果，求裝袋的種類(lèi)數(shù)袋的種類(lèi)數(shù).11001(1)nnnnnxnxn 1.nan 所所以以12 6. 把把n個(gè)相異的球放到個(gè)相異的球放到4個(gè)相異盒子個(gè)相異盒子 中，求使得中，求使得 含有奇數(shù)個(gè)球，含有奇數(shù)個(gè)球， 含有偶數(shù)個(gè)球的不含有偶數(shù)個(gè)球的不同的放球方法數(shù)同的放球

9、方法數(shù).1234,A A A A1A2A則數(shù)列則數(shù)列 對(duì)應(yīng)的指母函數(shù)為對(duì)應(yīng)的指母函數(shù)為na解解 設(shè)滿足條件的放球方法數(shù)為設(shè)滿足條件的放球方法數(shù)為.na3524232( )()(1)3!5!2!4! (1)2!3!exxxxG xxxxx 13222xxxxxeeeee 414xe 1144!nnnxn 114!nnnxn 14.nna 所以所以14 7. 由數(shù)字由數(shù)字1至至9組成的每種數(shù)字至少出現(xiàn)組成的每種數(shù)字至少出現(xiàn)1次的次的 位數(shù)有多少個(gè)？位數(shù)有多少個(gè)？ (9)n n解解 設(shè)所求的數(shù)為設(shè)所求的數(shù)為an,則則an的指母函數(shù)為的指母函數(shù)為 9(9)09( 1)kk xkek 2399( )()

10、(1)2!3!xexxG xxe 9009( 1)(9)!nknknxknk 9009( 1)(9)!nknnkxknk 909( 1)(9)knnkakk所以所以15 8. 由字母由字母a,b,c,d,e組成的總字母數(shù)為組成的總字母數(shù)為n的單詞的單詞中，要求中，要求a與與b的個(gè)數(shù)之和為偶數(shù)，求這樣的單詞的個(gè)數(shù)之和為偶數(shù)，求這樣的單詞的個(gè)數(shù)的個(gè)數(shù). 解解 這樣的單詞有兩類(lèi)：一類(lèi)包括偶數(shù)個(gè)這樣的單詞有兩類(lèi)：一類(lèi)包括偶數(shù)個(gè)a與與偶數(shù)個(gè)偶數(shù)個(gè)b；另一類(lèi)包括奇數(shù)個(gè)；另一類(lèi)包括奇數(shù)個(gè)a與奇數(shù)個(gè)與奇數(shù)個(gè)b.設(shè)所求設(shè)所求的數(shù)為的數(shù)為an,則則an的指母函數(shù)為的指母函數(shù)為 242323352323( )(1)

11、 (1)2!4!2!3! () (1)3!5!2!3!exxxxG xxxxxxxx16 223322xxxxxxeeeeee故故 50011()(5)22!nnxxnnnxxeenn 0512!nnnxn 512nna17 9.有多少個(gè)長(zhǎng)度為有多少個(gè)長(zhǎng)度為n的的0與與1串串, 在這些串中在這些串中, 既不既不包含子串包含子串010，也不包含子串，也不包含子串101？解解 設(shè)這種數(shù)串的個(gè)數(shù)為設(shè)這種數(shù)串的個(gè)數(shù)為 將滿足條件的數(shù)串分為兩類(lèi)：將滿足條件的數(shù)串分為兩類(lèi)： ,nf1224ff則則，3n 時(shí)時(shí)， (1) 最后兩位數(shù)字相同最后兩位數(shù)字相同. 這種長(zhǎng)度為這種長(zhǎng)度為n的數(shù)串可的數(shù)串可由長(zhǎng)度為由長(zhǎng)

12、度為n-1的串最后一位數(shù)字重復(fù)一次而得，故的串最后一位數(shù)字重復(fù)一次而得，故這類(lèi)數(shù)串的個(gè)數(shù)這類(lèi)數(shù)串的個(gè)數(shù) 1nf ； (2) 最后兩位數(shù)字不同最后兩位數(shù)字不同. 這種長(zhǎng)度為這種長(zhǎng)度為n的數(shù)串可的數(shù)串可由長(zhǎng)度為由長(zhǎng)度為n-2的串最后一位的串最后一位(設(shè)為設(shè)為a)重復(fù)一次，再加重復(fù)一次，再加上與上與a不同的數(shù)字而得不同的數(shù)字而得, 故這類(lèi)數(shù)串的個(gè)數(shù)為故這類(lèi)數(shù)串的個(gè)數(shù)為 2.nf 18于是得遞推關(guān)系于是得遞推關(guān)系12122, 4 nnnfffff 由由Fibonacci數(shù)列數(shù)列,得通解得通解121515()()22nnnfcc代入初值代入初值,得得 125555,55cc1121515 ()()225

13、nnnf所所以以19 10. 由由0,1,2,3組成的長(zhǎng)度為組成的長(zhǎng)度為n的序列中，求含的序列中，求含偶數(shù)個(gè)偶數(shù)個(gè)0的序列個(gè)數(shù)和含奇數(shù)個(gè)的序列個(gè)數(shù)和含奇數(shù)個(gè)0的序列個(gè)數(shù)的序列個(gè)數(shù). 解解 設(shè)設(shè)an為含偶數(shù)個(gè)為含偶數(shù)個(gè)0的序列個(gè)數(shù)，的序列個(gè)數(shù)，bn為含奇為含奇數(shù)個(gè)數(shù)個(gè)0的序列個(gè)數(shù)的序列個(gè)數(shù).則有則有 114 3nnnnnnababa解得解得1122 4,nnna1144(22 4)nnnnnnba112 42nn20 11. 十個(gè)數(shù)字十個(gè)數(shù)字(0到到9)和四個(gè)運(yùn)算符和四個(gè)運(yùn)算符( +，- -，*，/ )組成組成14個(gè)元素，求由其中的個(gè)元素，求由其中的n個(gè)元素的排列構(gòu)成一個(gè)元素的排列構(gòu)成一形式算術(shù)

14、表達(dá)式的個(gè)數(shù)形式算術(shù)表達(dá)式的個(gè)數(shù). 解解 令令an表示表示n個(gè)元素排列成算術(shù)表達(dá)式的數(shù)目，個(gè)元素排列成算術(shù)表達(dá)式的數(shù)目，則則 1212104010, 120 nnnaaaaa解得解得133 65133 65(565)(565)5252nnna21 12. 在一圓周上均勻地取在一圓周上均勻地取2n個(gè)點(diǎn)，用個(gè)點(diǎn)，用n條兩兩條兩兩不相交的弦把這些點(diǎn)配成對(duì)，求所有這種配對(duì)的不相交的弦把這些點(diǎn)配成對(duì)，求所有這種配對(duì)的方式數(shù)方式數(shù). 解解 設(shè)所求配對(duì)的方式數(shù)為設(shè)所求配對(duì)的方式數(shù)為hn,則則h1 = 1,則則h0 = 1,設(shè)設(shè)2n個(gè)點(diǎn)依次為個(gè)點(diǎn)依次為， ， ， ，1222,knvvvv連接連接，12,kvv

15、12k2(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.22于是于是 10112101nnkn knnnkhhhh hh hhh解得解得 211nnhnn23 13.一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)編碼字，如果它包含偶數(shù)個(gè)編碼字，如果它包含偶數(shù)個(gè)0，就是有效的，就是有效的.求有效的求有效的n位編碼字的個(gè)數(shù)位編碼字的個(gè)數(shù)an .解解 顯然顯然 19.a 若末位數(shù)是若末位數(shù)是1到到9中某個(gè)數(shù)，則

16、前面中某個(gè)數(shù)，則前面n-1位組成的位組成的有效數(shù)有有效數(shù)有an-1個(gè)，因此，末位數(shù)不是個(gè)，因此，末位數(shù)不是0的的n位有效數(shù)字位有效數(shù)字有有 9 an-1個(gè)個(gè).若末位數(shù)是若末位數(shù)是0，則這樣的，則這樣的n位十進(jìn)制數(shù)有位十進(jìn)制數(shù)有10n-1個(gè)，個(gè)， 而不是有效數(shù)的有而不是有效數(shù)的有 an-1個(gè)個(gè) (因因n-1位的有效數(shù)后面添一位的有效數(shù)后面添一個(gè)個(gè)0就不是有效數(shù)了就不是有效數(shù)了), 所以末位數(shù)是所以末位數(shù)是0的有效數(shù)有的有效數(shù)有 241110nna 個(gè)個(gè).于是得遞推關(guān)系于是得遞推關(guān)系 11119(10)9nnnnaaaa 1118109nnnaaa 即即 解得通解解得通解 185 10,nnnaC

17、 代入初始條件得代入初始條件得 1.2C 故所求有效數(shù)字有故所求有效數(shù)字有 114 85 10nnna 個(gè)個(gè). 25 14.把把 件彼此相異的物品分給甲、乙、件彼此相異的物品分給甲、乙、丙三人，使得甲至少分得兩件物品，乙和丙至少分丙三人，使得甲至少分得兩件物品，乙和丙至少分得一件物品，有多少種不同的分法？得一件物品，有多少種不同的分法？(4)n n 解解 設(shè)有設(shè)有N種不同的分法種不同的分法. 因?yàn)榘岩驗(yàn)榘裯件彼此相異件彼此相異的物品分給的物品分給3個(gè)人，使得每人至少分得一件物品的個(gè)人，使得每人至少分得一件物品的方法共有方法共有 332033!( , )( 1)33 23innniSn kii

18、種，其中使得甲恰分得一件物品的分法有種，其中使得甲恰分得一件物品的分法有 221102( 1)(22)inninini 種，故種，故 11(33 23)(22) 3(6)223nnnnnNnnn 27 15. 令令m和和n是非負(fù)整數(shù)且是非負(fù)整數(shù)且 , 有有m + n 個(gè)人個(gè)人站成一排進(jìn)入劇院，入場(chǎng)費(fèi)為每人站成一排進(jìn)入劇院，入場(chǎng)費(fèi)為每人50元元.這這 m + n 個(gè)個(gè)人中有人中有n個(gè)人有個(gè)人有50元面額的鈔票，而另外元面額的鈔票，而另外m個(gè)人只個(gè)人只有有100元面額的鈔票元面額的鈔票.售票處開(kāi)門(mén)時(shí)使用一個(gè)空的現(xiàn)售票處開(kāi)門(mén)時(shí)使用一個(gè)空的現(xiàn)金收銀機(jī)金收銀機(jī).求能夠使得需要的時(shí)候總有零錢(qián)可找的隊(duì)求能夠

19、使得需要的時(shí)候總有零錢(qián)可找的隊(duì)列方式數(shù)列方式數(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)成的序列，使構(gòu)成的序列，使28120, 1,2,kaaakmn這這m + n個(gè)數(shù)的排列是集合個(gè)數(shù)的排列是集合 的排列，的排列， 1,( 1)nm排列數(shù)為排列數(shù)為 mnm 設(shè)設(shè)A是滿足以上要求的序列全體，稱(chēng)為可接受是滿足以上要求的序列全體，稱(chēng)為可接受排列排列.設(shè)設(shè)U為不可接受排列的全體，則為不可接受排列的全體，則 |mnAUm29 由于由于U是不可接

20、受排列的集合，對(duì)是不可接受排列的集合，對(duì)U中任一個(gè)中任一個(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的序列的序列.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 -

21、 -1個(gè)個(gè)- -1的的序列前序列前k項(xiàng)變號(hào)，項(xiàng)變號(hào)，就可得一就可得一個(gè)有個(gè)有n個(gè)個(gè)1和和m個(gè)個(gè)- -1的的U中中一個(gè)排列一個(gè)排列.所以所以U是集合是集合 的排列全體，于是的排列全體，于是 nm12,ka aa (1) 1,(1) ( 1)nm |1mnUn所以所以 |1mnmnAmn 11mnnmnm31組合數(shù)學(xué)練習(xí)題組合數(shù)學(xué)練習(xí)題(二二)一一部部由由 樓樓上上升升到到樓樓的的電電梯梯內(nèi)內(nèi)共共有有 個(gè)個(gè)乘乘客客 他他們們分分別別到到 樓樓至至樓樓去去，該該電電梯梯從從 樓樓開(kāi)開(kāi)始始每每層層樓樓都都停停 以以便便讓讓乘乘客客決決定定是是否否離離開(kāi)開(kāi)電電梯梯求求 個(gè)個(gè)乘乘客客離離開(kāi)開(kāi)電電梯梯的的不

22、不同同方方法法的的種種數(shù)數(shù)求求 至至樓樓每每層層樓樓都都有有人人離離開(kāi)開(kāi)電電梯梯的的不不同同方方法法的的種種數(shù)數(shù) 1. 110, 5105, . (1) . (2) 5 0. 1nn32(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

23、,6iiiaSai iaPAaS aPi 設(shè)設(shè)若若在在方方法法 之之下下 沒(méi)沒(méi)有有人人在在第第樓樓離離開(kāi)開(kāi)電電梯梯 則則稱(chēng)稱(chēng) 具具有有性性質(zhì)質(zhì)令令具具有有性性質(zhì)質(zhì)| (61)5 1,2,6nniAi則則有有 33| (62)4 nnijA Aij同樣 同樣 1212, | (6) (16)kniiikA AAkiii一般地一般地126,666| 6543123666 210456nnnnnnnAAA 由逐步淘汰原理 所求方案數(shù)為由逐步淘汰原理 所求方案數(shù)為506( 1)(6)knkkk 34 2.將將4個(gè)黑球、個(gè)黑球、3個(gè)白球、個(gè)白球、2個(gè)紅球排成一列，個(gè)紅球排成一列，但不能讓任何一種同顏色的

24、球全部排在一起，問(wèn)但不能讓任何一種同顏色的球全部排在一起，問(wèn)有多少種排法有多少種排法(假定同色球不加區(qū)別假定同色球不加區(qū)別)？ 解解 設(shè)所求數(shù)為設(shè)所求數(shù)為N，以，以S表示由表示由4個(gè)黑球，個(gè)黑球，3個(gè)個(gè)白球，白球，2個(gè)紅球作成的全排列之集，個(gè)紅球作成的全排列之集，A，B，C分分別表示別表示S中中4個(gè)黑球，個(gè)黑球，3個(gè)白球，個(gè)白球，2個(gè)紅球排在一起個(gè)紅球排在一起的全排列之集的全排列之集. 則則 ，！ ！ ！9!6|1260 |604! 3! 2!1 32SA35，！ ！ ！ ！ ！ ！ ！78|105 |2804 1 243 14!5!|12 |201! 1! 2!1! 3! 1!6!|30 |

25、364 1 1BCABACBCABC所以所以| | (|) (|)|NABCSABCABACBCABC 87136 3. n個(gè)單位各派個(gè)單位各派2名代表出席一個(gè)會(huì)議，名代表出席一個(gè)會(huì)議，2n名名代表圍一圓桌坐下代表圍一圓桌坐下.試問(wèn)：試問(wèn)： (1) 同一單位代表相鄰而坐的方案有多少種？同一單位代表相鄰而坐的方案有多少種？ (3)同一單位的代表不相鄰的方案有多少種同一單位的代表不相鄰的方案有多少種? 解解 (1) 這是這是2n個(gè)元的圓排列個(gè)元的圓排列,故各單位代表入座故各單位代表入座方式有方式有 (21)!.n 種種 (2) 將同一單位代表看作一個(gè)整體參與排列，有將同一單位代表看作一個(gè)整體參與排

26、列，有 (1)!.n 種種2 (1)!.nn 種種而同一單位的兩位代表坐法有而同一單位的兩位代表坐法有2種種(左或右左或右),故同一單位代表相鄰而坐的方案有故同一單位代表相鄰而坐的方案有37(3) 設(shè)這設(shè)這2n個(gè)人入座方式的全體為個(gè)人入座方式的全體為S，則，則 |(21)!.SnS中第中第i個(gè)單位的兩個(gè)人相鄰的入座方式個(gè)單位的兩個(gè)人相鄰的入座方式 iA 設(shè)設(shè)1,2,in ，則則 |2(22)!iAn；2|2 (23)!, ijA Anij ；3|2 (24)!, , ,ijkA A Ani j k互互異異；12|2 (1)!nnA AAn38由容斥原理，所求方案數(shù)為由容斥原理，所求方案數(shù)為12

27、2| (21)!2(22)!1 2 (23)!( 1)2 (1)!2nnnnAAAnnnnnnn 同類(lèi)問(wèn)題：同類(lèi)問(wèn)題： n對(duì)夫妻圍圓桌而坐，求夫妻不相鄰的入坐方對(duì)夫妻圍圓桌而坐，求夫妻不相鄰的入坐方案數(shù)案數(shù).39 4.用用10 個(gè)球壘成一個(gè)三角陣，使得個(gè)球壘成一個(gè)三角陣，使得1個(gè)球在個(gè)球在2個(gè)球之上，個(gè)球之上，2個(gè)球在個(gè)球在3個(gè)球之上，個(gè)球之上，3個(gè)球在個(gè)球在4個(gè)球之個(gè)球之上上.這個(gè)三角陣可自由旋轉(zhuǎn)這個(gè)三角陣可自由旋轉(zhuǎn).用紅色與藍(lán)色對(duì)該陣各用紅色與藍(lán)色對(duì)該陣各球著色，求不等價(jià)著色數(shù)球著色，求不等價(jià)著色數(shù).如果再允許翻轉(zhuǎn)該陣，如果再允許翻轉(zhuǎn)該陣，不等價(jià)著色數(shù)又有多少種？不等價(jià)著色數(shù)又有多少種？

28、12345678910 解解 將三角陣上的球標(biāo)將三角陣上的球標(biāo)以以110表示，它表示，它分別分別繞其繞其中心逆時(shí)針旋轉(zhuǎn)中心逆時(shí)針旋轉(zhuǎn)0 ,120 ,240得置換群得置換群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)逆時(shí)轉(zhuǎn) )120 3(1 7 10)(2 8 6)(3 4 9)(5) p(逆時(shí)轉(zhuǎn)逆時(shí)轉(zhuǎn) )240 由由 定理知，所求方案數(shù)為定理知，所求方案數(shù)為Polya 1 13 3104(222 )352L41如果球陣可以翻轉(zhuǎn)，則置換群為如果球陣可以翻轉(zhuǎn)

29、，則置換群為 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 9)(5)(10)ppp1 16 61046(22232 )208L由由 定理知，所求方案數(shù)為定理知，所求方案數(shù)為Polya 42 5.將一個(gè)將一個(gè)3行行3列棋盤(pán)的列棋盤(pán)的9個(gè)正方形著紅色和藍(lán)色，個(gè)正方形著紅色和藍(lán)色，棋盤(pán)可以繞對(duì)稱(chēng)中心旋轉(zhuǎn)，但不能繞對(duì)稱(chēng)軸翻轉(zhuǎn)，棋盤(pán)可以繞對(duì)稱(chēng)中心旋轉(zhuǎn)，但不能繞對(duì)稱(chēng)軸翻轉(zhuǎn)，求不等價(jià)的著色方案數(shù)求不等價(jià)的著色方案數(shù).從而得置換群從而得置換

30、群Q所含的置換為所含的置換為90 ,180 ,270 ，解解 棋盤(pán)可以分別繞對(duì)稱(chēng)中心逆時(shí)針旋轉(zhuǎn)棋盤(pán)可以分別繞對(duì)稱(chēng)中心逆時(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 12345678943故由故由 定理知不等價(jià)的著色方案數(shù)為定理知不等價(jià)的著色方案數(shù)為Polya 9351(22 22 )1404L 44證證 用用表表示示相相鄰鄰 個(gè)個(gè)數(shù)數(shù)之之和和. . (1,2,10)3iq i注注意意到到這這些些數(shù)數(shù)中中的的每每個(gè)個(gè)數(shù)數(shù)都都在

31、在作作和和數(shù)數(shù)時(shí)時(shí)出出現(xiàn)現(xiàn)了了 次次 故故有有12101,2,10,3,qqq 101 3(1210)165iiq 6.把把1到到10這這10個(gè)數(shù)隨機(jī)地寫(xiě)成一個(gè)圓圈個(gè)數(shù)隨機(jī)地寫(xiě)成一個(gè)圓圈.證明：證明：必存在某必存在某3個(gè)相鄰數(shù)之和大于或等于個(gè)相鄰數(shù)之和大于或等于17.45即即存存在在某某個(gè)個(gè)使使 , 17.iiqq問(wèn)問(wèn)題題歸歸結(jié)結(jié)為為: :把把件件物物品品放放入入個(gè)個(gè)抽抽屜屜里里16510,由由抽抽屜屜原原理理知知 至至少少有有一一個(gè)個(gè)抽抽屜屜( (即即某某個(gè)個(gè)放放有有,)iq不少于不少于 1651710, 件物品件物品這表明圓圈的這表明圓圈的10個(gè)數(shù)中個(gè)數(shù)中,必存在三個(gè)連續(xù)的數(shù)必存在三個(gè)連續(xù)

32、的數(shù),其其和大于或等于和大于或等于17.46 7. 證明：如果從證明：如果從 S = 1, 3, 5, 7, , 599 中任中任選選101個(gè)數(shù)，在所選出的數(shù)中總存在個(gè)數(shù)，在所選出的數(shù)中總存在2個(gè)數(shù)，它們個(gè)數(shù)，它們之間最多差之間最多差4.證證 把把S中的數(shù)分成中的數(shù)分成100組：組：1,3,5,7,9,11,595,597,599則每組中的數(shù)之間的差均不超過(guò)則每組中的數(shù)之間的差均不超過(guò)4.從從S中任取中任取101個(gè)數(shù)，由抽屜原理，至少有個(gè)數(shù)，由抽屜原理，至少有2個(gè)數(shù)在同一組，它們個(gè)數(shù)在同一組，它們之差不超過(guò)之差不超過(guò)4.47 8. 一間屋內(nèi)有一間屋內(nèi)有10個(gè)人，他們當(dāng)中沒(méi)有人超過(guò)個(gè)人，他們當(dāng)中

33、沒(méi)有人超過(guò)60歲歲(年齡只能以整數(shù)給出年齡只能以整數(shù)給出)，但又至少不低于，但又至少不低于1歲歲. 證證明：總能找出兩組人明：總能找出兩組人(兩組不含相同的人兩組不含相同的人)，各組人，各組人的年齡和是相同的的年齡和是相同的. 題中的數(shù)題中的數(shù)10能換成更小的數(shù)嗎？能換成更小的數(shù)嗎？解解 設(shè)這設(shè)這10個(gè)人的年齡依次為個(gè)人的年齡依次為這這10個(gè)數(shù)形成的求和方式數(shù)為個(gè)數(shù)形成的求和方式數(shù)為，1210,a aa101010102110231210而這而這10個(gè)人年齡之和是個(gè)人年齡之和是10600之間的整數(shù)，用此之間的整數(shù)，用此作作“抽屜抽屜”，將，將1023件物品放入其中，由抽屜原件物品放入其中，由抽

34、屜原理，必有兩個(gè)求和方式的結(jié)果相同，設(shè)為理，必有兩個(gè)求和方式的結(jié)果相同，設(shè)為481212,1,2,10,1,2, ;1,2,stkkkmmmijaaaaaak mis jt 如果集合如果集合 與集合與集合 沒(méi)有相同元素，則它們對(duì)應(yīng)的兩組人即為所求；沒(méi)有相同元素，則它們對(duì)應(yīng)的兩組人即為所求；12,skkkaaa12,tmmmaaa如果這兩個(gè)集合有相同元素，則在等式如果這兩個(gè)集合有相同元素，則在等式1212stkkkmmmaaaaaa兩端同時(shí)減去這些相同元素的值，等式仍成立，兩端同時(shí)減去這些相同元素的值，等式仍成立，等式中兩端余下的各項(xiàng)對(duì)應(yīng)的人就是所求兩組年等式中兩端余下的各項(xiàng)對(duì)應(yīng)的人就是所求兩組年齡和相同的人齡和相同的人.