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

組合(zǔhé)數(shù)學(xué)復(fù)習(xí)要點(diǎn)一、排列組合1.排列和組合的根本性質(zhì)2.排列組合的計(jì)數(shù)(jìshù)公式，多重集的排列數(shù)和組合數(shù)的求法3.應(yīng)用第一頁(yè)，共72頁(yè)。1二、母函數(shù)(hánshù)1.母函數(shù)與數(shù)列的關(guān)系2.母函數(shù)與排列數(shù)、組合數(shù)的關(guān)系3.用普通型母函數(shù)解決多重集的組合問(wèn)題4.用指數(shù)(zhǐshù)型母函數(shù)解決多重集的排列問(wèn)題5.用母函數(shù)解遞推關(guān)系式6.不定方程的整數(shù)解的個(gè)數(shù)與多重集的組合數(shù)之關(guān)系第二頁(yè)，共72頁(yè)。2三、遞推關(guān)系(guānxì)1.常系數(shù)線(xiàn)性遞推關(guān)系的解法(jiěfǎ)〔特征根法〕2.用待定系數(shù)法求常系數(shù)線(xiàn)性非齊次遞推關(guān)系的特解(前兩種類(lèi)型)3.列遞推關(guān)系解應(yīng)用題4.一般遞推關(guān)系的線(xiàn)性化5.Fibonacci數(shù)列及其模型6.第二類(lèi)Stirling數(shù)的組合意義7.Catalan數(shù)列及其解法(jiěfǎ)第三頁(yè)，共72頁(yè)。3四、容斥原理(yuánlǐ)1.容斥原理的根本形式(容斥原理、逐步淘汰原理)2.容斥原理的應(yīng)用(比方解決多重集排列(páiliè)組合問(wèn)題)3.有限制條件的排列(páiliè)(比方錯(cuò)排問(wèn)題、相鄰禁位排列問(wèn)題、保位問(wèn)題)第四頁(yè)，共72頁(yè)。4五、抽屜(chōuti)原理1.抽屜原理的幾種根本(gēnběn)形式2.抽屜原理的簡(jiǎn)單應(yīng)用第五頁(yè)，共72頁(yè)。5六、波利亞(Pólya)定理(dìnglǐ)3.Burnside引理計(jì)數(shù)公式4.Pólya定理(dìnglǐ)計(jì)數(shù)公式5.Pólya定理(dìnglǐ)的應(yīng)用第六頁(yè)，共72頁(yè)。61、一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作時(shí)間，而且每天至少工作5小時(shí)，問(wèn)共有(ɡònɡyǒu)多少種安排方案？練習(xí)題第七頁(yè)，共72頁(yè)。72、n個(gè)男n個(gè)女排成一男女相間的隊(duì)伍，試問(wèn)有多少(duōshǎo)種不同的方案.假設(shè)圍成一圓桌坐下，又有多少(duōshǎo)種不同的方案？第八頁(yè)，共72頁(yè)。8第九頁(yè)，共72頁(yè)。9第十頁(yè)，共72頁(yè)。10解用表示(biǎoshì)所求方法數(shù).易知使得(shǐde)相鄰格子異色的涂色方法數(shù)有其中使得(shǐde)首末兩格同色的涂色方法有所以用m種顏色去涂棋盤(pán),每格涂一種顏色,種,種,從而第十一頁(yè)，共72頁(yè)。11另一解法參見(jiàn)(cānjiàn)教材P87例第十二頁(yè)，共72頁(yè)。12解(1)先任意(rènyì)選定一個(gè)女人入座，有種方法(fāngfǎ)；(2)再安排其他(qítā)女人入座，使得任何兩個(gè)女人之間至少有k個(gè)空座位：第十三頁(yè)，共72頁(yè)。13此不定(bùdìng)方程的解的個(gè)數(shù)為于是(yúshì)完成此步驟的方法有種.第十四頁(yè)，共72頁(yè)。14(3)最后安排m個(gè)男人入座(rùzuò)，有m!種方法.由乘法原理(yuánlǐ)，所求的安排座位方法數(shù)為第十五頁(yè)，共72頁(yè)。156、某學(xué)者每周工作6天,共42小時(shí),每天工作的小時(shí)數(shù)是整數(shù),且每天工作時(shí)間不少(bùshǎo)于6小時(shí)也不多于8小時(shí),如果編排一周的工作時(shí)間表,問(wèn)有多少種不同的方案？第十六頁(yè)，共72頁(yè)。16第十七頁(yè)，共72頁(yè)。177、將充分多的蘋(píng)果(píngguǒ)、香蕉、橘子和梨進(jìn)行裝袋，要求每袋中蘋(píng)果(píngguǒ)數(shù)是偶數(shù)，香蕉數(shù)是5的倍數(shù)，橘子最多4個(gè)，而梨的個(gè)數(shù)為0或1。如果每袋裝n個(gè)水果，求裝袋的種類(lèi)數(shù)。第十八頁(yè)，共72頁(yè)。18第十九頁(yè)，共72頁(yè)。198、由字母a，b，c，d，e組成(zǔchénɡ)的總字母數(shù)為n的單詞中，要求a與b的個(gè)數(shù)之和為偶數(shù)，問(wèn)這樣的單詞有多少個(gè)？解設(shè)滿(mǎn)足條件的單詞個(gè)數(shù)為an，這樣(zhèyàng)的單詞只有兩類(lèi)：一類(lèi)包括偶數(shù)個(gè)a與偶數(shù)個(gè)b；另一類(lèi)包括奇數(shù)個(gè)a與奇數(shù)個(gè)b.因此(yīncǐ){an}對(duì)應(yīng)的母函數(shù)為第二十頁(yè)，共72頁(yè)。20故第二十一頁(yè)，共72頁(yè)。219、把2n件相異(xiānɡyì)物品放到m個(gè)不同的盒中，使得每個(gè)盒子中的物品件數(shù)均為偶數(shù)(零也是偶數(shù))，求不同的放法種數(shù).解相應(yīng)(xiāngyīng)的指母函數(shù)是第二十二頁(yè)，共72頁(yè)。22故所求放法數(shù)為第二十三頁(yè)，共72頁(yè)。2310、由數(shù)字1至9組成(zǔchénɡ)的每種數(shù)字至少出現(xiàn)1次的位數(shù)有多少(duōshǎo)個(gè)？解設(shè)所求的數(shù)為那么(nàme)的指母函數(shù)為第二十四頁(yè)，共72頁(yè)。24所以(suǒyǐ)(此題也可用容斥原理(yuánlǐ)做)第二十五頁(yè)，共72頁(yè)。2511、求由0、1、2組成的長(zhǎng)為n的三進(jìn)制串的個(gè)數(shù),但其中的0和1不相鄰(即01和10從不(cónɡbù)出現(xiàn))解

設(shè)所求三進(jìn)制串的個(gè)數(shù)為那么(nàme)(1)假設(shè)(jiǎshè)首位是2,那么此類(lèi)三進(jìn)制串有(2)假設(shè)首位是1,那么第二位必是1或2.假設(shè)第二位是2,那么此類(lèi)串有假設(shè)前二位是1,那么第三位必是1或2.假設(shè)第三位是2,那么此類(lèi)串有第二十六頁(yè)，共72頁(yè)。26……；假設(shè)(jiǎshè)前n-2位是1,那么第n-1位必是1或2.假設(shè)(jiǎshè)第n-1位必是2，那么此類(lèi)串有假設(shè)(jiǎshè)前n-1位是1,那么第n位必是1或2，那么此類(lèi)串有2個(gè).所以首位是1的三進(jìn)制串有個(gè).(3)假設(shè)首位是0,同理可得三進(jìn)制串有個(gè).因此,得第二十七頁(yè)，共72頁(yè)。27兩式相減，得定解問(wèn)題(wèntí)求得通解(tōngjiě)代入初值得(zhídé)第二十八頁(yè)，共72頁(yè)。2812、有多少(duōshǎo)個(gè)長(zhǎng)度為n的0與1串,在這些串中,既不包含子串010，也不包含子串101？解設(shè)這種數(shù)串的個(gè)數(shù)為將滿(mǎn)足條件的數(shù)串分為(fēnwéi)兩類(lèi)：(1)最后兩位數(shù)字相同.這種長(zhǎng)度為n的數(shù)串可由長(zhǎng)度為n-1的串最后一位數(shù)字重復(fù)一次而得，故這類(lèi)數(shù)串的個(gè)數(shù)

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

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

于是某一個(gè)信第四十頁(yè)，共72頁(yè)。40那么留下(liúxià)空單元息假設(shè)(jiǎshè)占用了第兩個(gè)(liǎnɡɡè)單元，的平均數(shù)為

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

即又由第四十一頁(yè)，共72頁(yè)。41得解得〔解法(jiěfǎ)見(jiàn)教材P69例〕第四十二頁(yè)，共72頁(yè)。4217、一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)編碼字，如果它包含偶數(shù)(ǒushù)個(gè)0，就是有效的.求有效的n位編碼字的個(gè)數(shù)an.解顯然(xiǎnrán)假設(shè)末位數(shù)是1到9中某個(gè)數(shù)，那么前面(qiánmian)n-1位組成的有效數(shù)有an-1個(gè)，因此，末位數(shù)不是0的n位有效數(shù)字有9an-1個(gè).假設(shè)末位數(shù)是0，那么這樣的n位十進(jìn)制數(shù)有10n-1個(gè)，而不是有效數(shù)的有an-1個(gè)(因n-1位的有效數(shù)后面添一個(gè)0就不是有效數(shù)了),所以末位數(shù)是0的有效數(shù)有

第四十三頁(yè)，共72頁(yè)。43個(gè).于是(yúshì)得遞推關(guān)系即解得通解(tōngjiě)代入初始條件得故所求有效數(shù)字(yǒuxiàoshùzì)有個(gè).第四十四頁(yè)，共72頁(yè)。4418、把件彼此相異的物品(wùpǐn)分給甲、乙、丙三人，使得甲至少分得兩件物品(wùpǐn)，乙和丙至少分得一件物品(wùpǐn)，有多少種不同的分法？解設(shè)有N種不同的分法.因?yàn)榘裯件彼此相異的物品分給3個(gè)人，使得每人至少(zhìshǎo)分得一件物品的方法共有種，其中使得(shǐde)甲恰分得一件物品的分法有第四十五頁(yè)，共72頁(yè)。45種，故第四十六頁(yè)，共72頁(yè)。46第四十七頁(yè)，共72頁(yè)。47第四十八頁(yè)，共72頁(yè)。48第四十九頁(yè)，共72頁(yè)。4920、n個(gè)單位各派2名代表出席一個(gè)會(huì)議，2n名代表圍一圓桌坐下.試問(wèn)(shìwèn)：(1)各單位代表入座的方案有多少種?(2)各單位的2位代表不相鄰的方案有多少種?解(1)這是2n個(gè)元的圓排列,故各單位代表入座方式有(2)設(shè)這2n個(gè)人入座方式(fāngshì)的全體為S，那么{S中第i個(gè)單位的兩個(gè)人相鄰的入座方式}那么(nàme)第五十頁(yè)，共72頁(yè)。50由容斥原理(yuánlǐ)，所求方案數(shù)為第五十一頁(yè)，共72頁(yè)。51解設(shè)所求數(shù)為N，以S表示(biǎoshì)由的全排列(páiliè)之集，作成(zuòchéng)以A，B分別表示S中由容斥原理，第五十二頁(yè)，共72頁(yè)。5222、由a，b，c，d四個(gè)字符組成所有(suǒyǒu)n位(n≥4)字符串中，a，b，c，三個(gè)字母同時(shí)出現(xiàn)在一個(gè)串中至少一次的這種n位字符串的個(gè)數(shù)有多少？解設(shè)S表示由a，b，c，d構(gòu)成(gòuchéng)的所有n位字符串之集。那么(nàme)第五十三頁(yè)，共72頁(yè)。53于是(yúshì)所求數(shù)為第五十四頁(yè)，共72頁(yè)。54第五十五頁(yè)，共72頁(yè)。55第五十六頁(yè)，共72頁(yè)。5624、隨意把一個(gè)3×9棋盤(pán)的每個(gè)方格(fānɡɡé)涂成紅色或藍(lán)色,證明必有兩列方格(fānɡɡé),它們的涂色方法是一樣的.證用紅、藍(lán)兩色去涂3×1棋盤(pán)共有種涂色方法.表示第i種涂色方法.以設(shè)K是任一個(gè)(yīɡè)已用紅色或藍(lán)色涂了色的3×9棋盤(pán),表示(biǎoshì)K的第i列的涂色方法,以并令由抽屜原理,必有某與第l列的涂色方法是一樣的.那么K的第k列第五十七頁(yè)，共72頁(yè)。57第五十八頁(yè)，共72頁(yè)。58證(1)將這個(gè)(zhège)等邊三角形分成4個(gè)邊長(zhǎng)為的等邊三角形.而每個(gè)小等邊三角形內(nèi)任意(rènyì)兩點(diǎn)之間的距離不超過(guò)由抽屜原理(yuánlǐ)，5個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，這2個(gè)點(diǎn)的距離不超過(guò)第五十九頁(yè)，共72頁(yè)。59(2)將這個(gè)(zhège)等邊三角形分成9個(gè)邊長(zhǎng)為的等邊三角形.而每個(gè)小等邊三角形內(nèi)任意兩點(diǎn)之間的距離(jùlí)不超過(guò)第六十頁(yè)，共72頁(yè)。60(3)將這個(gè)(zhège)等邊三角形分成個(gè)邊長(zhǎng)為的等邊三角形.由抽屜原理(yuánlǐ)，10個(gè)點(diǎn)必有2個(gè)點(diǎn)在一個(gè)小三角形中，這2個(gè)點(diǎn)的距離(jùlí)不超過(guò)第六十一頁(yè)，共72頁(yè)。6126、某個(gè)宴會(huì)共有2n個(gè)人出席，每個(gè)人均(rénjūn)至少認(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)邊,令第六十二頁(yè)，共72頁(yè)。62如果(rúguǒ)那么(nàme)第六十三頁(yè)，共72頁(yè)。63第六十