研究生組合數(shù)學(xué)復(fù)習(xí)要點(diǎn)

1、1組合數(shù)學(xué)復(fù)習(xí)要點(diǎn)組合數(shù)學(xué)復(fù)習(xí)要點(diǎn)一、排列組合一、排列組合1. 排列和組合的基本性質(zhì)排列和組合的基本性質(zhì)2. 排列組合的計(jì)數(shù)公式，多重集的排列數(shù)和組合排列組合的計(jì)數(shù)公式，多重集的排列數(shù)和組合 數(shù)的求法數(shù)的求法3. 應(yīng)用應(yīng)用2二、母函數(shù)二、母函數(shù)1. 母函數(shù)與數(shù)列的關(guān)系母函數(shù)與數(shù)列的關(guān)系2. 母函數(shù)與排列數(shù)、組合數(shù)的關(guān)系母函數(shù)與排列數(shù)、組合數(shù)的關(guān)系3. 用普通型母函數(shù)解決多重集的組合問題用普通型母函數(shù)解決多重集的組合問題4. 用指數(shù)型母函數(shù)解決多重集的排列問題用指數(shù)型母函數(shù)解決多重集的排列問題5. 用母函數(shù)解遞推關(guān)系式用母函數(shù)解遞推關(guān)系式6. 不定方程的整數(shù)解的個(gè)數(shù)與多重集的組合數(shù)之不定方程的整

2、數(shù)解的個(gè)數(shù)與多重集的組合數(shù)之 關(guān)系關(guān)系3三、遞推關(guān)系三、遞推關(guān)系1. 常系數(shù)線性遞推關(guān)系的解法（特征根法）常系數(shù)線性遞推關(guān)系的解法（特征根法）2. 用待定系數(shù)法求常系數(shù)線性非齊次遞推關(guān)系的用待定系數(shù)法求常系數(shù)線性非齊次遞推關(guān)系的 特解特解(前兩種類型前兩種類型)3.列遞推關(guān)系解應(yīng)用題列遞推關(guān)系解應(yīng)用題4. 一般遞推關(guān)系的線性化一般遞推關(guān)系的線性化5. Fibonacci數(shù)列及其模型數(shù)列及其模型6. 第二類第二類Stirling數(shù)的組合意義數(shù)的組合意義7. Catalan數(shù)列及其解法數(shù)列及其解法4四、容斥原理四、容斥原理1. 容斥原理的基本形式容斥原理的基本形式(容斥原理、逐步淘汰原理容斥原理、

3、逐步淘汰原理)2. 容斥原理的應(yīng)用容斥原理的應(yīng)用(比如解決多重集排列組合問題比如解決多重集排列組合問題)3. 有限制條件的排列有限制條件的排列(比如錯(cuò)排問題、相鄰禁位排比如錯(cuò)排問題、相鄰禁位排 列問題、保位問題列問題、保位問題)5五、抽屜原理五、抽屜原理1. 抽屜原理的幾種基本形式抽屜原理的幾種基本形式2. 抽屜原理的簡單應(yīng)用抽屜原理的簡單應(yīng)用6六、波利亞六、波利亞(Plya)定理定理1.1.置換在研究等價(jià)類計(jì)數(shù)中的作用置換在研究等價(jià)類計(jì)數(shù)中的作用2.2.將置換表為輪換之積將置換表為輪換之積3.3.Burnside引理計(jì)數(shù)公式引理計(jì)數(shù)公式4. Plya定理計(jì)數(shù)公式定理計(jì)數(shù)公式5.5.Plya定

4、理的應(yīng)用定理的應(yīng)用7 1、一位學(xué)者要在一周內(nèi)安排、一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作個(gè)小時(shí)的工作時(shí)間，而且每天至少工作時(shí)間，而且每天至少工作5小時(shí)，問共有多少種安小時(shí)，問共有多少種安排方案？排方案？127 50 5,1,2,7ixxxxi 解解 問問題題相相當(dāng)當(dāng)于于不不定定方方程程 (7151,15)(21,6)CC 解解得得12715 0,1,2,7ixxxxi 即即練習(xí)題練習(xí)題8 2、n個(gè)男個(gè)男n個(gè)女排成一男女相間的隊(duì)伍，試問有個(gè)女排成一男女相間的隊(duì)伍，試問有多少種不同的方案多少種不同的方案.若圍成一圓桌坐下，又有多少種若圍成一圓桌坐下，又有多少種不同的方案？不同的方案？2 1!,!,

5、2 ( !).nnn 解解 （ ）男男士士有有種種排排法法 女女士士也也有有種種排排法法 男男女女相相間間又又分分男男在在前前或或女女在在前前兩兩種種, ,所所以以共共有有種種(2)(1)!,!,(1)!( !).nnnnnnn 先先安安排排男男士士，有有種種 然然后后在在這這 位位男男士士所所形形成成的的 個(gè)個(gè)間間隔隔中中安安排排 位位女女士士, ,有有種種 所所以以共共有有種種9 .1nrrnnnr)+ rnrrnr 證證 先先將將每每個(gè)個(gè)盒盒子子放放一一個(gè)個(gè)球球，問問題題變變?yōu)闉閷⑹ＪＳ嘤嗟牡膫€(gè)個(gè)相相同同的的球球放放到到 個(gè)個(gè)不不同同的的盒盒子子里里，其其放放球球方方案案數(shù)數(shù)為為111

6、1(-1(-1 3-1.-1nrnnrr 、 個(gè)個(gè)完完全全一一樣樣的的球球，放放到到 個(gè)個(gè)有有標(biāo)標(biāo)志志的的盒盒子子，要要求求無無一一空空盒盒，試試證證其其方方案案數(shù)數(shù)為為10 4 (2)1(2), ?m mn n 、 用用種種顏顏色色去去涂涂棋棋盤盤 每每個(gè)個(gè)方方格格涂涂一一種種顏顏色色 使使得得相相鄰鄰方方格格顏顏色色相相異異的的涂涂色色方方案案有有多多少少11,1.(1).nmmnmm m 解解 第第一一個(gè)個(gè)方方格格可可涂涂種種顏顏色色之之一一，有有種種涂涂色色方方法法；為為使使相相鄰鄰方方格格顏顏色色相相異異，只只須須使使其其余余個(gè)個(gè)方方格格的的顏顏色色異異于于它它左左邊邊相相鄰鄰的的那

7、那個(gè)個(gè)方方格格的的顏顏色色 于于是是其其余余的的每每個(gè)個(gè)方方格格都都有有種種涂涂法法 故故所所求求的的涂涂色色方方案案有有種種11(2)1(2),?m mn n 用用種種顏顏色色去去涂涂棋棋盤盤 每每個(gè)個(gè)方方格格涂涂一一種種顏顏色色，使使得得相相鄰鄰方方格格顏顏色色相相首首末末兩兩格格也也異異，的的涂涂色色若若題題目目改改方方案案色色成成：有有多多少少異異nh2(1).hm m 解解 用用表示所求方法數(shù)表示所求方法數(shù).易知易知使得相鄰格子異色的涂色方法數(shù)有使得相鄰格子異色的涂色方法數(shù)有其中使得首末兩格同色的涂色方法有其中使得首末兩格同色的涂色方法有所以所以用用m種顏色去涂種顏色去涂1 ()n

8、nm 棋盤棋盤,每格涂一種顏色每格涂一種顏色,1(1)nm m 種種,1nh 種種,11(1) (2)nnnhm mhn 從而從而1212(1)(1)( 1)(1)( 1) (1)nnnnmmmm 111222(1)(1)(1)( 1)nnnnnnhm mhm mm mh 123222(1)(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 另一解法參見教材另一解法參見教材P87例例3.5

9、.7135(2)(),()n nmnmk mnk 、安安排排女女人人和和 個(gè)個(gè)男男人人圍圍圓圓桌桌而而坐坐個(gè)個(gè)座座位位已已編編號(hào)號(hào) 使使得得任任何何兩兩個(gè)個(gè)女女人人之之間間至至少少有有個(gè)個(gè)男男人人，求求不不同同的的安安排排座座位位方方法法數(shù)數(shù). .解解 (1) 先任意選定一個(gè)女人入座，有先任意選定一個(gè)女人入座，有nm 種方法；種方法； (2) 再安排其他女人入座，使得任何兩個(gè)女人再安排其他女人入座，使得任何兩個(gè)女人之間至少有之間至少有k個(gè)空座位：個(gè)空座位：1211,(1,2,1)niiinna aanaainxaax 用用表表示示 個(gè)個(gè)女女人人的的一一種種坐坐法法，并并設(shè)設(shè)與與之之間間有有 個(gè)

10、個(gè)空空座座位位，與與之之間間有有個(gè)個(gè)空空座座位位，則則1412(1,2, )nixxxmxk in 此不定方程的解的個(gè)數(shù)為此不定方程的解的個(gè)數(shù)為()111nmnknmnkmnkn 于是完成此步驟的方法有于是完成此步驟的方法有1(1)!1nmnknn 種種.15(3) 最后安排最后安排m個(gè)男人入座，有個(gè)男人入座，有m!種方法種方法.由乘法原理，所求的安排座位方法數(shù)為由乘法原理，所求的安排座位方法數(shù)為1()!(1)!1nmnknmmnn 16 6 6、某學(xué)者每周工作、某學(xué)者每周工作6 6天天, ,共共4242小時(shí)小時(shí), ,每天工作每天工作的小時(shí)數(shù)是整數(shù)的小時(shí)數(shù)是整數(shù), ,且每天工作時(shí)間不少于且每天

11、工作時(shí)間不少于6 6小時(shí)也小時(shí)也不多于不多于8 8小時(shí)小時(shí), ,如果編排一周的工作時(shí)間表如果編排一周的工作時(shí)間表, ,問有多問有多少種不同的方案？少種不同的方案？,nnaa解解 設(shè)設(shè)有有種種不不同同的的編編排排方方法法 則則 相相應(yīng)應(yīng)的的母母函函數(shù)數(shù)為為6786( )()G xxxx 3626( )(1)G xxxx 36366(1) (1)xxx 363606(1615)() kkxxxxk1736394205(615)5kkkxxxx 42565350615555 a 42x所所以以的的系系數(shù)數(shù)11861555 141 4623361518 7、將充分多的蘋果、香蕉、橘子和梨進(jìn)行裝袋，、將

12、充分多的蘋果、香蕉、橘子和梨進(jìn)行裝袋，要求每袋中蘋果數(shù)是偶數(shù)，香蕉數(shù)是要求每袋中蘋果數(shù)是偶數(shù)，香蕉數(shù)是5 5的倍數(shù)，橘子的倍數(shù)，橘子最多最多4 4個(gè)，而梨的個(gè)數(shù)為個(gè)，而梨的個(gè)數(shù)為0 0或或1 1。如果每袋裝。如果每袋裝n個(gè)水果，個(gè)水果，求裝袋的種類數(shù)。求裝袋的種類數(shù)。 24510234( )(1)(1)(1)(1)naG xxxxxxxxxx解解 所所求求種種類類數(shù)數(shù) 的的母母函函數(shù)數(shù)為為52521111(1)111(1)xxxxxx 19001(1)nnnnnxnxn 1.nan 所所以以20 8、由字母、由字母a，b，c，d，e組成的總字母數(shù)為組成的總字母數(shù)為n的的單詞中，要求單詞中，要求

13、a與與b的個(gè)數(shù)之和為偶數(shù)，問這樣的單的個(gè)數(shù)之和為偶數(shù)，問這樣的單詞有多少個(gè)？詞有多少個(gè)？ 解解 設(shè)滿足條件的單詞個(gè)數(shù)為設(shè)滿足條件的單詞個(gè)數(shù)為an ，這樣的單詞只，這樣的單詞只有兩類：一類包括偶數(shù)個(gè)有兩類：一類包括偶數(shù)個(gè)a與偶數(shù)個(gè)與偶數(shù)個(gè)b；另一類包括；另一類包括奇數(shù)個(gè)奇數(shù)個(gè)a與奇數(shù)個(gè)與奇數(shù)個(gè)b. 因此因此an 對(duì)應(yīng)的母函數(shù)為對(duì)應(yīng)的母函數(shù)為 2422335223( )(1) (1)2!4!2!() (1)3!5!2!exxxGxxxxxxx212323()()22xxxxxxeeeeee51()2xxee001(5)2!nnnnnxxnn051()2!nnnxn 512nna 故故22 9、把、

14、把2n件相異物品放到件相異物品放到m個(gè)不同的盒中，使個(gè)不同的盒中，使得每個(gè)盒子中的物品件數(shù)均為偶數(shù)得每個(gè)盒子中的物品件數(shù)均為偶數(shù)(零也是偶數(shù)零也是偶數(shù))，求不同的放法種數(shù)求不同的放法種數(shù).解解 相應(yīng)的指母函數(shù)是相應(yīng)的指母函數(shù)是24( )(1)()2!4!2xxmmexxeeGx 22011(1)22mmxxmmxkxmmkmeeeek (2)012mk m xmkmek 001(2)!2jmjmkjmxkmkj 23001(2)!2jmjmjkmxkmkj 故所求放法數(shù)為故所求放法數(shù)為 201(2)2mnmkmkmk 2410、由數(shù)字、由數(shù)字1至至9組成的每種數(shù)字至少出現(xiàn)組成的每種數(shù)字至少出現(xiàn)

15、1次的次的 (9)n n 位數(shù)有多少個(gè)？位數(shù)有多少個(gè)？ 解解 設(shè)所求的數(shù)為設(shè)所求的數(shù)為 ,na則則 的指母函數(shù)為的指母函數(shù)為 na2399( )()(1)2!3!xexxGxxe 9(9)09( 1)kk xkek 9009( 1)(9)!nknknxkkn 259009( 1)(9)!nknnkxkkn 所以所以 (此題也可用容斥原理做此題也可用容斥原理做) 909( 1)(9)knnkakk 26 11、求由、求由0、1、2組成的長為組成的長為n的三進(jìn)制串的個(gè)數(shù)的三進(jìn)制串的個(gè)數(shù),但其中的但其中的0和和1不相鄰不相鄰(即即01和和10從不出現(xiàn)從不出現(xiàn)) 解解 設(shè)所求三進(jìn)制串的個(gè)數(shù)為設(shè)所求三進(jìn)

16、制串的個(gè)數(shù)為na ，則則 123,7aa ，3n 時(shí)時(shí)，(1)若首位是若首位是2,則此類三進(jìn)制串有則此類三進(jìn)制串有-1na個(gè)個(gè)；(2)(2)若首位是若首位是1,1,則第二位必是則第二位必是1 1或或2.2.若第二位是若第二位是2,則此類串有則此類串有-2na個(gè)個(gè)；若前二位是若前二位是1,則第三位必是則第三位必是1或或2. 若第三位是若第三位是2,則此類串有則此類串有-3na個(gè)個(gè)；27；若前；若前n- -2位是位是1,則第則第n- -1位必是位必是1或或2.若第若第n- -1位必是位必是2，則，則此類串有此類串有1a 個(gè)個(gè)；若前若前n-1位是位是1,則第則第n位必是位必是1或或2，則此類串有，則

17、此類串有2個(gè)個(gè).所以首位是所以首位是1的三進(jìn)制串有的三進(jìn)制串有23212nnaaaa 個(gè)個(gè).(3)若首位是若首位是0,同理可得三進(jìn)制串有同理可得三進(jìn)制串有23212nnaaaa 個(gè)個(gè).因此因此, 得得28 123212(2)nnnnaaaaaa 1234212(2)nnnnaaaaaa 兩式相減，得定解問題兩式相減，得定解問題 12122(3)3,7nnnaaanaa 求得通解求得通解12(12)(12)nnnaCC 代入初值得代入初值得121212,22CC 111(12)(12)2nnna 故故29 12、有多少個(gè)長度為、有多少個(gè)長度為n的的0與與1串串, 在這些串中在這些串中, 既不包含

18、子串既不包含子串010，也不包含子串，也不包含子串101？解解 設(shè)這種數(shù)串的個(gè)數(shù)為設(shè)這種數(shù)串的個(gè)數(shù)為 將滿足條件的數(shù)串分為兩類：將滿足條件的數(shù)串分為兩類： ,nf1224ff則則，3n 時(shí)時(shí)， (1) 最后兩位數(shù)字相同最后兩位數(shù)字相同. 這種長度為這種長度為n的數(shù)串可的數(shù)串可由長度為由長度為n- -1的串最后一位數(shù)字重復(fù)一次而得，故的串最后一位數(shù)字重復(fù)一次而得，故這類數(shù)串的個(gè)數(shù)這類數(shù)串的個(gè)數(shù) 1nf ； (2) 最后兩位數(shù)字不同最后兩位數(shù)字不同. 這種長度為這種長度為n的數(shù)串可的數(shù)串可由長度為由長度為n- -2的串最后一位的串最后一位(設(shè)為設(shè)為a)重復(fù)一次，再加重復(fù)一次，再加上與上與a不同的數(shù)

19、字而得不同的數(shù)字而得, 故這類數(shù)串的個(gè)數(shù)為故這類數(shù)串的個(gè)數(shù)為 2.nf 30于是得遞推關(guān)系于是得遞推關(guān)系12122, 4 nnnfffff 由由Fibonacci數(shù)列數(shù)列,得通解得通解121515()()22nnnfcc代入初值代入初值,得得 125555,55cc1121515 ()()225nnnf所所以以31 13、平面上有兩兩相交，無、平面上有兩兩相交，無3線共點(diǎn)的線共點(diǎn)的n條直線條直線,求求這這n條直線把平面分成多少個(gè)區(qū)域？條直線把平面分成多少個(gè)區(qū)域？解解 設(shè)這設(shè)這n條直線把平面分成條直線把平面分成 個(gè)區(qū)域，個(gè)區(qū)域， na易知易知 12,a 條直線把平面分成條直線把平面分成 去掉所給

20、去掉所給n條直線中的一條直線條直線中的一條直線,則剩下的則剩下的n-11na 個(gè)區(qū)域個(gè)區(qū)域. 線放回原處后線放回原處后, 于是得定解問題于是得定解問題 再把去掉的那條直再把去掉的那條直1na 則在則在的基礎(chǔ)上增加了的基礎(chǔ)上增加了n個(gè)區(qū)域個(gè)區(qū)域,112 nnaana 3221(2),(2)2nannn 解得解得顯然，當(dāng)顯然，當(dāng)n=1時(shí)，上式仍成立時(shí)，上式仍成立. 故故n條直線把平面分成條直線把平面分成 個(gè)區(qū)域個(gè)區(qū)域. 21(2)2nann 33 14、有、有2n個(gè)人排成一隊(duì)購票，票價(jià)個(gè)人排成一隊(duì)購票，票價(jià)5元。元。2n個(gè)個(gè)人中有人中有n個(gè)人有個(gè)人有5元的錢幣，另外元的錢幣，另外n個(gè)人有個(gè)人有10

21、元的錢元的錢幣。開始售票時(shí)售票處沒有準(zhǔn)備找零的錢。問有多幣。開始售票時(shí)售票處沒有準(zhǔn)備找零的錢。問有多少種列隊(duì)方式，使得只要有少種列隊(duì)方式，使得只要有10元的人買票，售票處元的人買票，售票處就有就有5元的錢幣找零？元的錢幣找零？ 解解 將有將有5元錢幣的人賦值元錢幣的人賦值1，有，有10元錢幣的人元錢幣的人賦值賦值-1，則該問題為：包括，則該問題為：包括n個(gè)個(gè)1和和n個(gè)個(gè)-1的的2n個(gè)數(shù)個(gè)數(shù)122,na aa構(gòu)成序列，使構(gòu)成序列，使120,1,2,2kaaakn 34這這2n個(gè)數(shù)的排列是多重集個(gè)數(shù)的排列是多重集1,( 1)nn 的排列，的排列，排列總數(shù)為排列總數(shù)為(2 )!.! !nn n的排列

22、是：的排列是：“從左向右掃描，出現(xiàn)從左向右掃描，出現(xiàn)- -1的累計(jì)數(shù)超的累計(jì)數(shù)超過過1的累計(jì)數(shù)的累計(jì)數(shù)”，所以存在最小的，所以存在最小的k，使，使而這些排列中，不符合要求而這些排列中，不符合要求 1210,1kkaaaa 1211,1-1.kka aa 即即使使偶偶數(shù)數(shù)，且且中中有有相相等等個(gè)個(gè)數(shù)數(shù)的的 和和將將1212,kkna aaaa 35前前k個(gè)變號(hào)后，可得到一個(gè)有個(gè)變號(hào)后，可得到一個(gè)有n+1個(gè)個(gè)1和和n-1個(gè)個(gè)-1的序列，的序列，反之，反之，n+1個(gè)個(gè)1和和n-1個(gè)個(gè)-1的序列，必存在的序列，必存在k，使得該，使得該序列的前序列的前k個(gè)數(shù)個(gè)數(shù)12,ka aa中中1的個(gè)數(shù)恰比的個(gè)數(shù)恰比

23、-1的的個(gè)數(shù)多個(gè)數(shù)多1.將這將這k個(gè)數(shù)變號(hào)，就得到一個(gè)有個(gè)數(shù)變號(hào)，就得到一個(gè)有n個(gè)個(gè)1和和n個(gè)個(gè)-1的序列，的序列，于是不合要求的排列與多重集于是不合要求的排列與多重集(1) 1,(1) ( 1)nn 的排列一一對(duì)應(yīng)的排列一一對(duì)應(yīng).這種排列有這種排列有(2 )!(1)!(1)!nnn36個(gè)個(gè). 故所求列隊(duì)方式數(shù)為故所求列隊(duì)方式數(shù)為 (2 )!(2 )!1(2 )! !(1)!(1)!(1)! !nnnn nnnnn n 21(1)nnn 37 另解另解 把有把有5角錢的人用角錢的人用1標(biāo)識(shí)標(biāo)識(shí),有有1元錢的人用元錢的人用0標(biāo)識(shí)標(biāo)識(shí),問題就轉(zhuǎn)化為問題就轉(zhuǎn)化為“由由n個(gè)個(gè)1和和n個(gè)個(gè)0組成的組成的

24、2n位排位排列中，從左向右掃描，列中，從左向右掃描，1的累計(jì)數(shù)不小于的累計(jì)數(shù)不小于0的累計(jì)的累計(jì)數(shù)數(shù)”.故所求序列數(shù)為故所求序列數(shù)為1211nnCnn 38 15、十個(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ù).解解 令令na表示表示n個(gè)元素排列成算術(shù)表達(dá)式的數(shù)目，個(gè)元素排列成算術(shù)表達(dá)式的數(shù)目，則則1212104010, 120 nnnaaaaa 210400 xx 12565,565,qq 特征方程特征方程解得特征根解得特征根

25、得通解得通解 12(565)(565)nnnacc39代入初始條件得代入初始條件得 12133 65133 65,5252cc133 65133 65(565)(565)5252nnna 故故40 16、設(shè)有地址從、設(shè)有地址從1到到n的單元，用以記錄一組信的單元，用以記錄一組信息，這個(gè)信息的每個(gè)元素都占用兩個(gè)單元，而且存息，這個(gè)信息的每個(gè)元素都占用兩個(gè)單元，而且存放的地址是完全隨機(jī)的，因而可能出現(xiàn)兩個(gè)存放信放的地址是完全隨機(jī)的，因而可能出現(xiàn)兩個(gè)存放信息單元之間留一個(gè)空單元無法存放其它信息息單元之間留一個(gè)空單元無法存放其它信息.求這求這n個(gè)單元留下空單元的平均數(shù)個(gè)單元留下空單元的平均數(shù).解解 設(shè)

26、這個(gè)平均數(shù)為設(shè)這個(gè)平均數(shù)為 na ，并設(shè)某一個(gè)信息占用了第并設(shè)某一個(gè)信息占用了第 1,2ii 兩個(gè)單元，兩個(gè)單元， 第一部分有第一部分有i個(gè)單元，這個(gè)單元，這i個(gè)單元留下空單元個(gè)單元留下空單元把這組單元剩余的單元分成兩把這組單元剩余的單元分成兩個(gè)部分，個(gè)部分，的平均數(shù)為的平均數(shù)為 第二部分有第二部分有 2ni 2n ia ，ia ，個(gè)單元，這些個(gè)單元，這些單元留下空單元的平均數(shù)為單元留下空單元的平均數(shù)為 于是某一個(gè)信于是某一個(gè)信41則留下空單元?jiǎng)t留下空單元息若占用了第息若占用了第 1,2ii 兩個(gè)單元，兩個(gè)單元，的平均數(shù)為的平均數(shù)為 2.in iaa 由于用相鄰兩個(gè)單元的幾由于用相鄰兩個(gè)單元的

27、幾率相等，故率相等，故 0213201()()()1nnnnaaaaaaan 20(1)2nnkknaa 即即310(2)2nnkknaa 又由又由 42 1201(1)(2)200,1,nnnnanaaaa 102 (1)( 1)!knknknkak 得得 解得解得（解法見教材（解法見教材P69例例3.3.7）43 17、一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一、一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)編碼字，如果它包含偶數(shù)個(gè)個(gè)編碼字，如果它包含偶數(shù)個(gè)0，就是有效的，就是有效的.求有效求有效的的n位編碼字的個(gè)數(shù)位編碼字的個(gè)數(shù)an .解解 顯然顯然 19.a 若末位數(shù)是若末位數(shù)是1到到9中某個(gè)數(shù)

28、，則前面中某個(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ù)有 441110nna 個(gè)個(gè).于是得遞推關(guān)系于是得遞推關(guān)系 11119(10)9nnnnaaaa 1118109nnnaaa 即即 解得通解解得通解 185 10,nnn

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

30、ii 種，其中使得甲恰分得一件物品的分法有種，其中使得甲恰分得一件物品的分法有 221102( 1)(22)inninini 46種，故種，故 11(33 23)(22) 3(6)223nnnnnNnnn 47 19 110, 5, . (1) . (2) . nn、 一一部部由由 樓樓上上升升到到樓樓的的電電梯梯內(nèi)內(nèi)共共有有 個(gè)個(gè)乘乘客客 該該電電梯梯從從 樓樓開開始始每每層層樓樓都都停停 以以便便讓讓乘乘客客決決定定是是否否離離開開電電梯梯求求 個(gè)個(gè)乘乘客客離離開開電電梯梯的的不不同同方方法法的的種種數(shù)數(shù)求求每每層層樓樓都都有有人人離離開開電電梯梯的的不不同同方方法法的的種種數(shù)數(shù)(1) 5

31、 6 7 8 9 106,6.nn 解解 因因?yàn)闉槊棵總€(gè)個(gè)人人可可以以選選擇擇在在 、 樓樓離離開開電電梯梯，即即每每人人離離開開電電梯梯的的方方法法有有 種種 由由乘乘法法原原理理 個(gè)個(gè)乘乘客客離離開開電電梯梯的的不不同同方方法法有有種種48(2),|6 .nSnS 令令 表表示示由由 個(gè)個(gè)乘乘客客離離開開電電梯梯的的全全部部不不同同方方法法所所成成之之集集 則則, , 4 (1,2,6), | 1,2,6iiiaSai iaPAaS aPi 設(shè)設(shè)若若在在方方法法 之之下下 沒沒有有人人在在第第樓樓離離開開電電梯梯 則則稱稱 具具有有性性質(zhì)質(zhì)令令具具有有性性質(zhì)質(zhì)|(61)5 1,2,6nni

32、Ai 則則有有 | (62)4 nnijA Aij 同同樣樣 1212, | (6) (16)kniiikA AAkiii 一一般般地地49126,666| 6543123666 210456nnnnnnnAAA 由由逐逐步步淘淘汰汰原原理理 所所求求方方案案數(shù)數(shù)為為506( 1)(6)knkkk 50 20、n個(gè)單位各派個(gè)單位各派2名代表出席一個(gè)會(huì)議，名代表出席一個(gè)會(huì)議，2n名代表圍一圓桌坐下名代表圍一圓桌坐下.試問：試問： (1) 各單位代表入座的方案有多少種各單位代表入座的方案有多少種? (2) 各單位的各單位的2位代表不相鄰的方案有多少種位代表不相鄰的方案有多少種? 解解 (1) 這是

33、這是2n個(gè)元的圓排列個(gè)元的圓排列,故各單位代表入座故各單位代表入座方式有方式有 (21)!.n 種種(2) 設(shè)這設(shè)這2n個(gè)人入座方式的全體為個(gè)人入座方式的全體為S，則，則 |(21)!.Sn S中第中第i個(gè)單位的兩個(gè)人相鄰的入座方式個(gè)單位的兩個(gè)人相鄰的入座方式 iA 設(shè)設(shè)1,2,in ，則則 51|2(22)!iAn ；2|2 (23)!, ijA Anij ；3|2 (24)!, , ,ijkA A Ani j k 互互異異；12|2 (1)!nnA AAn 由容斥原理，所求方案數(shù)為由容斥原理，所求方案數(shù)為122| (21)!2(22)!1 2 (23)!( 1)2 (1)!2nnnnAAA

34、nnnnnnn 5212123421(4),nn na aaaaaa 、求求由由個(gè)個(gè)相相異異元元作作成成的的與與不不相相鄰鄰，與與也也不不相相鄰鄰的的全全排排列列的的個(gè)個(gè)數(shù)數(shù). .解解 設(shè)所求數(shù)為設(shè)所求數(shù)為N，以，以S表示由表示由的全排列之集，的全排列之集，12,na aa作成作成|!Sn 則則以以A，B分別表示分別表示S中中1234aaaa與與 相相鄰鄰， 與與 相相鄰鄰的的全全排排列列所所成成之之集集，則則| |2(1)! |4(2)!ABnABn ，由容斥原理，由容斥原理，| (|)|NSABAB! 2(1)! 2(1)!4(2)!nnnn2(58)(2)!nnn 53 22、由、由a，

35、b，c，d四個(gè)字符組成所有四個(gè)字符組成所有n位位( (n4) )字符串中，字符串中，a，b，c，三個(gè)字母同時(shí)出現(xiàn)在一個(gè)串，三個(gè)字母同時(shí)出現(xiàn)在一個(gè)串中至少一次的這種中至少一次的這種n位字符串的個(gè)數(shù)有多少？位字符串的個(gè)數(shù)有多少？ 解解 設(shè)設(shè)S表示由表示由a，b，c，d構(gòu)成的所有構(gòu)成的所有n位字符位字符串之集。串之集。123|,|,|,Ax xS xaAx xS xbAx xS xc中中不不出出現(xiàn)現(xiàn)字字符符 中中不不出出現(xiàn)現(xiàn)字字符符 中中不不出出現(xiàn)現(xiàn)字字符符 則則54 123123| 4| | |3|2(, ,1,2,3)| 1nnnijSAAAA Aij i jA A A ，于是所求數(shù)為于是所求數(shù)

36、為 123123121323123| | (|)(|)|AAASAAAA AA AA AA A A1433 21nnn 55 23 36,1,2,36 36、 把把一一個(gè)個(gè)圓圓盤盤分分成成個(gè)個(gè)相相等等的的扇扇形形 然然后后把把這這些些數(shù)數(shù)任任意意填填入入個(gè)個(gè)扇扇形形中中, ,證證明明存存在在三三個(gè)個(gè)連連續(xù)續(xù)的的扇扇形形, ,其其中中的的數(shù)數(shù)字字之之和和至至少少是是5 56 6. .(1,2,36),36.im i 證證 用用表表示示該該圓圓盤盤上上三三個(gè)個(gè)連連續(xù)續(xù)扇扇形形上上的的數(shù)數(shù)字字之之和和 這這樣樣的的數(shù)數(shù)共共有有個(gè)個(gè)1,2,注注意意到到123636,m mm這這些些數(shù)數(shù)中中的的每每個(gè)個(gè)

37、數(shù)數(shù)都都在在作作和和數(shù)數(shù)時(shí)時(shí)出出現(xiàn)現(xiàn)了了三三次次, ,故故有有361 3(1236)1998iim 56, 56.iimm 即即存存在在某某個(gè)個(gè)使使199836,問問題題歸歸結(jié)結(jié)為為: :把把件件物物品品放放入入個(gè)個(gè)抽抽屜屜里里,)im由由抽抽屜屜原原理理知知 至至少少有有一一個(gè)個(gè)抽抽屜屜( (即即某某個(gè)個(gè)放放有有不少于不少于19985636 , 件物品件物品57 24、隨意把一個(gè)、隨意把一個(gè)39棋盤的每個(gè)方格涂成紅色棋盤的每個(gè)方格涂成紅色或藍(lán)色或藍(lán)色,證明必有兩列方格證明必有兩列方格,它們的涂色方法是一樣的它們的涂色方法是一樣的. 證證 用紅、藍(lán)兩色去涂用紅、藍(lán)兩色去涂31棋盤共有棋盤共有

38、種涂種涂色方法色方法. 328 表示第表示第i種涂色方法種涂色方法. (1,2,8)iai 以以設(shè)設(shè)K是任一個(gè)已用紅色或藍(lán)色涂了色的是任一個(gè)已用紅色或藍(lán)色涂了色的39棋盤棋盤,表示表示K的第的第i列的涂色方法列的涂色方法, 以以 (1,2,9)ibi 129, , Bbbb 設(shè)設(shè)，并令并令 | 1 28jjBb bBaj 且且與與相相同同， ， ，81 1 28,.jjjBB jBB 則則， ， ， 且且由抽屜原理由抽屜原理,必有某必有某 ,|2,ttBB 使使得得,kltbbB設(shè)設(shè)和和 是是中中的的兩兩個(gè)個(gè)元元與第與第l列的涂色方法是一樣的列的涂色方法是一樣的. 則則K的第的第k列列 25

39、(1)1152.2 (2)11102.3 (2),121.nnmmn、 證證明明：在在邊邊長長為為 的的等等邊邊三三角角形形內(nèi)內(nèi)任任意意選選擇擇 個(gè)個(gè)點(diǎn)點(diǎn)，則則存存在在 個(gè)個(gè)點(diǎn)點(diǎn)，其其間間距距離離至至多多為為證證明明：在在邊邊長長為為 的的等等邊邊三三角角形形內(nèi)內(nèi)任任意意選選擇擇個(gè)個(gè)點(diǎn)點(diǎn)，則則存存在在 個(gè)個(gè)點(diǎn)點(diǎn)，其其間間距距離離至至多多為為確確定定一一個(gè)個(gè)整整數(shù)數(shù)使使得得如如果果在在邊邊長長為為 的的等等邊邊三三角角形形內(nèi)內(nèi)任任意意選選擇擇個(gè)個(gè)點(diǎn)點(diǎn)，則則存存在在 個(gè)個(gè)點(diǎn)點(diǎn)，其其間間距距離離至至多多為為59 證證 (1)將這個(gè)等邊三角形分成將這個(gè)等邊三角形分成4個(gè)邊長為個(gè)邊長為 的的等邊三角形等

40、邊三角形.12而每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離不超過而每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離不超過12，由抽屜原理，由抽屜原理，5個(gè)點(diǎn)必有個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，個(gè)點(diǎn)在一個(gè)小三角形中，這這2個(gè)點(diǎn)的距離不超過個(gè)點(diǎn)的距離不超過1.260 (2)將這個(gè)等邊三角形分成將這個(gè)等邊三角形分成9個(gè)邊長為個(gè)邊長為 的等的等邊三角形邊三角形.13而每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離不超過而每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離不超過61 (3)將這個(gè)等邊三角形分成將這個(gè)等邊三角形分成個(gè)邊長為個(gè)邊長為 的等邊三角形的等邊三角形.1n2135(21)nn 21.nmn 故故取取即即可可由抽屜原理，由抽屜

41、原理，10個(gè)點(diǎn)必有個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，個(gè)點(diǎn)在一個(gè)小三角形中，13，這這2個(gè)點(diǎn)的距離不超過個(gè)點(diǎn)的距離不超過1.3 26、某個(gè)宴會(huì)共有、某個(gè)宴會(huì)共有2n個(gè)人出席，每個(gè)人均至少個(gè)人出席，每個(gè)人均至少認(rèn)識(shí)其中的認(rèn)識(shí)其中的n個(gè)人個(gè)人. 求證求證: 可安排這可安排這2n個(gè)人中的某個(gè)人中的某4個(gè)人圍圓桌而坐個(gè)人圍圓桌而坐, 使得每個(gè)人的旁邊都是他所認(rèn)識(shí)使得每個(gè)人的旁邊都是他所認(rèn)識(shí)的人的人. 證證 用平面上的點(diǎn)表示個(gè)人用平面上的點(diǎn)表示個(gè)人, 并以并以V表示這個(gè)點(diǎn)表示這個(gè)點(diǎn)所成之集所成之集. 對(duì)對(duì)V中的任意兩個(gè)點(diǎn)中的任意兩個(gè)點(diǎn), 如果它們表示的如果它們表示的兩個(gè)人互相認(rèn)識(shí)兩個(gè)人互相認(rèn)識(shí)(不認(rèn)識(shí)不認(rèn)識(shí)

42、), 則用紅邊則用紅邊(藍(lán)邊藍(lán)邊)把這兩把這兩個(gè)點(diǎn)連結(jié)起來個(gè)點(diǎn)連結(jié)起來, 這樣得到一個(gè)這樣得到一個(gè)2著色的著色的 2.nK 如果如果 的邊全是紅色的邊全是紅色, 則結(jié)論顯然成立則結(jié)論顯然成立; 否則否則它至少有一條藍(lán)邊，它至少有一條藍(lán)邊， 2nK設(shè)設(shè) 是一條藍(lán)邊是一條藍(lán)邊, 令令12v v12 | |Av vVv vBv vVv v 且且是是紅紅邊邊且且是是紅紅邊邊|2,ABn 則則 |,AnBn 由由題題設(shè)設(shè)，| 1,AB 如果如果| |21ABABABn 則則|2.ABn 這這與與矛矛盾盾 |2,AB 所所以以 34,vvAB 設(shè)設(shè) 1324.v v v v則則四四邊邊形形是是一一個(gè)個(gè)紅紅色色四四邊邊形形4v3v2v1v12341324,4,4v vvvv vvv所所表表示示的的 個(gè)個(gè)人人 只只要要按按的的次次序序安安排排 人人圍圍圓圓桌桌而而坐坐, ,則則可可使使得得每每個(gè)個(gè)人人的的旁旁邊邊都都是是他他所所認(rèn)認(rèn)識(shí)識(shí)的的人人. .4v3v2v1v2v4v3v1v 27 10601.:. 1 0 、 一一間間屋屋內(nèi)內(nèi)有有個(gè)個(gè)人人，它它們們當(dāng)當(dāng)中中沒沒有有人人超超過過歲歲( (年年齡齡只只能能以以整整數(shù)數(shù)給給出出) )，但但又又至