2015級(jí)組合數(shù)學(xué)復(fù)習(xí)題解答

2015級(jí)組合數(shù)學(xué)(shùxué)復(fù)習(xí)題解答第一頁(yè)，共50頁(yè)。(2)所選出的6根木棍實(shí)際上可將這20根排成一行的木棍分割(fēngē)成7段(加上首和尾).設(shè)所選左邊第1根木棍的左側(cè)有x1根未被選中的木棍；在第1與第2根所選木棍之間有x2根未被選中的木棍；…；在第5與第6根所選木棍之間有x6根未被選中的木棍；在第6根所選木棍的右側(cè)有x7根未被選中的木棍，那么由于沒(méi)有兩根選出的木棍是相鄰的，所以第二頁(yè)，共50頁(yè)。2作變量(biànliàng)代換那么(nàme)原方程變成這個(gè)方程的非負(fù)整數(shù)(zhěngshù)解的個(gè)數(shù)即為所求的選擇數(shù)第三頁(yè)，共50頁(yè)。3(3)同(2)中的分析，此時(shí)有不定(bùdìng)方程仿照(2)，這個(gè)(zhège)方程的非負(fù)整數(shù)解的個(gè)數(shù)即為所求的選擇數(shù)第四頁(yè)，共50頁(yè)。42.(1)在2n個(gè)物體中有n個(gè)是相同的，那么從這2n個(gè)物體中選取(xuǎnqǔ)n個(gè)的方法有幾種？(2)在3n+1個(gè)物體中有n個(gè)是相同的，那么從這3n+1個(gè)物體中選取(xuǎnqǔ)n個(gè)的方法有幾種？解(1)若選出的物體有

個(gè)不相同(xiānɡtónɡ),那么其余n-k個(gè)是相同(xiānɡtónɡ)的,所以選取的方法數(shù)為(2)類似于(1)的分析(fēnxī)可知，所以選取的方法數(shù)為第五頁(yè)，共50頁(yè)。53.用

種顏色去涂

棋盤(pán)，每格涂一種顏色，求使得相鄰格子異色，首末兩格也異色的涂色方法數(shù).解

用hn表示所求方法數(shù).易知用m種顏色去涂

棋盤(pán)，每格涂一種顏色，使得相鄰格子異色的涂色方法數(shù)有種,其中使得首末兩格同色的涂色方法有

種,所以從而(cóngér)第六頁(yè)，共50頁(yè)。6第七頁(yè)，共50頁(yè)。74.用

種顏色去涂

棱錐的n+1個(gè)頂點(diǎn),每個(gè)頂點(diǎn)涂一種顏色，求使得棱錐的每條棱的兩個(gè)端點(diǎn)異色的涂色方法數(shù)解設(shè)V是一個(gè)n棱錐,那么可依如下兩個(gè)步驟(bùzhòu)去完成V的n+1個(gè)頂點(diǎn)的涂色工作:先涂頂點(diǎn)v0,有m種涂色方法;然后(ránhòu)用異于v0顏色的m-1種顏色去涂頂點(diǎn)序列v1，v2，…，vn,使得相鄰頂點(diǎn)異色且首末兩個(gè)頂點(diǎn)也異色.第八頁(yè)，共50頁(yè)。8由上題可知,完成此步驟(bùzhòu)的方法有種，由乘法(chéngfǎ)原理,得所求涂色方法數(shù)為第九頁(yè)，共50頁(yè)。95.將充分多的蘋(píng)果(píngguǒ)、香蕉、橘子和梨這4種水果裝袋，要求各袋有偶數(shù)個(gè)蘋(píng)果(píngguǒ)，最多2個(gè)橘子，3的倍數(shù)個(gè)香蕉，最多1個(gè)梨.如果每袋裝n個(gè)水果，求裝袋的種類數(shù).第十頁(yè)，共50頁(yè)。10第十一頁(yè)，共50頁(yè)。116.把n個(gè)相異的球放到4個(gè)相異盒子中，求使得含有奇數(shù)個(gè)球，含有偶數(shù)個(gè)球的不同的放球方法數(shù).則數(shù)列對(duì)應(yīng)的指母函數(shù)為解設(shè)滿足條件的放球方法數(shù)為第十二頁(yè)，共50頁(yè)。12所以(suǒyǐ)第十三頁(yè)，共50頁(yè)。137.由數(shù)字1至9組成的每種數(shù)字至少出現(xiàn)1次的

位數(shù)有多少個(gè)？解設(shè)所求的數(shù)為an,那么(nàme){an}的指母函數(shù)為所以(suǒyǐ)第十四頁(yè)，共50頁(yè)。148.由字母a,b,c,d,e組成的總字母數(shù)為n的單詞(dāncí)中，要求a與b的個(gè)數(shù)之和為偶數(shù)，求這樣的單詞(dāncí)的個(gè)數(shù).解這樣的單詞(dāncí)有兩類：一類包括偶數(shù)個(gè)a與偶數(shù)個(gè)b；另一類包括奇數(shù)個(gè)a與奇數(shù)個(gè)b.設(shè)所求的數(shù)為an,那么{an}的指母函數(shù)為第十五頁(yè)，共50頁(yè)。15故第十六頁(yè)，共50頁(yè)。169.有多少個(gè)長(zhǎng)度(chángdù)為n的0與1串,在這些串中,既不包含子串010，也不包含子串101？解設(shè)這種數(shù)串的個(gè)數(shù)為將滿足條件的數(shù)串分為(fēnwéi)兩類：(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ù)為第十七頁(yè)，共50頁(yè)。17于是(yúshì)得遞推關(guān)系由Fibonacci數(shù)列(shùliè),得通解代入初值,得第十八頁(yè)，共50頁(yè)。1810.由0,1,2,3組成(zǔchénɡ)的長(zhǎng)度為n的序列中，求含偶數(shù)個(gè)0的序列個(gè)數(shù)和含奇數(shù)個(gè)0的序列個(gè)數(shù).解設(shè)an為含偶數(shù)個(gè)0的序列(xùliè)個(gè)數(shù)，bn為含奇數(shù)個(gè)0的序列(xùliè)個(gè)數(shù).那么有解得第十九頁(yè)，共50頁(yè)。1911.十個(gè)數(shù)字(0到9)和四個(gè)運(yùn)算符(+，-，*，/)組成14個(gè)元素，求由其中的n個(gè)元素的排列(páiliè)構(gòu)成一形式算術(shù)表達(dá)式的個(gè)數(shù).解令an表示(biǎoshì)n個(gè)元素排列成算術(shù)表達(dá)式的數(shù)目，那么解得第二十頁(yè)，共50頁(yè)。2012.在一圓周上均勻地取2n個(gè)點(diǎn)，用n條兩兩不相交的弦把這些點(diǎn)配成對(duì)，求所有(suǒyǒu)這種配對(duì)的方式數(shù).解設(shè)所求配對(duì)(pèiduì)的方式數(shù)為hn,那么h1=1,那么h0=1,設(shè)2n個(gè)點(diǎn)依次(yīcì)為連接配對(duì)方式數(shù)為hk-1,那么將圓周一分為二,一邊有2(k-1)個(gè)點(diǎn),另一邊有2(n-k)個(gè)點(diǎn)，配對(duì)方式數(shù)為hn-k.第二十一頁(yè)，共50頁(yè)。21于是(yúshì)解得第二十二頁(yè)，共50頁(yè)。2213.一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)編碼字，如果它包含偶數(shù)個(gè)0，就是(jiùshì)有效的.求有效的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è)，共50頁(yè)。23個(gè).于是(yúshì)得遞推關(guān)系即解得通解(tōngjiě)代入初始條件得故所求有效數(shù)字(yǒuxiàoshùzì)有個(gè).第二十四頁(yè)，共50頁(yè)。2414.把件彼此相異的物品分給甲、乙、丙三人，使得甲至少分得兩件物品，乙和丙至少分得一件物品，有多少種不同的分法？解設(shè)有N種不同的分法.因?yàn)榘裯件彼此相異的物品分給3個(gè)人(gèrén)，使得每人至少分得一件物品的方法共有種，其中使得(shǐde)甲恰分得一件物品的分法有第二十五頁(yè)，共50頁(yè)。25種，故第二十六頁(yè)，共50頁(yè)。15.令m和n是非負(fù)整數(shù)且,有m+n個(gè)人站成一排進(jìn)入劇院，入場(chǎng)費(fèi)為每人50元.這

m+n個(gè)人中有n個(gè)人有50元面額的鈔票，而另外m個(gè)人只有100元面額的鈔票.售票處開(kāi)門(mén)時(shí)使用一個(gè)空的現(xiàn)金收銀機(jī).求能夠使得需要的時(shí)候總有零錢(qián)可找的隊(duì)列方式數(shù).證將有50元的人用1標(biāo)識(shí)，有100元的人用-1標(biāo)識(shí)，那么該問(wèn)題(wèntí)為：包括m個(gè)-1和n個(gè)1的m+n個(gè)數(shù)構(gòu)成(gòuchéng)的序列，使第二十七頁(yè)，共50頁(yè)。27這m+n個(gè)數(shù)的排列是集合

的排列，排列(páiliè)數(shù)為設(shè)A是滿足以上要求的序列全體，稱為可接受排列(páiliè).設(shè)U為不可接受排列(páiliè)的全體，那么第二十八頁(yè)，共50頁(yè)。28由于U是不可接受(jiēshòu)排列的集合，對(duì)U中任一個(gè)排列，必有最小的k，使從而(cóngér)有即k-1是偶數(shù)，且

中有相等個(gè)數(shù)的1和-1.將中前k個(gè)變號(hào)后，可得一個(gè)(yīɡè)由n+1個(gè)1和m-1個(gè)-1的序列.第二十九頁(yè)，共50頁(yè)。29

反之n+1個(gè)1和m-1個(gè)-1的序列.由于,故必存在k，使

中1的個(gè)數(shù)恰比-1的個(gè)數(shù)多1.只要將這n+1個(gè)1和m-1個(gè)-1的序列前k項(xiàng)變號(hào)，就可得一個(gè)有n個(gè)1和m個(gè)-1的U中一個(gè)排列.所以U是集合

的排列全體，于是所以(suǒyǐ)第三十頁(yè)，共50頁(yè)。30組合(zǔhé)數(shù)學(xué)練習(xí)題(二)第三十一頁(yè)，共50頁(yè)。31第三十二頁(yè)，共50頁(yè)。32第三十三頁(yè)，共50頁(yè)。332.將4個(gè)黑球、3個(gè)白球、2個(gè)紅球排成一列，但不能讓任何(rènhé)一種同顏色的球全部排在一起，問(wèn)有多少種排法(假定同色球不加區(qū)別)？解設(shè)所求數(shù)為N，以S表示由4個(gè)黑球，3個(gè)白球，2個(gè)紅球作成的全排列之集，A，B，C分別(fēnbié)表示S中4個(gè)黑球，3個(gè)白球，2個(gè)紅球排在一起的全排列之集.那么第三十四頁(yè)，共50頁(yè)。34所以(suǒyǐ)第三十五頁(yè)，共50頁(yè)。353.n個(gè)單位各派2名代表出席一個(gè)會(huì)議，2n名代表圍一圓桌坐下.試問(wèn)：(1)同一單位代表相鄰而坐的方案(fāngàn)有多少種？(3)同一單位的代表不相鄰的方案(fāngàn)有多少種?解(1)這是2n個(gè)元的圓排列,故各單位代表入座方式有(2)將同一單位代表看作一個(gè)(yīɡè)整體參與排列，有而同一(tóngyī)單位的兩位代表坐法有2種(左或右),故同一單位代表相鄰而坐的方案有第三十六頁(yè)，共50頁(yè)。36(3)設(shè)這2n個(gè)人(gèrén)入座方式的全體為S，那么{S中第i個(gè)單位的兩個(gè)人相鄰的入座方式}那么(nàme)第三十七頁(yè)，共50頁(yè)。37由容斥原理(yuánlǐ)，所求方案數(shù)為同類問(wèn)題：n對(duì)夫妻圍圓桌而坐，求夫妻不相鄰(xiānɡlín)的入坐方案數(shù).第三十八頁(yè)，共50頁(yè)。384.用10個(gè)球壘成一個(gè)三角陣，使得1個(gè)球在2個(gè)球之上，2個(gè)球在3個(gè)球之上，3個(gè)球在4個(gè)球之上.這個(gè)(zhège)三角陣可自由旋轉(zhuǎn).用紅色與藍(lán)色對(duì)該陣各球著色，求不等價(jià)著色數(shù).如果再允許翻轉(zhuǎn)該陣，不等價(jià)著色數(shù)又有多少種？

解

將三角陣上的球標(biāo)以1～10表示，它分別繞其中心逆時(shí)針旋轉(zhuǎn)得置換群第三十九頁(yè)，共50頁(yè)。39其中(qízhōng)(恒等置換(zhìhuàn))，(逆時(shí)轉(zhuǎn))(逆時(shí)轉(zhuǎn))由定理知，所求方案數(shù)為第四十頁(yè)，共50頁(yè)。40如果球陣可以(kěyǐ)翻轉(zhuǎn)，那么置換群為其中同前，由定理知，所求方案數(shù)為第四十一頁(yè)，共50頁(yè)。415.將一個(gè)3行3列棋盤(pán)(qípán)的9個(gè)正方形著紅色和藍(lán)色，棋盤(pán)(qípán)可以繞對(duì)稱中心旋轉(zhuǎn)，但不能繞對(duì)稱軸翻轉(zhuǎn)，求不等價(jià)的著色方案數(shù).從而(cóngér)得置換群Q所含的置換為解棋盤(pán)可以分別繞對(duì)稱中心逆時(shí)針旋轉(zhuǎn)第四十二頁(yè)，共50頁(yè)。42故由定理知不等價(jià)的著色方案數(shù)為第四十三頁(yè)，共50頁(yè)。436.把1到10這10個(gè)數(shù)隨機(jī)(suíjī)地寫(xiě)成一個(gè)圓圈.證明：必存在某3個(gè)相鄰數(shù)之和大于或等于17.第四十四頁(yè)，共50頁(yè)。44這說(shuō)明圓圈(yuánquān)的10個(gè)數(shù)中,必存在三個(gè)連續(xù)的數(shù),其和大于或等于17.第四十五頁(yè)，共50頁(yè)。457.證明(zhèngmíng)：如果從S={1,3,5,7,