《組合數(shù)學(xué)》姜建國(guó)著(第二版)_課后習(xí)題答案完全版

《《組合數(shù)學(xué)》姜建國(guó)著(第二版)_課后習(xí)題答案完全版》由會(huì)員分享，可在線閱讀，更多相關(guān)《《組合數(shù)學(xué)》姜建國(guó)著(第二版)_課后習(xí)題答案完全版（77頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、.組合數(shù)學(xué)-姜建國(guó),岳建國(guó)習(xí)題一排列與組合1在1到9999之間,有多少個(gè)每位上數(shù)字全不相同而且由奇數(shù)構(gòu)成的整數(shù)？解：該題相當(dāng)于從1,3,5,7,9”五個(gè)數(shù)字中分別選出1,2,3,4作排列的方案數(shù)； 1選1個(gè),即構(gòu)成1位數(shù),共有個(gè)； 2選2個(gè),即構(gòu)成兩位數(shù),共有個(gè)； 3選3個(gè),即構(gòu)成3位數(shù),共有個(gè)； 4選4個(gè),即構(gòu)成4位數(shù),共有個(gè)； 由加法法則可知,所求的整數(shù)共有：個(gè)。2比5400小并具有下列性質(zhì)的正整數(shù)有多少個(gè)？1每位的數(shù)字全不同；2每位數(shù)字不同且不出現(xiàn)數(shù)字2與7；解：1比5400小且每位數(shù)字全不同的正整數(shù)； 按正整數(shù)的位數(shù)可分為以下幾種情況： 一位數(shù),可從19中任取一個(gè),共有9個(gè)； 兩位數(shù)。

2、十位上的數(shù)可從19中選取,個(gè)位數(shù)上的數(shù)可從其余9個(gè)數(shù)字中選取,根據(jù)乘法法則,共有個(gè)； 三位數(shù)。百位上的數(shù)可從19中選取,剩下的兩位數(shù)可從其余9個(gè)數(shù)中選2個(gè)進(jìn)行排列,根據(jù)乘法法則,共有個(gè)； 四位數(shù)。又可分三種情況：n 千位上的數(shù)從14中選取,剩下的三位數(shù)從剩下的9個(gè)數(shù)字中選3個(gè)進(jìn)行排列,根據(jù)乘法法則,共有個(gè)；n 千位上的數(shù)取5,百位上的數(shù)從13中選取,剩下的兩位數(shù)從剩下的8個(gè)數(shù)字中選2個(gè)進(jìn)行排列,共有個(gè)；n 千位上的數(shù)取5,百位上的數(shù)取0,剩下的兩位數(shù)從剩下的8個(gè)數(shù)字中選2個(gè)進(jìn)行排列,共有個(gè)； 根據(jù)加法法則,滿足條件的正整數(shù)共有：個(gè)；2比5400小且每位數(shù)字不同且不出現(xiàn)數(shù)字2與7的正整數(shù)；按正整

3、數(shù)的位數(shù)可分為以下幾種情況：設(shè) 一位數(shù),可從中任取一個(gè),共有7個(gè)； 兩位數(shù)。十位上的數(shù)可從中選取,個(gè)位數(shù)上的數(shù)可從A中其余7個(gè)數(shù)字中選取,根據(jù)乘法法則,共有個(gè)； 三位數(shù)。百位上的數(shù)可從中選取,剩下的兩位數(shù)可從A其余7個(gè)數(shù)中選2個(gè)進(jìn)行排列,根據(jù)乘法法則,共有個(gè)； 四位數(shù)。又可分三種情況：n 千位上的數(shù)從1,3,4中選取,剩下的三位數(shù)從A中剩下的7個(gè)數(shù)字中選3個(gè)進(jìn)行排列,根據(jù)乘法法則,共有個(gè)；n 千位上的數(shù)取5,百位上的數(shù)從0,1,3中選取,剩下的兩位數(shù)從A中剩下的6個(gè)數(shù)字中選2個(gè)進(jìn)行排列,共有個(gè)； 根據(jù)加法法則,滿足條件的正整數(shù)共有：個(gè)；3一教室有兩排,每排8個(gè)座位,今有14名學(xué)生,問(wèn)按下列不同

4、的方式入座,各有多少種做法？ 1規(guī)定某5人總坐在前排,某4人總坐在后排,但每人具體座位不指定； 2要求前排至少坐5人,后排至少坐4人。解：1因?yàn)榫妥怯写涡虻?所有是排列問(wèn)題。5人坐前排,其坐法數(shù)為,4人坐后排,其坐法數(shù)為, 剩下的5個(gè)人在其余座位的就坐方式有種, 根據(jù)乘法原理,就座方式總共有：種 2因前排至少需坐6人,最多坐8人,后排也是如此。可分成三種情況分別討論： 前排恰好坐6人,入座方式有； 前排恰好坐7人,入座方式有； 前排恰好坐8人,入座方式有；各類入座方式互相不同,由加法法則,總的入座方式總數(shù)為： 典型錯(cuò)誤：先選6人坐前排,再選4人坐后排,剩下的4人坐入余下的6個(gè)座位。故總的入坐

5、方式共有：種。但這樣計(jì)算無(wú)疑是有重復(fù)的,例如恰好選6人坐前排,其余8人全坐后排,那么上式中的就有重復(fù)。4一位學(xué)者要在一周內(nèi)安排50個(gè)小時(shí)的工作時(shí)間,而且每天至少工作5小時(shí),問(wèn)共有多少種安排方案？解：用表示第i天的工作時(shí)間,則問(wèn)題轉(zhuǎn)化為求不定方程的整數(shù)解的組數(shù),且,于是又可以轉(zhuǎn)化為求不定方程的整數(shù)解的組數(shù)。該問(wèn)題等價(jià)于：將15個(gè)沒(méi)有區(qū)別的球,放入7個(gè)不同的盒子中,每盒球數(shù)不限,即相異元素允許重復(fù)的組合問(wèn)題。故安排方案共有： 種 另解：因?yàn)樵试S,所以問(wèn)題轉(zhuǎn)化為長(zhǎng)度為1的15條線段中間有14個(gè)空,再加上前后兩個(gè)空,共16個(gè)空,在這16個(gè)空中放入6個(gè)號(hào),每個(gè)空放置的號(hào)數(shù)不限,未放號(hào)的線段合成一條線段,

6、求放法的總數(shù)。從而不定方程的整數(shù)解共有：組 即共有54 264種安排方案。5若某兩人拒絕相鄰而坐,問(wèn)12個(gè)人圍圓周就坐有多少種方式？解：12個(gè)人圍圓周就坐的方式有：種,設(shè)不愿坐在一起的兩人為甲和乙,將這兩個(gè)人相鄰而坐,可看為1人,則這樣的就坐方式有：種；由于甲乙相鄰而坐,可能是甲乙也可能是乙甲；所以則滿足條件的就坐方式有：種。6有15名選手,其中5名只能打后衛(wèi),8名只能打前鋒,2名只能打前鋒或后衛(wèi),今欲選出11人組成一支球隊(duì),而且需要7人打前鋒,4人打后衛(wèi),試問(wèn)有多少種選法？解：用A、B、C分別代表5名打后衛(wèi)、8名打前鋒、2名可打前鋒或后衛(wèi)的集合,則可分為以下幾種情況： 17個(gè)前鋒從B中選取,

7、有種選法,4個(gè)后衛(wèi)從A中選取,有種, 根據(jù)乘法法則,這種選取方案有：種； 27個(gè)前鋒從B中選取,從A中選取3名后衛(wèi),從C中選1名后衛(wèi), 根據(jù)乘法法則,這種選取方案有：種； 37個(gè)前鋒從B中選取,從A中選取2名后衛(wèi),C中2名當(dāng)后衛(wèi), 根據(jù)乘法法則,這種選取方案有：種； 4從B中選6個(gè)前鋒,從C中選1個(gè)前鋒,從A中選4個(gè)后衛(wèi), 根據(jù)乘法法則,這種選取方案有：種； 5從B中選6個(gè)前鋒,從C中選1個(gè)前鋒,從A中選3個(gè)后衛(wèi),C中剩下的一個(gè)當(dāng)后衛(wèi),選取方案有：種； 6從B中選5個(gè)前鋒,C中2個(gè)當(dāng)前鋒,從A中選4個(gè)后衛(wèi), 選取方案有：種； 根據(jù)加法法則,總的方案數(shù)為：7求展開(kāi)式中項(xiàng)的系數(shù)。解：令,則中項(xiàng)的系

8、數(shù)為,即中,的系數(shù),因此,的系數(shù)為：。8求的展開(kāi)式。解：,展開(kāi)式共有項(xiàng), 所以,9求展開(kāi)式中的系數(shù)。解：的系數(shù)為： 10試證任一整數(shù)n可唯一表示成如下形式：證明：1可表示性。令,顯然,顯然,定義函數(shù),顯然,即,由于f是用普通乘法和普通加法所定義的,故f無(wú)歧義,肯定是一個(gè)函數(shù)。從而必有一確定的數(shù),使得,為了證明N中的任一數(shù)n均可表示成的形式,只需證明f是滿射函數(shù)即可。又因?yàn)閒是定義在兩個(gè)有限且基數(shù)相等的函數(shù)上,因此如果能證明f單射,則f必是滿射。假設(shè)f不是單射,則存在,且有,使得由于,故必存在,使得。不妨設(shè)這個(gè)j是第一個(gè)使之不相等的,即,且,因?yàn)樗? 產(chǎn)生矛盾,所以f必是單射函數(shù)。因?yàn)?所以f

9、必然也是滿射函數(shù),故對(duì)任意的,都存在,使得 這說(shuō)明對(duì)任意的整數(shù),都可以表示成的形式。 2唯一性。 由于函數(shù)是一個(gè)單射,也是滿射,即f是雙射函數(shù),故,對(duì)任意的,都存在唯一的,使得。否則,若存在另一個(gè),使得將與f是單射函數(shù)矛盾。證畢。11證明,并給出組合意義。證明：因?yàn)?現(xiàn)令,則可得,即組合意義：將n個(gè)元素分為3堆,1堆1個(gè)元素,1堆r個(gè)元素,1堆個(gè)元素?？梢杂邢旅鎯煞N不同的分法： 1先從n個(gè)元素中選出個(gè)元素,剩下的個(gè)作為1堆；再將選出的個(gè)元素分為兩堆,1堆1個(gè),1堆r個(gè)。 2先從n個(gè)元素中選出1人作為1堆,再?gòu)氖Ｏ碌膫€(gè)中選出r個(gè)作為1堆,剩下的作為1堆。 顯然,兩種分法是等價(jià)的,所以等式成立。1

10、2證明 。證明：采用殊途同歸法。 組合意義一：考慮從n個(gè)人中選出1名正式代表和若干名列席代表的選法列席代表人數(shù)不限,可以為0。可以有以下兩種不同的選法：1先選定正式代表,有種選法；然后從人中選列席代表,這 個(gè)人都有選和不選的兩種狀態(tài),共有種選法；根據(jù)乘法法則,共有 種選法；2可以先選出人,然后再?gòu)闹羞x出1名正式代表,其余k人作為列席代表,對(duì)于每個(gè)k,這樣的選法有：,從而總選法有： 顯然,兩種選法是等價(jià)的,所以等式成立。 組合意義二：將n個(gè)不同的球放入標(biāo)號(hào)為A、B、C的3個(gè)盒子,其中要求A盒只放1個(gè)球,其余兩盒的球數(shù)不限。那么,有兩種不同的放法：1先從n個(gè)不同的球中選出1個(gè),放入A盒,再將其余個(gè)

11、球放入另外兩盒,有種放法；2先從n個(gè)球中選出k個(gè),再?gòu)乃x的k個(gè)球中選出1個(gè)放入A盒,將其余的個(gè)球放入B盒,剩下的個(gè)球放入C盒,根據(jù)乘法法則,對(duì)于不同的k,有種放法。當(dāng)時(shí),各種情況互不重復(fù),且包含了所有放法,根據(jù)加法法則,總的放法有：。 顯然兩種放法是等價(jià)的,故等式成立。 另法：根據(jù)二項(xiàng)式定理：,兩邊求導(dǎo),得：,令,即得13有n個(gè)不同的整數(shù),從中取出兩組來(lái),要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù),問(wèn)有多少種方案？解：設(shè)這n個(gè)不同的數(shù)為,若假定第一組取個(gè)數(shù),第二組取個(gè)數(shù),并且令,則要求第一組數(shù)里的最小數(shù)大于第二組里的最大數(shù),我們可以這樣來(lái)選：先從n個(gè)數(shù)中任選m個(gè)數(shù)出來(lái),有種選法；再?gòu)倪@m個(gè)數(shù)中

12、從大到小取個(gè)數(shù)作為第一組數(shù),有種取法；再將其余的個(gè)數(shù)作為第二組數(shù)。故總方案數(shù)有：14六個(gè)引擎分列兩排,要求引擎的點(diǎn)火次序兩排交錯(cuò)開(kāi)來(lái),試求從某一特定引擎開(kāi)始點(diǎn)火有多少種方案？解：第一次點(diǎn)火僅有一種選擇,即點(diǎn)某個(gè)特定引擎的火；第二次點(diǎn)另一組某個(gè)引擎的火,有三種選擇；第三次有2種,。所以方案數(shù)為：種 如果只指定從第一排先開(kāi)始點(diǎn)火,不指定某一個(gè),則方案數(shù)為種 如果第一個(gè)引擎任意選,只要求點(diǎn)火過(guò)程是交錯(cuò)的,則方案數(shù)為種15試求從1到1 000 000的整數(shù)中,0出現(xiàn)了幾次？解：分別計(jì)算0出現(xiàn)在各個(gè)位上的次數(shù)。 10出現(xiàn)在個(gè)位,此時(shí)符合條件的2位數(shù)有9個(gè)；3位數(shù)有個(gè)；4位數(shù)有個(gè)；5位數(shù)有個(gè)；6位數(shù)有個(gè)；

13、 20出現(xiàn)在十位,此時(shí)符合條件的3位數(shù)有個(gè)；4位數(shù)有個(gè)；5位數(shù)有個(gè)；6位數(shù)有個(gè)； 30出現(xiàn)在百位,此時(shí)符合條件的4位數(shù)有個(gè)；5位數(shù)有個(gè)；6位數(shù)有個(gè)； 40出現(xiàn)在千位,此時(shí)符合條件的5位數(shù)有個(gè)；6位數(shù)有個(gè)； 50出現(xiàn)在萬(wàn)位,此時(shí)符合條件的6位數(shù)有個(gè)； 另外1 000 000中有6個(gè)0。 所以,從1到1 000 000的整數(shù)中,0出現(xiàn)的次數(shù)總共有：次 另法：先不考慮1 000 000本身,那么任一個(gè)000 000999 999之間的數(shù)都可以表示成如下形式：,其中每個(gè)是0到9的數(shù)字。因?yàn)槊课粩?shù)字可以有10種選擇,根據(jù)乘法法則,共有個(gè)6位數(shù),又每個(gè)6位數(shù)由6個(gè)數(shù)字組成包括無(wú)效0,所以共有個(gè)數(shù)字,又每個(gè)

14、數(shù)字出現(xiàn)的概率相等,所以0出現(xiàn)的次數(shù)應(yīng)是,但習(xí)慣上在計(jì)算0的個(gè)數(shù)時(shí),不包括無(wú)效0即高位的0,因而要從中去掉無(wú)效0,其中：11位數(shù)有9個(gè)不包括0,其無(wú)效0共有個(gè)即00000；22位數(shù)有90個(gè),其無(wú)效0共個(gè)。依次類推,無(wú)效0的總數(shù)為 因?yàn)槿珵?時(shí)的6個(gè)0和1 000 000本身的6個(gè)0相互抵消,所以1到1 000 000之間的自然數(shù)中0出現(xiàn)的次數(shù)為次 注意：1出現(xiàn)的次數(shù)為要考慮1 000 000這個(gè)數(shù)的首位1,2,3,9各自出現(xiàn)的次數(shù)為。16n個(gè)男n個(gè)女排成一男女相間的隊(duì)伍,試問(wèn)有多少種不同的方案？若圍成一圓桌坐下,又有多少種不同的方案？解：排成男女相間的隊(duì)伍：先將n個(gè)男的排成1行,共有種排法；再

15、將n個(gè)女的往n個(gè)空里插,有種排法；由于可以先男后女,也可以先女后男,因此共有種排法；根據(jù)乘法法則,男女相間的隊(duì)伍共有：種方案。若圍成一圓周坐下,同理先將n個(gè)男的圍成一圓周,共有種排法,再將n個(gè)女的往n個(gè)空中插,有種排法,根據(jù)乘法法則,圍成圓周坐下,總的方案數(shù)有：種。17n個(gè)完全一樣的球,放到r個(gè)有標(biāo)志的盒子,要求無(wú)一空盒,試證其方案數(shù)為。證明：因?yàn)闆](méi)有空盒,可先每盒放入一個(gè)球,再將剩余的球放入r個(gè)盒子中, 即將個(gè)無(wú)區(qū)別的球,放入r個(gè)不同的盒子中,每盒的球數(shù)不受限制, 因此方案數(shù)有：。 另法：插空法。問(wèn)題可看為：n個(gè)球排成1行,球與球之間形成個(gè)空,再在這個(gè)空中,插入個(gè)隔板,這樣就可形成r個(gè)盒子,

16、每盒球不空的方案,其方案數(shù)為。18設(shè),是k個(gè)素?cái)?shù),試求能整除盡數(shù)n的正整數(shù)數(shù)目。解：能整除數(shù)n的正整數(shù)即n的正約數(shù),其個(gè)數(shù)為：。19試求n個(gè)完全一樣的骰子能擲出多少種不同的方案？解：每個(gè)骰子有六個(gè)面,每個(gè)面的點(diǎn)數(shù)可以是中的一種。由于n個(gè)骰子完全一樣,故這樣相當(dāng)于將n個(gè)完全一樣的球放到6個(gè)不同的盒子中,每盒球數(shù)不限。故方案數(shù)有種20凸十邊形的任意三個(gè)對(duì)角線不共點(diǎn),試求這凸十邊形的對(duì)角線交于多少個(gè)點(diǎn)？又把所有的對(duì)角線分割成多少段？解：1從一個(gè)頂點(diǎn)可引出7條對(duì)角線,這7條對(duì)角線和其他頂點(diǎn)引出的對(duì)角線的交點(diǎn)情況如下：從右到左,和第一條對(duì)角線的交點(diǎn)有：個(gè),和第二條的交點(diǎn)有,和第三條的交點(diǎn)有條,故和一個(gè)頂

17、點(diǎn)引出的7條線相交的點(diǎn)為：,故和從10點(diǎn)引出的對(duì)角線交的點(diǎn)有個(gè),但每個(gè)點(diǎn)重復(fù)了四次因?yàn)槊總€(gè)點(diǎn)在兩條線上,而每條線又有兩個(gè)端點(diǎn),故凸十邊形對(duì)角線交于個(gè)點(diǎn)。 也可以直接這樣看：因?yàn)橐粋€(gè)交點(diǎn)需要兩條對(duì)角線相交,而兩條對(duì)角線又需要多邊形的四個(gè)點(diǎn)構(gòu)成一四邊形。反之,從n個(gè)頂點(diǎn)中任取四個(gè)頂點(diǎn),連成一四邊形,而四邊形的兩條對(duì)角線必須確定唯一的一個(gè)交點(diǎn),故凸十邊形的對(duì)角線的交點(diǎn)共有：個(gè)前提：任三個(gè)對(duì)角線不共點(diǎn),否則,一個(gè)交點(diǎn)不能對(duì)應(yīng)n邊形的唯一四個(gè)頂點(diǎn)2由1知,一個(gè)點(diǎn)引出的7條對(duì)角線中,第一條線上有7個(gè)點(diǎn),故將該線段分成8段；第二條線上有12個(gè)點(diǎn),故將該線段分成13段,故從一個(gè)點(diǎn)出發(fā)的7條線上的段數(shù)為：?，F(xiàn)有

18、10個(gè)點(diǎn)。故總的段數(shù)為：。但每段重復(fù)計(jì)算了2次因?yàn)槊織l線有2個(gè)端點(diǎn)故總的段數(shù)應(yīng)為：。 另法：一個(gè)交點(diǎn)給相交的兩條對(duì)角線各增加1段,所以對(duì)角線總的段數(shù)為： 對(duì)角線數(shù)2倍交點(diǎn)數(shù) 段21試證一整數(shù)n是另一整數(shù)的平方的充要條件是除盡n的正整數(shù)的數(shù)目為奇數(shù)。證明：必要性：整數(shù)n可表示為,且為素?cái)?shù),則除盡n的正整數(shù)個(gè)數(shù)為：,若為偶數(shù),則必存在為奇數(shù),則n不可能寫(xiě)成令一個(gè)數(shù)的平方。所以n是另一整數(shù)的平方的必要條件是除盡n的正整數(shù)數(shù)目為奇數(shù)。充分性：若除盡n的正整數(shù)的數(shù)目為奇數(shù),則均為偶數(shù),則 可寫(xiě)成另一整數(shù)的平方。證畢。22統(tǒng)計(jì)力學(xué)需要計(jì)算r個(gè)質(zhì)點(diǎn)放到n個(gè)盒子里去,并分別服從下列假定之一,問(wèn)有多少種不同的圖

19、像？假設(shè)盒子始終是不同的。 1Maxwell-Boltzmann假定：r個(gè)質(zhì)點(diǎn)是不同的,任何盒子可以放任意個(gè)； 2Bose-Einstein假定：r個(gè)質(zhì)點(diǎn)完全相同,每一個(gè)盒子可以放任意個(gè)。 3Fermi-Dirac假定：r個(gè)質(zhì)點(diǎn)都完全相同,每盒不得超過(guò)一個(gè)。解：1問(wèn)題即：將r個(gè)不同的質(zhì)點(diǎn)放到n個(gè)不同的盒子,每個(gè)盒子放的質(zhì)點(diǎn)數(shù)不受限制,即相異元素允許重復(fù)排列,其方案數(shù)有： 2問(wèn)題即：將r個(gè)沒(méi)有區(qū)別的質(zhì)點(diǎn)放到n個(gè)不同的盒子,每個(gè)盒子方的質(zhì)點(diǎn)數(shù)不受限制,即相異元素允許重復(fù)組合,其方案數(shù)有： 3問(wèn)題即：將r個(gè)沒(méi)有區(qū)別的質(zhì)點(diǎn)放到n個(gè)不同的盒子,每盒不超過(guò)一個(gè),即相異元素不允許重復(fù)的組合,其方案數(shù)有：23

20、從26個(gè)英文字母中取出6個(gè)字母組成一字,若其中有2或3個(gè)母音,問(wèn)分別可構(gòu)成多少個(gè)字不允許重復(fù)？解：母音指元音,即a,e,i,o,u 1有2個(gè)元音。先從5個(gè)元音中取出2個(gè),再?gòu)氖Ｏ碌?1個(gè)字母中選出4個(gè),再將6個(gè)字母進(jìn)行全排列,則可構(gòu)成的字總共有：個(gè) 2有3個(gè)元音。先從5個(gè)元音中取出3個(gè),再?gòu)氖Ｏ碌?1個(gè)字母中選出4個(gè),再將6個(gè)字母進(jìn)行全排列,則可構(gòu)成的字總共有：個(gè)24給出的組合意義。證明： 組合意義一：從個(gè)元素中取出個(gè)元素的組合數(shù)為：,且,其中第位置上的元素可取,當(dāng)取時(shí),前邊的r個(gè)數(shù)可在這個(gè)數(shù)中取,故有種取法；后邊的個(gè)數(shù)可在這個(gè)數(shù)中取,故有種取法。根據(jù)乘法法則,當(dāng)時(shí),這樣的組合數(shù)為： 再根據(jù)加

21、法法則,對(duì)進(jìn)行求和,就有。 組合意義二：格路方法等式左端：從點(diǎn)到點(diǎn),直接經(jīng)過(guò)點(diǎn)再到點(diǎn)的路徑數(shù)。從A到C的路徑數(shù)為：,從D到B的路徑數(shù)為：,根據(jù)乘法法則和加法法則,從A到B的路徑數(shù)有：。等式右端：從點(diǎn)到點(diǎn)的路徑數(shù)為：25給出的組合意義。證明：1等式右端：從個(gè)元素中,任選個(gè)元素的組合方案數(shù)為：。 2等式左端：從不同元素中選取個(gè)元素,一定選元素,但不選元素的方案數(shù)。根據(jù)乘法法則,當(dāng)k值取定時(shí),這樣的方案數(shù)為從其余的個(gè)元素中任取r個(gè)的方案數(shù),即,再根據(jù)加法法則,總的方案數(shù)有：26證明 。證明：考慮從m雙互不相同的鞋中取出n只,要求其中沒(méi)有任何兩只是成對(duì)的,求方案數(shù)。 一方面,先從m雙鞋中選取n雙,共有

22、種選法,再?gòu)拇薾雙中每雙抽掉一只,有種取法,由乘法原理,總的方案數(shù)為：。 另一方面,先取出只左腳的鞋,再在其余的雙中取出只右腳的鞋,則總的方案數(shù)為： 所以,。 另法：根據(jù) 從而有： 27對(duì)于給定的正整數(shù)n,證明在所有中,當(dāng) 時(shí),取得最大值。證明：取與進(jìn)行比較。, 當(dāng)時(shí),即, 當(dāng)時(shí),即, 因此,只有當(dāng)或最接近時(shí),取得最大值。281用組合方法證明 和 都是整數(shù)。 2證明是整數(shù)。證明：1考慮個(gè)有區(qū)別的球放入n個(gè)不同的盒子里,每盒兩個(gè),盒中球不計(jì)順序,則方案數(shù)為：,方案數(shù)是整數(shù),所以是整數(shù)。同理,考慮個(gè)有區(qū)別的球放入n個(gè)不同的盒子里,每盒3個(gè),盒中球不計(jì)順,則方案數(shù)為：,方案數(shù)是整數(shù),所以是整數(shù)。 2

23、考慮個(gè)不同的球放入n個(gè)相同的盒子,每盒n個(gè),盒中球不計(jì)順序的方案。 先假設(shè)盒子是不同的,則這樣的方案數(shù)為：, 又盒子是相同的,所以方案數(shù)應(yīng)為：, 方案數(shù)必然是整數(shù),所以是整數(shù)。291在2n個(gè)球中,有n個(gè)相同,求從這2n個(gè)球中選取n個(gè)的方案數(shù)。 2在個(gè)球中,有n個(gè)相同,求從這個(gè)球中選取n個(gè)的方案數(shù)。解：1問(wèn)題即：從集合中,選取n個(gè)的方案數(shù), 即多項(xiàng)式中的系數(shù),即 從這2n個(gè)球中選取n個(gè)的方案數(shù)為種。 2問(wèn)題即：從集合中,選取n個(gè)的方案數(shù), 即多項(xiàng)式中的系數(shù),即30證明在由字母表生成的長(zhǎng)度為n的字符串中, 10出現(xiàn)偶數(shù)次的字符串有個(gè)； 2,其中 。證明：1采用數(shù)學(xué)歸納法當(dāng)時(shí),0出現(xiàn)偶數(shù)次0次,長(zhǎng)度

24、為1的字符串為1”和2”兩個(gè)字符串,而,故結(jié)論成立。假設(shè)當(dāng)時(shí),結(jié)論成立,即0出現(xiàn)偶數(shù)次,長(zhǎng)度為k的字符串有個(gè),當(dāng)時(shí),0出現(xiàn)偶數(shù)次,長(zhǎng)度為的字符串包括兩部分： 在0出現(xiàn)偶數(shù)次,長(zhǎng)度為k的字符串后面再增加一位不是0的數(shù)只能是1或2,因此,這樣的字符串有個(gè)。 給0出現(xiàn)奇數(shù)次,長(zhǎng)度為k的字符串后面再增加一個(gè)0, 因此,這樣的字符串有：。根據(jù)加法法則,0出現(xiàn)偶數(shù)次,長(zhǎng)度為的字符串共有：,即時(shí),結(jié)論也成立。 所以,根據(jù)數(shù)學(xué)歸納法,結(jié)論成立。2由1知,右端表示0出現(xiàn)偶數(shù)次的字符串?dāng)?shù)。 而左端代表的組合問(wèn)題是：長(zhǎng)度為n的字符串中,有0個(gè)0的字符串?dāng)?shù)有：, 有2個(gè)0的字符串?dāng)?shù)有：,有q個(gè)0的字符串?dāng)?shù)有：,根據(jù)加

25、法法則,可知,左端代表的是長(zhǎng)度為n的字符串中0出現(xiàn)偶數(shù)次的字符串?dāng)?shù),因此315臺(tái)教學(xué)儀器供m個(gè)學(xué)生使用,要求使用第1臺(tái)和第2臺(tái)的人數(shù)相等,有多少種分配方案？解： 方法一：先從m個(gè)學(xué)生中選取k個(gè)使用第1臺(tái)機(jī)器,再?gòu)氖Ｏ碌膫€(gè)學(xué)生中選取k個(gè)使用第2臺(tái)機(jī)器,其余個(gè)學(xué)生可以任意使用剩下的3臺(tái)機(jī)器,按乘法原理,其組合數(shù)為,這里,于是,按加法原理,共有種使用方案。 方法二：先從m個(gè)學(xué)生種選出2k個(gè),再將選出2k個(gè)學(xué)生平均分到1、2臺(tái)機(jī)器上,其余的個(gè)學(xué)生可以任意使用剩下的3臺(tái)機(jī)器,按乘法法則,其組合數(shù)為,這里于是,按加法原理,共有種使用方案。32由n個(gè)0及n個(gè)1組成的字符串,其任意前k個(gè)字符中,0的個(gè)數(shù)不少于

26、1的個(gè)數(shù)的字符串有多少？解：參見(jiàn)P21,例轉(zhuǎn)化為格路問(wèn)題。即從點(diǎn)到,只能從對(duì)角線上方走,但可以碰到對(duì)角線的所有最短路徑數(shù)。顯然,第一步必然要走到點(diǎn),因此可以轉(zhuǎn)換為從點(diǎn)到的所有滿足條件的路徑數(shù),進(jìn)一步,可以轉(zhuǎn)換為從點(diǎn)到,只能從對(duì)角線上方走,但不可以碰到對(duì)角線的所有路徑數(shù),因?yàn)閺狞c(diǎn)到的所有經(jīng)過(guò)對(duì)角線的路徑數(shù)與從點(diǎn)到點(diǎn)的所有路徑數(shù)是一一對(duì)應(yīng)的,因此,所求的字符串有：個(gè) 方法二：由n個(gè)1和n個(gè)0組成的2n位二進(jìn)制數(shù)共有個(gè),設(shè)所求的二進(jìn)制數(shù)共有個(gè),不符合要求的數(shù)有個(gè)。而不合要求的數(shù)的特征是從左向右掃描時(shí),必然在某一位首次出現(xiàn)0的個(gè)數(shù)小于1的個(gè)數(shù),即從左向右累計(jì)到第2k1位時(shí)出現(xiàn)k個(gè)0和個(gè)1。此時(shí),后位上

27、有個(gè)1,個(gè)0。將后部分的0改寫(xiě)為1,1改寫(xiě)為0。結(jié)果整個(gè)數(shù)變成由個(gè)和個(gè)0組成的2n位數(shù)z。即一個(gè)不合要求的數(shù)唯一對(duì)應(yīng)于這樣的一個(gè)數(shù)z。反之,給定一個(gè)由個(gè)1和個(gè)0組成的2n位數(shù)z由于1比0多2個(gè),故一定在某一位首次出現(xiàn)0的累計(jì)數(shù)少于1的累計(jì)數(shù)。依同法將此位后的0與1互換,使z變成由n個(gè)1和n個(gè)0組成的2n位數(shù)。所以,這兩種二進(jìn)制數(shù)一一對(duì)應(yīng)。即故。習(xí)題二母函數(shù)及其應(yīng)用1求下列數(shù)列的母函數(shù) 1； 2； 3；4；解：1母函數(shù)為：；2母函數(shù)為：； 方法二： 3母函數(shù)為：； 方法二： 4母函數(shù)為：。 方法二：2證明序列的母函數(shù)為 。證明：因?yàn)?令,則 ,而 故 又 所以 方法二：已知的k-組合數(shù)為,其母函

28、數(shù)為：序列的母函數(shù)為3設(shè),求序列的母函數(shù)。其中,是S的滿足下列條件的n組合數(shù)。1S的每個(gè)元素都出現(xiàn)奇數(shù)次；2S的每個(gè)元素都出現(xiàn)3的倍數(shù)次；3不出現(xiàn),至多出現(xiàn)一次；4只出現(xiàn)1、3或11次,只出現(xiàn)2、4或5次；5S的每個(gè)元素至少出現(xiàn)10次。解：1 2 3 4 54投擲兩個(gè)骰子,點(diǎn)數(shù)之和為r,其組合數(shù)是多少？解：用表示骰子的點(diǎn)數(shù)為i, 1若兩個(gè)骰子不同,則問(wèn)題等價(jià)于r的特殊有序2-分拆故相應(yīng)的母函數(shù)為則點(diǎn)數(shù)之和為r的方案總數(shù)就是的系數(shù)。2若兩個(gè)骰子相同,則問(wèn)題等價(jià)于r的特殊無(wú)序2-分拆而此問(wèn)題又可轉(zhuǎn)化為求r的最大分項(xiàng)等于2,且項(xiàng)數(shù)不超過(guò)6的分拆數(shù),即求方程的非負(fù)整數(shù)解的個(gè)數(shù)。相應(yīng)的母函數(shù)為其中點(diǎn)數(shù)之

29、和為r的方案數(shù)就是的系數(shù)。5投擲4個(gè)骰子,其點(diǎn)數(shù)之和為12的組合數(shù)是多少？解： 參考第4題。第二版第5題居民小區(qū)組織義務(wù)活動(dòng),號(hào)召每家出一到兩個(gè)人參加。設(shè)該小區(qū)共有n個(gè)家庭,現(xiàn)從中選出r人,問(wèn)：1設(shè)每個(gè)家庭都是3口之家,有多少種不同的選法？當(dāng)n=50時(shí),選法有多少種？2設(shè)n個(gè)家庭中兩家有4口人,其余家庭都是3口人,有多少種選法？解：1 2 第二版第6題把n個(gè)相同的小球放入編號(hào)為的m個(gè)盒子中,使得每個(gè)盒子內(nèi)的球數(shù)不小于它的編號(hào)數(shù)。已知,求不同的放球方法數(shù)。解：對(duì)應(yīng)母函數(shù)為：故6紅、黃、藍(lán)三色的球各8個(gè),從中取出9個(gè),要求每種顏色的球至少一個(gè),問(wèn)有多少種不同的取法？解：對(duì)應(yīng)的母函數(shù)為： 從中取9個(gè)

30、對(duì)應(yīng)的組合數(shù)為的系數(shù),即種 方法二：原問(wèn)題等價(jià)于從集合中取出9個(gè)元素,且每個(gè)元素至少取一個(gè)。現(xiàn)在先把元素a、b、c各取一個(gè),然后再隨意選出6個(gè),則問(wèn)題轉(zhuǎn)變?yōu)閺募现腥〕?個(gè)元素,且每個(gè)元素個(gè)數(shù)不限,求重復(fù)組合的方案數(shù)。又由于每個(gè)元素的個(gè)數(shù)大于6,故從中取6個(gè)元素與從集合中取出6個(gè)元素的組合數(shù)一樣多,因此不同的取法為種7將幣值為2角的人民幣,兌換成硬幣壹分、貳分和伍分可有多少種兌換方法？解：該題用1分、2分、5分的硬幣組成20分。是可重復(fù)的無(wú)序拆分： 其母函數(shù)為： 則不同的兌換方法為的系數(shù),即 即有29種兌換方法。8有1克重砝碼2枚,2克重砝碼3枚,5克重砝碼3枚,要求這8個(gè)砝碼只許放在天平的一

31、端,能稱幾種重量的物品？有多少種不同的稱法？解：該題屬于有限重復(fù)的無(wú)序拆分問(wèn)題。對(duì)應(yīng)的母函數(shù)為： 所以能稱123克等23種重量的物品。 總共的稱法為母函數(shù)的各項(xiàng)系數(shù)之和,再減去常數(shù)項(xiàng),即總共有種不同的稱法。其中,稱1、3、20、22、23克重量各有1種稱法； 稱2、4、5、8、9、10、13、14、15、18、19、21克重量各有2種稱法； 稱6、7、11、12、16、17克重量各有3種乘法；若要枚舉出各種方案,則可作母函數(shù)：項(xiàng)即為稱克重量的一種方案。9證明不定方程的正整數(shù)解組的個(gè)數(shù)為。解：該問(wèn)題即,求正整數(shù)r的n有序分拆。 問(wèn)題可轉(zhuǎn)換為：將r個(gè)無(wú)區(qū)別的球,放入n個(gè)不同的盒子中,每盒至少1個(gè)的

32、組合問(wèn)題。可以先在每個(gè)盒子中放1球,再將個(gè)無(wú)區(qū)別的球,放入n個(gè)不同的盒子中,每盒球數(shù)不限,則其方案數(shù)為：故該不定方程的正整數(shù)解組的個(gè)數(shù)為。 方法二：?jiǎn)栴}可以視為將r個(gè)相同的1放入n個(gè)盒子。由于將之間的值互換,對(duì)應(yīng)不同的解,所以盒子不同。設(shè)共有個(gè)解,則的母函數(shù)為所以10求方程的大于1的整數(shù)解的個(gè)數(shù)。解：該題相當(dāng)于將24的3有序分拆,并且要求每個(gè)分項(xiàng)大于1。 其母函數(shù)為： 所求的整數(shù)解的個(gè)數(shù)即為的系數(shù)：。11設(shè),其中,。試證： 1,； 2求出、的母函數(shù),。證明：1 2 因?yàn)?所以 同理, 所以, 解聯(lián)立方程組 ,即可得,12設(shè),求序列的母函數(shù),其中是S的滿足下列條件的n排列數(shù)：1S的每個(gè)元素都出現(xiàn)

33、奇數(shù)次；2S的每個(gè)元素至少出現(xiàn)4次；3至少出現(xiàn)i次；4至多出現(xiàn)i次；解：1母函數(shù)為：； 2母函數(shù)為：； 3母函數(shù)為：； 4母函數(shù)為：；13把23本書(shū)分給甲乙丙丁四人,要求這四個(gè)人得到的書(shū)的數(shù)量分別不超過(guò)9本、8本、7本、6本,問(wèn)：1若23本書(shū)相同,有多少種不同的分法？2若23本書(shū)都不相同,又有多少種不同的分法？解：1對(duì)應(yīng)的母函數(shù)為：所求的分法數(shù)就是的系數(shù),即種 2對(duì)應(yīng)的母函數(shù)為： 所求的分法數(shù)就是的系數(shù),即148臺(tái)計(jì)算機(jī)分給3個(gè)單位,第一個(gè)單位的分配量不超過(guò)3臺(tái),第二個(gè)單位不超過(guò)4臺(tái),第三個(gè)單位不超過(guò)5臺(tái),問(wèn)共有幾種分配方案？解：對(duì)應(yīng)的母函數(shù)為： 所求的分配方案數(shù)即的系數(shù),即分配方案數(shù)為：種1

34、5用母函數(shù)證明下列等式成立： 1； 2。證明：1 方法一：根據(jù)范德蒙恒等式令,即得 方法二：因?yàn)?兩邊展開(kāi)得 比較次方的系數(shù),即得2 方法一：令, 則 ,且,令則即因?yàn)?所以,故 所以 。證畢。 方法二：比較兩邊的系數(shù),即可得：。 方法三組合意義法等式右端：相當(dāng)于從個(gè)不同的球中取個(gè)球的組合,其組合方案數(shù)為；等式左端：把這個(gè)球編號(hào)為,按取出的球中最小的編號(hào),可分為如下的m+1類：如果取出的個(gè)球中最小編號(hào)是1,其余n個(gè)球要從去掉1號(hào)球后剩下的個(gè)球中選取,此類組合方案數(shù)為；如果取出的個(gè)球中最小編號(hào)是2,則1不能被選取,其余n個(gè)球要從去掉1,2號(hào)球后剩下的個(gè)球中選取,此類組合方案數(shù)為；,依次類推,如果

35、取出的個(gè)球中最小編號(hào)是m,則不能被選取,其余n個(gè)球要從去掉號(hào)球后剩下的個(gè)球中選取,此類組合方案數(shù)為；如果取出的個(gè)球中最小編號(hào)是,則不能被選取,其余n個(gè)球要從去掉號(hào)球后剩下的n個(gè)球中選取,此類組合方案數(shù)為；因此,按加法原理,從個(gè)不同的球中取個(gè)球的組合方案數(shù)為。故等式兩邊相等。16證明自然數(shù)n分拆為互異的正整數(shù)之和的分拆數(shù)等于n分拆為奇數(shù)之和的分拆數(shù)。證明：將n分拆為互異的正整數(shù)之和的分拆數(shù)的母函數(shù)為：將n分拆為奇數(shù)之和的分拆數(shù)的母函數(shù)為：所以,兩種分拆的方案數(shù)相同。17求自然數(shù)50的分拆總數(shù),要求分拆的每個(gè)分項(xiàng)不超過(guò)3。解：其母函數(shù)為： 則所求的分拆數(shù)為的系數(shù),即習(xí)題三遞推關(guān)系1解下列遞推關(guān)系：

36、12345解：1對(duì)應(yīng)的特征方程為：,解得。 所以齊次遞推方程的通解為：, 代入初始條件,得：, 解得：, 故 。 2對(duì)應(yīng)的特征方程為：,解得：, 所以,齊次遞推方程的通解為：, 代入初始條件, 解得：,故。 3對(duì)應(yīng)的特征方程為：,解得：, 所以,齊次遞推方程的通解為：, 代入初始條件, 解得：,故 。 4對(duì)應(yīng)的特征方程為：,解得：, 所以,齊次遞推方程的通解為：, 代入初始條件, 解得：,故 。 5對(duì)應(yīng)的特征方程為：,解得：, 所以,齊次遞推方程的通解為：, 代入初始條件,解得,故 2求由A,B,C,D組成的允許重復(fù)的排列中AB至少出現(xiàn)一次的排列數(shù)。解： 方法一：我們只要求出n位排列中不出現(xiàn)A

37、B的排列個(gè)數(shù),則至少出現(xiàn)一次AB的排列個(gè)數(shù)為?？梢苑殖蓛刹糠郑涸趎位排列中不出現(xiàn)AB且在第n位出現(xiàn)A的排列數(shù)目。：在n位排列中不出現(xiàn)AB且在第n位出現(xiàn)B或C或D的排列的數(shù)目。因此,顯然,若在n位排列中不出現(xiàn)AB,則在前位中也不會(huì)出現(xiàn)AB,考慮第n位：1若第n位為A,則第位可以是A、B、C、D中的任何一位；2若第n位為B,則第位只能是B、C、D中任何一位；3若第n位為C或D,則第為可以是A、B、C、D中任一位；故可得遞推關(guān)系：令 ,方程 兩邊同乘于,即將上面的式子進(jìn)行累加,可得：,故 ,即方程 兩邊同乘于,即同樣,將上面的式子進(jìn)行累加,可得故 ,即故可得關(guān)于的聯(lián)立方程組,解得： 故 , 因此,所

38、以。 方法二：設(shè)表示由A,B,C,D組成的允許重復(fù)的不出現(xiàn)AB的n位排列數(shù)目；由A,B,C,D組成的允許重復(fù)的不出現(xiàn)AB的n位排列數(shù)目,可分為兩個(gè)部分：1第n位是A,C或D,則前位不出現(xiàn)AB的排列數(shù)為,則此類排列數(shù)為；2第n位是B,前位形成的不出現(xiàn)AB的排列數(shù)有個(gè)。其中,要去掉第位是A的排列,這樣的排列由前位形成的不出現(xiàn)AB的個(gè)位排列,再加上AB形成,于是此類排列的數(shù)目為；根據(jù)加法法則,可得到遞推關(guān)系：對(duì)應(yīng)齊次方程的特征方程為：,解得,故齊次方程的通解為：,代入初始條件：,解得：,故因此,由A,B,C,D組成的允許重復(fù)的且AB至少出現(xiàn)一次的n位排列數(shù)目為 。3求n位二進(jìn)制數(shù)中相鄰兩位不出現(xiàn)11

39、的數(shù)的個(gè)數(shù)。解：設(shè)所求的n位二進(jìn)制數(shù)有個(gè),對(duì)第1位數(shù)的數(shù)值有兩種可能： 10,則余下的位數(shù),滿足條件的個(gè)數(shù)有個(gè)； 21,則第2位數(shù)只能為0,余下的位數(shù),滿足條件的個(gè)數(shù)有個(gè)； 由加法法則,可得：,且, 由遞推關(guān)系反推,可得, 所以,4利用遞推關(guān)系求下列和： 1 234解：1顯然, 對(duì)應(yīng)的齊次方程的特征方程為：,解得, 所以對(duì)應(yīng)的齊次方程對(duì)應(yīng)的通解為：, 因?yàn)?是特征根,所以對(duì)應(yīng)的特解為： 所以方程的通解為, 顯然,代入上式,可得,解得：,所以 方法二：顯然, 類似,可得 ,兩式相減,可得, 同理,可得 ,兩式再相減,可得,同理,可得,兩式再相減,可得關(guān)于的齊次定解問(wèn)題： 其特征方程為：,解得：,

40、 故 , 代入初始條件, 解得：,故 方法三快速求系數(shù)通解為：,初始條件：,代入得, 解得：, 所以,2顯然, 同理對(duì)應(yīng)的齊次方程的特征根為1,通解為, 非齊次方程的特解為：, 所以,非齊次方程的通解為：, 初始條件為：,代入上式,可得,解得：,所以 方法二：顯然,類似可得,兩式相減得,同理可得,兩式再相減得,同理得,兩式再相減,可得關(guān)于的齊次定解問(wèn)題： 由1知,方程的通解為：,代入初始條件得：,解得：,故 方法三快速求系數(shù)通解為：,初始條件：,代入得, 解得：, 所以,3顯然,同理對(duì)應(yīng)的齊次方程的特征根為1,特解為, 非齊次方程的特解為：, 所以,非齊次方程的通解為：, 初始條件為：,代入上

41、式,可得,解得：,所以 方法二：顯然,類似可得,兩式相減得,同理可得,兩式再相減得,同理得,兩式再相減,可得關(guān)于的齊次定解問(wèn)題： 由1知,方程的通解為：,代入初始條件得：,解得：,故 方法三快速求系數(shù)通解為：,初始條件：,代入得, 解得：, 所以,4顯然,同理對(duì)應(yīng)的齊次方程的特征根為1,特解為, 非齊次方程的特解為：, 所以,非齊次方程的通解為：, 初始條件為：,代入上式,可得,解得：,所以 方法二： 顯然,類似可得,兩式相減得,同理可得,兩式再相減得,同理得,兩式再相減得,同理可得,兩式再相減,可得關(guān)于的齊次定解問(wèn)題： 其特征方程為：,是五重特征根, 所以方程的通解為：,代入初始條件得：,解

42、得：,故 方法三快速求系數(shù)通解為：,初始條件：,代入得, 解得：, 所以,5求n位四進(jìn)制數(shù)中2和3必須出現(xiàn)偶數(shù)次的數(shù)目。解： 設(shè)符合條件的n位四進(jìn)制數(shù)有個(gè),2出現(xiàn)奇數(shù)次3出現(xiàn)偶數(shù)次的數(shù)有個(gè),2出現(xiàn)偶數(shù)次3出現(xiàn)奇數(shù)次的數(shù)有個(gè),兩者都出現(xiàn)奇數(shù)次的數(shù)有個(gè)。1對(duì)2和3出現(xiàn)偶數(shù)次的n位四進(jìn)制數(shù),考慮最高位,可分為三種情況：最高位是0或1,則在后續(xù)的個(gè)數(shù)字中2和3還必須出現(xiàn)偶數(shù)次,這樣的四進(jìn)制數(shù)共有個(gè)；最高位是2,后位必須有奇數(shù)個(gè)2偶數(shù)個(gè)3,這樣的數(shù)有個(gè)；最高位是3,后位必須有偶數(shù)個(gè)2奇數(shù)個(gè)3,這樣的數(shù)有個(gè)。各類情形,沒(méi)有重復(fù)的數(shù)。由加法法則,得滿足的遞推關(guān)系為：2對(duì)2出現(xiàn)奇數(shù)次3出現(xiàn)偶數(shù)次的n位四進(jìn)制數(shù)

43、,考慮最高位,可分為三種情況：最高位是0或1,則在后續(xù)的個(gè)數(shù)字中2出現(xiàn)奇數(shù)次3出現(xiàn)偶數(shù)次,這樣的四進(jìn)制數(shù)共有個(gè)；最高位是2,后位必須有偶數(shù)個(gè)2偶數(shù)個(gè)3,這樣的數(shù)有個(gè)；最高位是3,后位必須有奇數(shù)個(gè)2奇數(shù)個(gè)3,這樣的數(shù)有個(gè)。各類情形,沒(méi)有重復(fù)的數(shù)。由加法法則,得滿足的遞推關(guān)系為：3對(duì)2出現(xiàn)偶數(shù)次3出現(xiàn)奇數(shù)次的n位四進(jìn)制數(shù),考慮最高位,可分為三種情況：最高位是0或1,則在后續(xù)的個(gè)數(shù)字中2出現(xiàn)偶數(shù)次3出現(xiàn)奇數(shù)次,這樣的四進(jìn)制數(shù)共有個(gè)；最高位是2,后位必須有奇數(shù)個(gè)2奇數(shù)個(gè)3,這樣的數(shù)有個(gè)；最高位是3,后位必須有偶數(shù)個(gè)2偶數(shù)個(gè)3,這樣的數(shù)有個(gè)。各類情形,沒(méi)有重復(fù)的數(shù)。由加法法則,得滿足的遞推關(guān)系為：4對(duì)2

44、出現(xiàn)奇數(shù)次3出現(xiàn)奇數(shù)次的n位四進(jìn)制數(shù),考慮最高位,可分為三種情況：最高位是0或1,則在后續(xù)的個(gè)數(shù)字中2出現(xiàn)奇數(shù)次3出現(xiàn)奇數(shù)次,這樣的四進(jìn)制數(shù)共有個(gè)；最高位是2,后位必須有偶數(shù)個(gè)2奇數(shù)個(gè)3,這樣的數(shù)有個(gè)；最高位是3,后位必須有奇數(shù)個(gè)2偶數(shù)個(gè)3,這樣的數(shù)有個(gè)。各類情形,沒(méi)有重復(fù)的數(shù)。由加法法則,得滿足的遞推關(guān)系為： 故可得聯(lián)立方程組： 初始條件為：,對(duì)應(yīng)的母函數(shù)分別為：,從而可以得到關(guān)于母函數(shù)的聯(lián)立方程： 解得： 則即的系數(shù),所以 6試求由a,b,c三個(gè)字母組成的n位符號(hào)串中不出現(xiàn)aa圖像的符號(hào)串的數(shù)目。解：假設(shè)符合條件的符合串的數(shù)目為,考慮第1位數(shù)的數(shù)值,有兩種情況： 1第1位為a,則第2位只能

45、是b或c,余下的位滿足條件的有個(gè)； 根據(jù)乘法法則,這類情況總共有個(gè)； 2第1位為b或c,則余下的滿足條件的有個(gè)； 根據(jù)加法法則,可得遞推關(guān)系,且； 對(duì)應(yīng)的特征方程為：,解得：, 因此,通解為,代入初始條件,解得,故 7利用遞推關(guān)系解行列式：解：設(shè)行列式的值為,則 故可得到遞推關(guān)系： 對(duì)應(yīng)齊次方程的特征方程為：, 解得：,對(duì)于通解,根據(jù)a與b的關(guān)系分情況討論： 1,則通解為,代入初始條件,得, 解得,所以行列式的值為；。 2：則通解為：,代入初始條件,得, 解得,所以行列式的值為： 8在方格的棋盤(pán)上,放有k枚相同的車,設(shè)任意兩枚不能相互吃掉的放法數(shù)為,證明滿足遞推關(guān)系：證明：考慮第一行有兩種情況

46、： 1有1枚棋子,則余下的枚放在余下的棋盤(pán)上,有種放法；考慮棋子不能同行同列,棋盤(pán)上放了枚棋子后,要在第一行放1枚棋子,則該棋子可放的位置有：種,根據(jù)乘法法則,這類放法共有：2沒(méi)有棋子,則k枚棋子要放在余下的棋盤(pán)上,有放法；根據(jù)加法法則,可得。9在方格的棋盤(pán)中,令表示棋盤(pán)里正方形的個(gè)數(shù)不同的正方形可以疊交,試建立滿足的遞推關(guān)系。解：設(shè)每個(gè)正方形方格的面積為單位1,當(dāng)棋盤(pán)大小由變?yōu)闀r(shí),所增加的正方形為1個(gè)面積為1的小正方形；2包含1中小正方形且面積為4的正方形有：個(gè)；3包含1中小正方形且面積為9的正方形有：個(gè)；n所有方格組成的最大的正方形面積為,只有1個(gè)；因此,可以得到遞推關(guān)系：,即滿足的遞推關(guān)

47、系為：10過(guò)一個(gè)球的中心做n個(gè)平面,其中無(wú)3個(gè)平面過(guò)同一直徑,問(wèn)這些平面可把球的內(nèi)部分成多少個(gè)兩兩無(wú)公共部分的區(qū)域？解：設(shè)這n個(gè)平面把球內(nèi)部分成個(gè)兩兩無(wú)公共部分的區(qū)域,顯然：,。當(dāng)時(shí),去掉所給的n個(gè)平面中的一個(gè)平面P,則剩下的平面把球分成 個(gè)區(qū)域,?，F(xiàn)把平面P放回原處,則P與其余個(gè)平面都相交,且所得的條交線都不同因?yàn)闊o(wú)3個(gè)平面過(guò)同一直徑,這條交線把平面P分成部分,每部分把原來(lái)的一個(gè)區(qū)域劃分成兩個(gè)區(qū)域,故把平面P放回原處后增加了個(gè)區(qū)域,從而滿足遞推關(guān)系： 解得：11設(shè)空間的n個(gè)平面兩兩相交,每3個(gè)平面有且僅有一個(gè)公共點(diǎn),任意4個(gè)平面都不共點(diǎn),這樣的n個(gè)平面把空間分割成多少個(gè)不重疊的區(qū)域？解：設(shè)n

48、個(gè)的平面把空間所分割成的不重疊的區(qū)域數(shù)為； 顯然, 當(dāng)時(shí),去掉所給的n個(gè)平面中的一個(gè)平面P,則剩下的平面把空間分割成 個(gè)區(qū)域,。現(xiàn)把平面P放回原處,則P與其余個(gè)平面都相交,且所得的條交線兩兩相交每3個(gè)平面只有一個(gè)公共點(diǎn),且任意三條不共點(diǎn)任意4個(gè)平面都不共點(diǎn),這條交線將平面P分割成：個(gè)不重疊的區(qū)域n條直線能將平面分割成個(gè)不重疊的區(qū)域,參見(jiàn)習(xí)題第13題每部分把原來(lái)的一個(gè)區(qū)域劃分成兩個(gè)區(qū)域,故把平面P放回原處后增加了個(gè)區(qū)域,從而滿足遞推關(guān)系：下面解遞推方程,采用迭代法：見(jiàn)第一章習(xí)題第25題,12相鄰位不同為0的n位二進(jìn)制數(shù)中一共出現(xiàn)了多少個(gè)0？解：假設(shè)符合條件的n位二進(jìn)制數(shù)有個(gè),出現(xiàn)的0的個(gè)數(shù)為,

49、考慮第一位數(shù),有兩種情況： 1第1位數(shù)為0,則第2位必為1,余下的位的二進(jìn)制數(shù)有個(gè), 故這類情況,共出現(xiàn)0的個(gè)數(shù)為：； 2第1位數(shù)為1,則余下的位二進(jìn)制數(shù)有個(gè), 這類情況下,共出現(xiàn)0的個(gè)數(shù)位： 根據(jù)加法法則,可得到遞推關(guān)系：, 有遞推關(guān)系可反推得：,所以,令,則,對(duì)應(yīng)的齊次方程的特征方程為,解得,所以非齊次方程的通解為：, 同理,的通解為：, 則非齊次方程的通解為：, 代入初始條件,可得：, 解得：,所以,13平面上有兩兩相交,無(wú)3線共點(diǎn)的n條直線,試求這n條直線把平面分成多少個(gè)區(qū)域？解：設(shè)這n條直線,把平面分成個(gè)區(qū)域,顯然。 當(dāng)時(shí),去掉所給的n條直線中的一條直線L,則剩下的條直線把平面劃分成

50、個(gè)區(qū)域。現(xiàn)在把L放回原處,則L與其余條直線都相交,且所得的個(gè)交點(diǎn)都不同無(wú)三線共點(diǎn)。這個(gè)交點(diǎn)把直線L分成n段,每段把原來(lái)的區(qū)域劃分成兩個(gè)小區(qū)域,故把直線L放回原處后增加了n個(gè)區(qū)域,因此滿足遞推關(guān)系：, 用迭代法解： 所有式子相加,便可得：14證明Fibonacci數(shù)列的性質(zhì),當(dāng)時(shí), 1 2 34證明： 1用數(shù)學(xué)歸納法：時(shí),命題成立；時(shí),命題成立； 假設(shè)當(dāng)時(shí),命題成立,即, 當(dāng)時(shí), 所以,時(shí),命題也成立； 由歸納原理知,命題成立。 方法二：2 證明：定義,則有,并且,因此有： 將上述式子兩端各自相加并代入,即可得：3 證明：與2類似,同理, 將上述式子兩端各自相加并代入,即可得：4證明：采用數(shù)學(xué)歸

51、納法。時(shí),命題成立；時(shí),命題成立； 假設(shè)時(shí),命題成立,即, 當(dāng)時(shí), 即時(shí),命題也成立, 根據(jù)歸納法,命題成立。15證明： 1當(dāng)時(shí), 2當(dāng)時(shí),證明：用數(shù)學(xué)歸納法。1當(dāng)時(shí),等式成立；當(dāng)時(shí),等式成立；假設(shè)當(dāng)時(shí),等式成立,即,則,時(shí)有即當(dāng)時(shí),等式也成立,由歸納原理知,等式成立。2由Fibonacci數(shù)列的定義,反推得 當(dāng)時(shí),等式成立, 當(dāng)時(shí),等式成立；假設(shè)當(dāng)時(shí),等式成立,即,則,時(shí)有即當(dāng)時(shí),等式也成立,由歸納原理知,等式成立。16有2n個(gè)人在戲院售票處排隊(duì),每張戲票票價(jià)為5角,其中n個(gè)人各有一張5角錢,另外n個(gè)人各有一張1元錢,售票處無(wú)零錢可換。現(xiàn)將這2n個(gè)人看成一個(gè)序列,從第一個(gè)人開(kāi)始,任何部分子序

52、列內(nèi),都保證有5角錢的人不比有1元錢的人少,則售票工作能依次序進(jìn)行,否則,只能中斷,而請(qǐng)后面有5角錢的人先上來(lái)買票。前一種情況,售票工作能順利進(jìn)行,對(duì)應(yīng)的序列稱為依次可進(jìn)行的。問(wèn)有多少種這樣的序列？解：將持有5角的人看為1,持有1元的人看為0,則該問(wèn)題等價(jià)于： 在由n個(gè)1和n個(gè)0組成的2n位二進(jìn)制數(shù)中,從左到右掃描,1的累計(jì)數(shù)不小于0的累計(jì)數(shù),求這樣的二進(jìn)制數(shù)的個(gè)數(shù)。 見(jiàn)P73例。這樣的序列有：種17用表示具有整數(shù)邊長(zhǎng)且周長(zhǎng)為n的三角形的個(gè)數(shù),證明證明：三邊構(gòu)成三角形的充要條件是：任二邊之和都大于第三邊。1當(dāng)n是偶數(shù)時(shí)一方面,對(duì)于任一周長(zhǎng)為的整邊三角形,設(shè)其兩較短邊為a、b,較長(zhǎng)邊為c三邊可以

53、相等,即可以a=b=c,則必有a+bc。于是可以知道： ,從而三邊a+1,b+1,c+1可構(gòu)成一周長(zhǎng)為n的整邊三角形,因此,有。另一方面,對(duì)于任一周長(zhǎng)為n的整邊三角形,設(shè)其兩較短邊為a、b,較長(zhǎng)邊為c三邊可以相等,即可以a=b=c,則必有a+bc。由于n是偶數(shù),故可設(shè)；由,可知,即,因此,從而,因此,即,所以, ,因此三邊可構(gòu)成一周長(zhǎng)為的整邊三角形,因此有： 。綜上所述,就可以得到：。2當(dāng)n為奇數(shù)時(shí)對(duì)于任一周長(zhǎng)為n的整邊三角形,設(shè)其兩較短邊為a、b,較長(zhǎng)邊為c三邊可以相等,即可以a=b=c,則必有a+bc。由于n是奇數(shù),故可設(shè)因?yàn)?；由?所以,即,故,從而,因此,即,所以,即,可分兩種情況來(lái)討

54、論：這時(shí)能構(gòu)成一周長(zhǎng)為的整邊三角形,這種情況下,周長(zhǎng)為n的整邊三角形有個(gè)。這時(shí)三邊不能構(gòu)成周長(zhǎng)為的整邊三角形,而此時(shí)有：,因此 。n 當(dāng)為偶數(shù)時(shí)這時(shí)三邊有種構(gòu)成方案,即,因此三邊a,b,c也有種構(gòu)成方案,它們可構(gòu)成周長(zhǎng)為n的整邊三角形的數(shù)目為：個(gè)n 當(dāng)為奇數(shù)時(shí)這時(shí)三邊也有種構(gòu)成方案,即,因此三邊a,b,c也有種構(gòu)成方案,它們可構(gòu)成的周長(zhǎng)為n的整邊三角形的數(shù)目為：個(gè)綜上,滿足條件的周長(zhǎng)為n的整邊三角形的個(gè)數(shù)為： 個(gè)根據(jù)加法法則,由知,當(dāng)n為奇數(shù)時(shí)周長(zhǎng)為n的整邊三角形的總個(gè)數(shù)為：個(gè)181證明邊長(zhǎng)為整數(shù)且最大邊長(zhǎng)為r的三角形的個(gè)數(shù)是 2設(shè)為邊長(zhǎng)不超過(guò)的三角形的個(gè)數(shù),為邊長(zhǎng)不超過(guò)的三角形的個(gè)數(shù),求和的解析表達(dá)式。1證明：設(shè)三角形的三邊長(zhǎng)分別為,且,顯然,下面對(duì)r進(jìn)行討論。時(shí),這時(shí)符合條件的三角形只有1個(gè),即, 顯然 ,結(jié)論成立。時(shí),符合條件的三角形只有2個(gè),即、,這時(shí),結(jié)論成立。為偶數(shù)時(shí),若,則有k種方案,即,；若,則有k種方案,即,；若,則有種方案,即,；若,則有種方案,即,；若,則有1種方案,即；若,則有1種方案,即； 綜上,為偶數(shù)時(shí),總的方案數(shù)為：,結(jié)論成立。為奇數(shù)時(shí),若,則有種方案,即,；若,則有k種方案,即,；若,則有k種方案,即,；若,則有種方案,即,；若,則有種方案,即,；若,則有1種方案,即；若,則有1種方案,即；