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

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

6、某學(xué)者每周工作6天,共42小時(shí),每天工作的小時(shí)數(shù)是整數(shù),且每天工作時(shí)間不少于6小時(shí)也不多于8小時(shí),如果編排一周的工作時(shí)間表,問(wèn)有多少種不同的方案？16177、將充分多的蘋果、香蕉、橘子和梨進(jìn)行裝袋，要求每袋中蘋果數(shù)是偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多4個(gè)，而梨的個(gè)數(shù)為0或1。如果每袋裝n個(gè)水果，求裝袋的種類數(shù)。18198、由字母a，b，c，d，e組成的總字母數(shù)為n的單詞中，要求a與b的個(gè)數(shù)之和為偶數(shù)，問(wèn)這樣的單詞有多少個(gè)？解設(shè)滿足條件的單詞個(gè)數(shù)為an

，這樣的單詞只有兩類：一類包括偶數(shù)個(gè)a與偶數(shù)個(gè)b；另一類包括奇數(shù)個(gè)a與奇數(shù)個(gè)b.

因此{(lán)an

}對(duì)應(yīng)的母函數(shù)為

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

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

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

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

由于用相鄰兩個(gè)單元的幾率相等，故

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

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

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

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

(3)將這個(gè)等邊三角形分成個(gè)邊長(zhǎng)為的等邊三角形.由抽屜原理，10個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，這2個(gè)點(diǎn)的距離不超過(guò)6026、某個(gè)宴會(huì)共有2n個(gè)人出席，每個(gè)人均至少認(rèn)識(shí)其中的n個(gè)人.求證:可安排這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é)起來(lái),這樣得到一個(gè)2著色的如果的邊全是紅色,則結(jié)論顯然成立;否則它至少有一條藍(lán)邊，設(shè)是一條藍(lán)邊,令如果則28、有n個(gè)人(n為大于等于4的偶數(shù))舉行一次聚會(huì)，參加的每個(gè)人都有偶數(shù)個(gè)(有可能是0個(gè))熟人.證明：在這次聚會(huì)上有3人有相同個(gè)數(shù)的熟人.證用數(shù)學(xué)歸納法.n=4時(shí)，只有三種情況：(1)4