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

1、1,組合數(shù)學(xué)復(fù)習(xí)要點,一、排列組合,1. 排列和組合的基本性質(zhì)2. 排列組合的計數(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ù)解的個數(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. 有限制條件的排列(比如錯排問題、相鄰禁位排 列問題、

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

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

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

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

7、23,故所求放法數(shù)為,24,10、由數(shù)字1至9組成的每種數(shù)字至少出現(xiàn)1次的,位數(shù)有多少個？,解 設(shè)所求的數(shù)為,則,的指母函數(shù)為,25,所以,(此題也可用容斥原理做),26,11、求由0、1、2組成的長為n的三進制串的個數(shù),但其中的0和1不相鄰(即01和10從不出現(xiàn)),解 設(shè)所求三進制串的個數(shù)為,則,(1)若首位是2,則此類三進制串有,(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個.,所以首位是1的三進制串有,個.,(3)若首位是0,同理可得三進制串有,個.,因此, 得,28,兩式相減，得定解問題,求得通解,代入初值得,29,12、有多少個長度為n的0與1串, 在這些串中, 既不包含子串010，也不包含子串101？,解 設(shè)這種數(shù)串的個數(shù)為,將滿足條

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

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

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

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

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

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

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

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

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

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

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

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

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