研究生組合數(shù)學復習要點

研究生組合數(shù)學復習要點二、母函數(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ù)之2三、遞推關(guān)系1.常系數(shù)線性遞推關(guān)系的解法（特征根法）2.用待定系數(shù)法求常系數(shù)線性非齊次遞推關(guān)系的特解(前兩種類型)3.列遞推關(guān)系解應(yīng)用題4.一般遞推關(guān)系的線性化5.Fibonacci數(shù)列及其模型6.第二類Stirling數(shù)的組合意義7.Catalan數(shù)列及其解法3四、容斥原理1.容斥原理的基本形式(容斥原理、逐步淘汰原理)2.容斥原理的應(yīng)用(比如解決多重集排列組合問題)3.有限制條件的排列(比如錯排問題、相鄰禁位排列問題、保位問題)4五、抽屜原理1.抽屜原理的幾種基本形式2.抽屜原理的簡單應(yīng)用5六、波利亞(Pólya)定理1.置換在研究等價類計數(shù)中的作用2.將置換表為輪換之積3.Burnside引理計數(shù)公式4.Pólya定理計數(shù)公式5.Pólya定理的應(yīng)用61、一位學者要在一周內(nèi)安排50個小時的工作時間，而且每天至少工作5小時，問共有多少種安排方案？練習題72、n個男n個女排成一男女相間的隊伍，試問有多少種不同的方案.若圍成一圓桌坐下，又有多少種不同的方案？8910解用表示所求方法數(shù).易知使得相鄰格子異色的涂色方法數(shù)有其中使得首末兩格同色的涂色方法有所以用m種顏色去涂棋盤,每格涂一種顏色,種,種,從而11另一解法參見教材P87例12解(1)先任意選定一個女人入座，有種方法；(2)再安排其他女人入座，使得任何兩個女人之間至少有k個空座位：13此不定方程的解的個數(shù)為于是完成此步驟的方法有種.14(3)最后安排m個男人入座，有m!種方法.由乘法原理，所求的安排座位方法數(shù)為15

6、某學者每周工作6天,共42小時,每天工作的小時數(shù)是整數(shù),且每天工作時間不少于6小時也不多于8小時,如果編排一周的工作時間表,問有多少種不同的方案？16177、將充分多的蘋果、香蕉、橘子和梨進行裝袋，要求每袋中蘋果數(shù)是偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多4個，而梨的個數(shù)為0或1。如果每袋裝n個水果，求裝袋的種類數(shù)。18198、由字母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ù)為

20故219、把2n件相異物品放到m個不同的盒中，使得每個盒子中的物品件數(shù)均為偶數(shù)(零也是偶數(shù))，求不同的放法種數(shù).解相應(yīng)的指母函數(shù)是22故所求放法數(shù)為2310、由數(shù)字1至9組成的每種數(shù)字至少出現(xiàn)1次的位數(shù)有多少個？解設(shè)所求的數(shù)為則的指母函數(shù)為24所以(此題也可用容斥原理做)2511、求由0、1、2組成的長為n的三進制串的個數(shù),但其中的0和1不相鄰(即01和10從不出現(xiàn))解

設(shè)所求三進制串的個數(shù)為則(1)若首位是2,則此類三進制串有(2)若首位是1,則第二位必是1或2.若第二位是2,則此類串有若前二位是1,則第三位必是1或2.若第三位是2,則此類串有26……；若前n-2位是1,則第n-1位必是1或2.若第n-1位必是2，則此類串有若前n-1位是1,則第n位必是1或2，則此類串有2個.所以首位是1的三進制串有個.(3)若首位是0,同理可得三進制串有個.因此,得27兩式相減，得定解問題求得通解代入初值得2812、有多少個長度為n的0與1串,在這些串中,既不包含子串010，也不包含子串101？解設(shè)這種數(shù)串的個數(shù)為將滿足條件的數(shù)串分為兩類：(1)最后兩位數(shù)字相同.這種長度為n的數(shù)串可由長度為n-1的串最后一位數(shù)字重復一次而得，故這類數(shù)串的個數(shù)

(2)最后兩位數(shù)字不同.這種長度為n的數(shù)串可由長度為n-2的串最后一位(設(shè)為a)重復一次，再加上與a不同的數(shù)字而得,故這類數(shù)串的個數(shù)為29于是得遞推關(guān)系由Fibonacci數(shù)列,得通解代入初值,得3013、平面上有兩兩相交，無3線共點的n條直線,求這n條直線把平面分成多少個區(qū)域？解設(shè)這n條直線把平面分成個區(qū)域，易知條直線把平面分成去掉所給n條直線中的一條直線,則剩下的n-1個區(qū)域.線放回原處后,于是得定解問題再把去掉的那條直則在的基礎(chǔ)上增加了n個區(qū)域,31解得顯然，當n=1時，上式仍成立.故n條直線把平面分成個區(qū)域.3214、有2n個人排成一隊購票，票價5元。2n個人中有n個人有5元的錢幣，另外n個人有10元的錢幣。開始售票時售票處沒有準備找零的錢。問有多少種列隊方式，使得只要有10元的人買票，售票處就有5元的錢幣找零？解將有5元錢幣的人賦值1，有10元錢幣的人賦值-1，則該問題為：包括n個1和n個-1的2n個數(shù)構(gòu)成序列，使33這2n個數(shù)的排列是多重集的排列，排列總數(shù)為的排列是：“從左向右掃描，出現(xiàn)-1的累計數(shù)超過1的累計數(shù)”，所以存在最小的k，使而這些排列中，不符合要求34前k個變號后，可得到一個有n+1個1和n-1個-1的序列，反之，n+1個1和n-1個-1的序列，必存在k，使得該序列的前k個數(shù)中1的個數(shù)恰比-1的個數(shù)多1.將這k個數(shù)變號，就得到一個有n個1和n個-1的序列，于是不合要求的排列與多重集的排列一一對應(yīng).這種排列有35個.故所求列隊方式數(shù)為36另解把有5角錢的人用1標識,有1元錢的人用0標識,問題就轉(zhuǎn)化為“由n個1和n個0組成的2n位排列中，從左向右掃描，1的累計數(shù)不小于0的累計數(shù)”.故所求序列數(shù)為3715、十個數(shù)字(0到9)和四個運算符(+,-,*,/)組成14個元素,求由其中的n個元素的排列構(gòu)成一形式算術(shù)表達式的個數(shù).解令表示n個元素排列成算術(shù)表達式的數(shù)目，則特征方程解得特征根得通解38代入初始條件得故3916、設(shè)有地址從1到n的單元，用以記錄一組信息，這個信息的每個元素都占用兩個單元，而且存放的地址是完全隨機的，因而可能出現(xiàn)兩個存放信息單元之間留一個空單元無法存放其它信息.求這n個單元留下空單元的平均數(shù).解設(shè)這個平均數(shù)為并設(shè)某一個信息占用了第兩個單元，第一部分有i個單元，這i個單元留下空單元把這組單元剩余的單元分成兩個部分，的平均數(shù)為

第二部分有個單元，這些單元留下空單元的平均數(shù)為

于是某一個信40則留下空單元息若占用了第

兩個單元，的平均數(shù)為

由于用相鄰兩個單元的幾率相等，故

即又由41得解得（解法見教材P69例）4217、一個計算機系統(tǒng)把一個十進制數(shù)字串作為一個編碼字，如果它包含偶數(shù)個0，就是有效的.求有效的n位編碼字的個數(shù)an.解顯然若末位數(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ù)有

43個.于是得遞推關(guān)系即解得通解代入初始條件得故所求有效數(shù)字有個.4418、把件彼此相異的物品分給甲、乙、丙三人，使得甲至少分得兩件物品，乙和丙至少分得一件物品，有多少種不同的分法？解設(shè)有N種不同的分法.因為把n件彼此相異的物品分給3個人，使得每人至少分得一件物品的方法共有種，其中使得甲恰分得一件物品的分法有45種，故4647484920、n個單位各派2名代表出席一個會議，2n名代表圍一圓桌坐下.試問：(1)各單位代表入座的方案有多少種?(2)各單位的2位代表不相鄰的方案有多少種?解(1)這是2n個元的圓排列,故各單位代表入座方式有(2)設(shè)這2n個人入座方式的全體為S，則{S中第i個單位的兩個人相鄰的入座方式}則50由容斥原理，所求方案數(shù)為51解設(shè)所求數(shù)為N，以S表示由的全排列之集，作成以A，B分別表示S中由容斥原理，5222、由a，b，c，d四個字符組成所有n位(n≥4)字符串中，a，b，c，三個字母同時出現(xiàn)在一個串中至少一次的這種n位字符串的個數(shù)有多少？解

設(shè)S表示由a，b，c，d構(gòu)成的所有n位字符串之集。則53于是所求數(shù)為54555624、隨意把一個3×9棋盤的每個方格涂成紅色或藍色,證明必有兩列方格,它們的涂色方法是一樣的.證用紅、藍兩色去涂3×1棋盤共有種涂色方法.表示第i種涂色方法.以設(shè)K是任一個已用紅色或藍色涂了色的3×9棋盤,表示K的第i列的涂色方法,以并令由抽屜原理,必有某與第l列的涂色方法是一樣的.則K的第k列57證(1)將這個等邊三角形分成4個邊長為的等邊三角形.而每個小等邊三角形內(nèi)任意兩點之間的距離不超過由抽屜原理，5個點必有2個點在一個小三角形中，這2個點的距離不超過58

(2)將這個等邊三角形分成9個邊長為的等邊三角形.而每個小等邊三角形內(nèi)任意兩點之間的距離不超過59

(3)將這個等邊三角形分成個邊長為的等邊三角形.由抽屜原理，10個點必有2個點在一個小三角形中，這2個點的距離不超過6026、某個宴會共有2n個人出席，每個人均至少認識其中的n個人.求證:可安排這2n個人中的某4個人圍圓桌而坐,使得每個人的旁邊都是他所認識的人.證用平面上的點表示個人,并以V表示這個點所成之集.對V中的任意兩個點,如果它們表示的兩個人互相認識(不認識),則用紅邊(藍邊)把這兩個點連結(jié)起來,這樣得到一個2著色的如果的邊全是紅色,則結(jié)論顯然成立;否則它至少有一條藍邊，設(shè)是一條藍邊,令如果則28、有n個人(n為大于等于4的偶數(shù))舉行一次聚會，參加的每個人都有偶數(shù)個(有可能是0個)熟人.證明：在這次聚會上有3人有相同個數(shù)的熟人.證用數(shù)學歸納法.n=4時，只有三種情況：(1)4