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

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

2、特征根法）2. 用待定系數(shù)法求常系數(shù)線性非齊次遞推關(guān)系的 特解(前兩種類型)3.列遞推關(guān)系解應(yīng)用題4. 一般遞推關(guān)系的線性化5. Fibonacci數(shù)列及其模型6. 第二類Stirling數(shù)的組合意義7. Catalan數(shù)列及其解法,4,四、容斥原理,1. 容斥原理的基本形式(容斥原理、逐步淘汰原理)2. 容斥原理的應(yīng)用(比如解決多重集排列組合問題)3. 有限制條件的排列(比如錯(cuò)排問題、相鄰禁位排 列問題、

3、保位問題),5,五、抽屜原理,1. 抽屜原理的幾種基本形式2. 抽屜原理的簡(jiǎn)單應(yīng)用,6,六、波利亞(Pólya)定理,1.置換在研究等價(jià)類計(jì)數(shù)中的作用2.將置換表為輪換之積3.Burnside引理計(jì)數(shù)公式4. Pólya定理計(jì)數(shù)公式5.Pólya定理的應(yīng)用,7,1、一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作時(shí)間，而且每天至少工作5小時(shí)，問共有多少種安排方案？,,練習(xí)題,8,2、n個(gè)男n個(gè)女排成一男女相

4、間的隊(duì)伍，試問有多少種不同的方案.若圍成一圓桌坐下，又有多少種不同的方案？,,9,10,11,解 用,表示所求方法數(shù).易知,使得相鄰格子異色的涂色方法數(shù)有,其中使得首末兩格同色的涂色方法有,所以,用m種顏色去涂,棋盤,每格涂一種顏色,,種,,種,,從而,12,另一解法參見教材P87例3.5.7,13,解 (1) 先任意選定一個(gè)女人入座，有,,種方法；,(2) 再安排其他女人入座，使得任何兩個(gè)女人之間至少有k個(gè)空座位：,14,,此不定

5、方程的解的個(gè)數(shù)為,,于是完成此步驟的方法有,種.,15,(3) 最后安排m個(gè)男人入座，有m!種方法.,由乘法原理，所求的安排座位方法數(shù)為,16,6、某學(xué)者每周工作6天,共42小時(shí),每天工作的小時(shí)數(shù)是整數(shù),且每天工作時(shí)間不少于6小時(shí)也不多于8小時(shí),如果編排一周的工作時(shí)間表,問有多少種不同的方案？,17,18,7、將充分多的蘋果、香蕉、橘子和梨進(jìn)行裝袋，要求每袋中蘋果數(shù)是偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多4個(gè)，而梨的個(gè)數(shù)為0或1。如果每袋裝n

6、個(gè)水果，求裝袋的種類數(shù)。,19,,20,8、由字母a，b，c，d，e組成的總字母數(shù)為n的單詞中，要求a與b的個(gè)數(shù)之和為偶數(shù)，問這樣的單詞有多少個(gè)？,解 設(shè)滿足條件的單詞個(gè)數(shù)為an ，這樣的單詞只有兩類：一類包括偶數(shù)個(gè)a與偶數(shù)個(gè)b；另一類包括奇數(shù)個(gè)a與奇數(shù)個(gè)b.,因此{(lán)an }對(duì)應(yīng)的母函數(shù)為,21,故,22,9、把2n件相異物品放到m個(gè)不同的盒中，使得每個(gè)盒子中的物品件數(shù)均為偶數(shù)(零也是偶數(shù))，求不同的放法種數(shù).,解 相應(yīng)的指母函數(shù)是,

7、23,故所求放法數(shù)為,24,10、由數(shù)字1至9組成的每種數(shù)字至少出現(xiàn)1次的,位數(shù)有多少個(gè)？,解 設(shè)所求的數(shù)為,則,的指母函數(shù)為,25,所以,(此題也可用容斥原理做),26,11、求由0、1、2組成的長(zhǎng)為n的三進(jìn)制串的個(gè)數(shù),但其中的0和1不相鄰(即01和10從不出現(xiàn)),解 設(shè)所求三進(jìn)制串的個(gè)數(shù)為,則,(1)若首位是2,則此類三進(jìn)制串有,(2)若首位是1,則第二位必是1或2.,若第二位是2,則此類串有,若前二位是1,則第三位必是1或2.,

8、若第三位是2,則此類串有,27,……；若前n-2位是1,則第n-1位必是1或2.,若第n-1位必是2，則此類串有,若前n-1位是1,則第n位必是1或2，則此類串有2個(gè).,所以首位是1的三進(jìn)制串有,個(gè).,(3)若首位是0,同理可得三進(jìn)制串有,個(gè).,因此, 得,28,兩式相減，得定解問題,求得通解,代入初值得,29,12、有多少個(gè)長(zhǎng)度為n的0與1串, 在這些串中, 既不包含子串010，也不包含子串101？,解 設(shè)這種數(shù)串的個(gè)數(shù)為,將滿足條

9、件的數(shù)串分為兩類：,(1) 最后兩位數(shù)字相同. 這種長(zhǎng)度為n的數(shù)串可由長(zhǎng)度為n-1的串最后一位數(shù)字重復(fù)一次而得，故這類數(shù)串的個(gè)數(shù),(2) 最后兩位數(shù)字不同. 這種長(zhǎng)度為n的數(shù)串可由長(zhǎng)度為n-2的串最后一位(設(shè)為a)重復(fù)一次，再加上與a不同的數(shù)字而得, 故這類數(shù)串的個(gè)數(shù)為,30,于是得遞推關(guān)系,由Fibonacci數(shù)列,得通解,代入初值,得,31,13、平面上有兩兩相交，無3線共點(diǎn)的n條直線,求這n條直線把平面分成多少個(gè)區(qū)域？,解 設(shè)這

10、n條直線把平面分成,個(gè)區(qū)域，,易知,條直線把平面分成,去掉所給n條直線中的一條直線,則剩下的n-1,個(gè)區(qū)域.,線放回原處后,,于是得定解問題,再把去掉的那條直,則在,的基礎(chǔ)上增加了n個(gè)區(qū)域,,32,解得,顯然，當(dāng)n=1時(shí)，上式仍成立.,故n條直線把平面分成,個(gè)區(qū)域.,33,14、有2n個(gè)人排成一隊(duì)購(gòu)票，票價(jià)5元。2n個(gè)人中有n個(gè)人有5元的錢幣，另外n個(gè)人有10元的錢幣。開始售票時(shí)售票處沒有準(zhǔn)備找零的錢。問有多少種列隊(duì)方式，使得只要有10

11、元的人買票，售票處就有5元的錢幣找零？,,解 將有5元錢幣的人賦值1，有10元錢幣的人賦值-1，則該問題為：包括n個(gè)1和n個(gè)-1的2n個(gè)數(shù),構(gòu)成序列，使,34,這2n個(gè)數(shù)的排列是多重集,的排列，,排列總數(shù)為,,的排列是：“從左向右掃描，出現(xiàn)-1的累計(jì)數(shù)超過1的累計(jì)數(shù)”，所以存在最小的k，使,而這些排列中，不符合要求,35,前k個(gè)變號(hào)后，可得到一個(gè)有n+1個(gè)1和n-1個(gè)-1的序列，,反之，n+1個(gè)1和n-1個(gè)-1的序列，必存在k，使得該

12、,序列的前k個(gè)數(shù),中1的個(gè)數(shù)恰比-1的,個(gè)數(shù)多1.,將這k個(gè)數(shù)變號(hào)，就得到一個(gè)有n個(gè)1和n,個(gè)-1的序列，,于是不合要求的排列與多重集,的排列一一對(duì)應(yīng).,這種排列有,36,個(gè).,故所求列隊(duì)方式數(shù)為,37,另解 把有5角錢的人用1標(biāo)識(shí),有1元錢的人用0標(biāo)識(shí),問題就轉(zhuǎn)化為“由n個(gè)1和n個(gè)0組成的2n位排列中，從左向右掃描，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)”.故所求序列數(shù)為,38,15、十個(gè)數(shù)字(0到9)和四個(gè)運(yùn)算符(+,-, *, /)組成14

13、個(gè)元素, 求由其中的n個(gè)元素的排列構(gòu)成一形式算術(shù)表達(dá)式的個(gè)數(shù).,解 令,表示n個(gè)元素排列成算術(shù)表達(dá)式的數(shù)目，,則,特征方程,解得特征根,得通解,39,代入初始條件得,故,40,16、設(shè)有地址從1到n的單元，用以記錄一組信息，這個(gè)信息的每個(gè)元素都占用兩個(gè)單元，而且存放的地址是完全隨機(jī)的，因而可能出現(xiàn)兩個(gè)存放信息單元之間留一個(gè)空單元無法存放其它信息.求這n個(gè)單元留下空單元的平均數(shù).,解 設(shè)這個(gè)平均數(shù)為,并設(shè)某一個(gè)信息占用了第,兩個(gè)單元，,

14、第一部分有i個(gè)單元，這i個(gè)單元留下空單元,把這組單元剩余的單元分成兩,個(gè)部分，,的平均數(shù)為,第二部分有,個(gè)單元，這些,單元留下空單元的平均數(shù)為,于是某一個(gè)信,41,則留下空單元,息若占用了第,兩個(gè)單元，,的平均數(shù)為,由于用相鄰兩個(gè)單元的幾,率相等，故,即,又由,42,得,解得,（解法見教材P69例3.3.7）,43,17、一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)編碼字，如果它包含偶數(shù)個(gè)0，就是有效的.求有效的n位編碼字的個(gè)數(shù)an .,解

15、 顯然,若末位數(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ù)有,44,個(gè).,于是得遞推關(guān)系,即,解得通解,代入初始條件得,故所求有效數(shù)字有,個(gè).,45,18、把 件彼此相異的物品分給甲、

16、乙、丙三人，使得甲至少分得兩件物品，乙和丙至少分得一件物品，有多少種不同的分法？,解 設(shè)有N種不同的分法. 因?yàn)榘裯件彼此相異的物品分給3個(gè)人，使得每人至少分得一件物品的方法共有,種，其中使得甲恰分得一件物品的分法有,,46,種，故,,47,48,49,50,20、n個(gè)單位各派2名代表出席一個(gè)會(huì)議，2n名代表圍一圓桌坐下.試問： (1) 各單位代表入座的方案有多少種? (2) 各單位的2位代表不相鄰的

17、方案有多少種?,解 (1) 這是2n個(gè)元的圓排列,故各單位代表入座方式有,(2) 設(shè)這2n個(gè)人入座方式的全體為S，則,{S中第i個(gè)單位的兩個(gè)人相鄰的入座方式},則,51,,由容斥原理，所求方案數(shù)為,52,解 設(shè)所求數(shù)為N，以S表示由,的全排列之集，,作成,以A，B分別表示S中,由容斥原理，,53,22、由a，b，c，d四個(gè)字符組成所有n位(n≥4)字符串中，a，b，c，三個(gè)字母同時(shí)出現(xiàn)在一個(gè)串中至少一次的這種n位字符串的個(gè)數(shù)有多少？

18、,解 設(shè)S表示由a，b，c，d構(gòu)成的所有n位字符串之集。,則,54,于是所求數(shù)為,55,56,57,24、隨意把一個(gè)3×9棋盤的每個(gè)方格涂成紅色或藍(lán)色,證明必有兩列方格,它們的涂色方法是一樣的.,設(shè)K是任一個(gè)已用紅色或藍(lán)色涂了色的3×9棋盤,,表示K的第i列的涂色方法,,以,并令,由抽屜原理,必有某,與第l列的涂色方法是一樣的.,則K的第k列,59,證 (1)將這個(gè)等邊三角形分成4個(gè)邊長(zhǎng)為 的等邊三角形.,而

19、每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離不超過,由抽屜原理，5個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，,這2個(gè)點(diǎn)的距離不超過,60,(2)將這個(gè)等邊三角形分成9個(gè)邊長(zhǎng)為 的等邊三角形.,而每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離不超過,61,(3)將這個(gè)等邊三角形分成,個(gè)邊長(zhǎng)為 的等邊三角形.,由抽屜原理，10個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，,這2個(gè)點(diǎn)的距離不超過,26、某個(gè)宴會(huì)共有2n個(gè)人出席，每個(gè)人均至少認(rèn)識(shí)其中的n個(gè)人. 求證:

20、可安排這2n個(gè)人中的某4個(gè)人圍圓桌而坐, 使得每個(gè)人的旁邊都是他所認(rèn)識(shí)的人.,證 用平面上的點(diǎn)表示個(gè)人, 并以V表示這個(gè)點(diǎn)所成之集. 對(duì)V中的任意兩個(gè)點(diǎn), 如果它們表示的兩個(gè)人互相認(rèn)識(shí)(不認(rèn)識(shí)), 則用紅邊(藍(lán)邊)把這兩個(gè)點(diǎn)連結(jié)起來, 這樣得到一個(gè)2著色的,如果 的邊全是紅色, 則結(jié)論顯然成立; 否則它至少有一條藍(lán)邊，,設(shè) 是一條藍(lán)邊, 令,如果,則,,,,,,,68,28、有n個(gè)人(n為大于等于4的偶數(shù))舉行一

21、次聚會(huì)，參加的每個(gè)人都有偶數(shù)個(gè)(有可能是0個(gè))熟人.證明：在這次聚會(huì)上有3人有相同個(gè)數(shù)的熟人.,證 用數(shù)學(xué)歸納法.,n=4時(shí)，只有三種情況：,(1)4個(gè)人互不認(rèn)識(shí)；,(2)有1個(gè)人有0個(gè)熟人，其余3人互相認(rèn)識(shí)；,(3)4人中每個(gè)人與另兩人認(rèn)識(shí).,此時(shí)無論哪種情況結(jié)論均成立.,69,假設(shè)n=k時(shí)(k為偶數(shù))存在3人，他們有相同個(gè)數(shù)的熟人.則當(dāng)n=k+2時(shí)，有如下情況：,(1)有0個(gè)人有0個(gè)熟人；(2)有1個(gè)人有0個(gè)熟人；(3)有2個(gè)人