《組合數(shù)學》第二版-課后習題答案全

組合數(shù)學（第二版）習題一（排列與組合）1在1到9999之間，有多少個每位上數(shù)字全不相同而且由奇數(shù)構(gòu)成的整數(shù)？解：該題相當于從“1，3，5，7，9”五個數(shù)字中分別選出1，2，3，4作排列的方案數(shù)； （1）選1個，即構(gòu)成1位數(shù)，共有個； （2）選2個，即構(gòu)成兩位數(shù)，共有個； （3）選3個，即構(gòu)成3位數(shù)，共有個； （4）選4個，即構(gòu)成4位數(shù)，共有個； 由加法法則可知，所求的整數(shù)共有：個。2比5400小并具有下列性質(zhì)的正整數(shù)有多少個？（1）每位的數(shù)字全不同；（2）每位數(shù)字不同且不出現(xiàn)數(shù)字2與7；解：（1）比5400小且每位數(shù)字全不同的正整數(shù)； 按正整數(shù)的位數(shù)可分為以下幾種情況： 一位數(shù)，可從19中任取一個，共有9個； 兩位數(shù)。十位上的數(shù)可從19中選取，個位數(shù)上的數(shù)可從其余9個數(shù)字中選取，根據(jù)乘法法則，共有個； 三位數(shù)。百位上的數(shù)可從19中選取，剩下的兩位數(shù)可從其余9個數(shù)中選2個進行排列，根據(jù)乘法法則，共有個； 四位數(shù)。又可分三種情況：n 千位上的數(shù)從14中選取，剩下的三位數(shù)從剩下的9個數(shù)字中選3個進行排列，根據(jù)乘法法則，共有個；n 千位上的數(shù)取5，百位上的數(shù)從13中選取，剩下的兩位數(shù)從剩下的8個數(shù)字中選2個進行排列，共有個；n 千位上的數(shù)取5，百位上的數(shù)取0，剩下的兩位數(shù)從剩下的8個數(shù)字中選2個進行排列，共有個； 根據(jù)加法法則，滿足條件的正整數(shù)共有：個；（2）比5400小且每位數(shù)字不同且不出現(xiàn)數(shù)字2與7的正整數(shù)；按正整數(shù)的位數(shù)可分為以下幾種情況：設 一位數(shù)，可從中任取一個，共有7個； 兩位數(shù)。十位上的數(shù)可從中選取，個位數(shù)上的數(shù)可從A中其余7個數(shù)字中選取，根據(jù)乘法法則，共有個； 三位數(shù)。百位上的數(shù)可從中選取，剩下的兩位數(shù)可從A其余7個數(shù)中選2個進行排列，根據(jù)乘法法則，共有個； 四位數(shù)。又可分三種情況：n 千位上的數(shù)從1，3，4中選取，剩下的三位數(shù)從A中剩下的7個數(shù)字中選3個進行排列，根據(jù)乘法法則，共有個；n 千位上的數(shù)取5，百位上的數(shù)從0，1，3中選取，剩下的兩位數(shù)從A中剩下的6個數(shù)字中選2個進行排列，共有個； 根據(jù)加法法則，滿足條件的正整數(shù)共有：個；3一教室有兩排，每排8個座位，今有14名學生，問按下列不同的方式入座，各有多少種做法？ （1）規(guī)定某5人總坐在前排，某4人總坐在后排，但每人具體座位不指定； （2）要求前排至少坐5人，后排至少坐4人。解：（1）因為就坐是有次序的，所有是排列問題。5人坐前排，其坐法數(shù)為，4人坐后排，其坐法數(shù)為， 剩下的5個人在其余座位的就坐方式有種， 根據(jù)乘法原理，就座方式總共有：（種） （2）因前排至少需坐6人，最多坐8人，后排也是如此?？煞殖扇N情況分別討論： 前排恰好坐6人，入座方式有； 前排恰好坐7人，入座方式有； 前排恰好坐8人，入座方式有；各類入座方式互相不同，由加法法則，總的入座方式總數(shù)為： ¨ 典型錯誤：先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個座位。故總的入坐方式共有：種。但這樣計算無疑是有重復的，例如恰好選6人坐前排，其余8人全坐后排，那么上式中的就有重復。4一位學者要在一周內(nèi)安排50個小時的工作時間，而且每天至少工作5小時，問共有多少種安排方案？解：用表示第i天的工作時間，則問題轉(zhuǎn)化為求不定方程的整數(shù)解的組數(shù)，且，于是又可以轉(zhuǎn)化為求不定方程的整數(shù)解的組數(shù)。該問題等價于：將15個沒有區(qū)別的球，放入7個不同的盒子中，每盒球數(shù)不限，即相異元素允許重復的組合問題。故安排方案共有： （種）¨ 另解：因為允許，所以問題轉(zhuǎn)化為長度為1的15條線段中間有14個空，再加上前后兩個空，共16個空，在這16個空中放入6個“”號，每個空放置的“”號數(shù)不限，未放“”號的線段合成一條線段，求放法的總數(shù)。從而不定方程的整數(shù)解共有：（組） 即共有54 264種安排方案。5若某兩人拒絕相鄰而坐，問12個人圍圓周就坐有多少種方式？解：12個人圍圓周就坐的方式有：種，設不愿坐在一起的兩人為甲和乙，將這兩個人相鄰而坐，可看為1人，則這樣的就坐方式有：種；由于甲乙相鄰而坐，可能是“甲乙”也可能是“乙甲”；所以則滿足條件的就坐方式有：種。6有15名選手，其中5名只能打后衛(wèi)，8名只能打前鋒，2名只能打前鋒或后衛(wèi)，今欲選出11人組成一支球隊，而且需要7人打前鋒，4人打后衛(wèi)，試問有多少種選法？解：用A、B、C分別代表5名打后衛(wèi)、8名打前鋒、2名可打前鋒或后衛(wèi)的集合，則可分為以下幾種情況： （1）7個前鋒從B中選取，有種選法，4個后衛(wèi)從A中選取，有種， 根據(jù)乘法法則，這種選取方案有：種； （2）7個前鋒從B中選取，從A中選取3名后衛(wèi)，從C中選1名后衛(wèi)， 根據(jù)乘法法則，這種選取方案有：種； （3）7個前鋒從B中選取，從A中選取2名后衛(wèi)，C中2名當后衛(wèi)， 根據(jù)乘法法則，這種選取方案有：種； （4）從B中選6個前鋒，從C中選1個前鋒，從A中選4個后衛(wèi)， 根據(jù)乘法法則，這種選取方案有：種； （5）從B中選6個前鋒，從C中選1個前鋒，從A中選3個后衛(wèi)，C中剩下的一個當后衛(wèi)，選取方案有：種； （6）從B中選5個前鋒，C中2個當前鋒，從A中選4個后衛(wèi)， 選取方案有：種； 根據(jù)加法法則，總的方案數(shù)為： 7求展開式中項的系數(shù)。解：令，則中項的系數(shù)為 ，即中，的系數(shù)，因此，的系數(shù)為：。8求的展開式。解：，展開式共有（項）， 所以，9求展開式中的系數(shù)。解：的系數(shù)為： 10試證任一整數(shù)n可唯一表示成如下形式： 證明：（1）可表示性。令，顯然， ，顯然，定義函數(shù)，顯然，即，由于f是用普通乘法和普通加法所定義的，故f無歧義，肯定是一個函數(shù)。從而必有一確定的數(shù)，使得，為了證明N中的任一數(shù)n均可表示成的形式，只需證明f是滿射函數(shù)即可。又因為f是定義在兩個有限且基數(shù)相等的函數(shù)上，因此如果能證明f單射，則f必是滿射。假設f不是單射，則存在，且有，使得由于，故必存在，使得。不妨設這個j是第一個使之不相等的，即，且，因為所以， 產(chǎn)生矛盾，所以f必是單射函數(shù)。因為，所以f必然也是滿射函數(shù)，故對任意的，都存在，使得 這說明對任意的整數(shù)，都可以表示成的形式。 （2）唯一性。 由于函數(shù)是一個單射，也是滿射，即f是雙射函數(shù)，故，對任意的，都存在唯一的，使得。否則，若存在另一個，使得將與f是單射函數(shù)矛盾。證畢。 11證明，并給出組合意義。證明：因為，現(xiàn)令，則可得 ，即組合意義：將n個元素分為3堆，1堆1個元素，1堆r個元素，1堆個元素?？梢杂邢旅鎯煞N不同的分法： （1）先從n個元素中選出個元素，剩下的個作為1堆；再將選出的個元素分為兩堆，1堆1個，1堆r個。 （2）先從n個元素中選出1人作為1堆，再從剩下的個中選出r個作為1堆，剩下的作為1堆。 顯然，兩種分法是等價的，所以等式成立。12證明 。證明：采用殊途同歸法。¨ 組合意義一：考慮從n個人中選出1名正式代表和若干名列席代表的選法（列席代表人數(shù)不限，可以為0）?？梢杂幸韵聝煞N不同的選法：（1）先選定正式代表，有種選法；然后從人中選列席代表，這 個人都有選和不選的兩種狀態(tài)，共有種選法；根據(jù)乘法法則，共有 種選法；（2）可以先選出人，然后再從中選出1名正式代表，其余k人作為列席代表，對于每個k，這樣的選法有：，從而總選法有： 顯然，兩種選法是等價的，所以等式成立。¨ 組合意義二：將n個不同的球放入標號為A、B、C的3個盒子，其中要求A盒只放1個球，其余兩盒的球數(shù)不限。那么，有兩種不同的放法：（1）先從n個不同的球中選出1個，放入A盒，再將其余個球放入另外兩盒，有種放法；（2）先從n個球中選出k個，再從所選的k個球中選出1個放入A盒，將其余的個球放入B盒，剩下的個球放入C盒，根據(jù)乘法法則，對于不同的k，有種放法。當時，各種情況互不重復，且包含了所有放法，根據(jù)加法法則，總的放法有：。 顯然兩種放法是等價的，故等式成立。¨ 另法：根據(jù)二項式定理：，兩邊求導，得： ，令，即得13有n個不同的整數(shù)，從中取出兩組來，要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù)，問有多少種方案？解：設這n個不同的數(shù)為，若假定第一組取個數(shù)，第二組取個數(shù)，并且令，則要求第一組數(shù)里的最小數(shù)大于第二組里的最大數(shù)，我們可以這樣來選：先從n個數(shù)中任選m個數(shù)出來，有種選法；再從這m個數(shù)中從大到小取個數(shù)作為第一組數(shù)，有種取法；再將其余的個數(shù)作為第二組數(shù)。故總方案數(shù)有：14六個引擎分列兩排，要求引擎的點火次序兩排交錯開來，試求從某一特定引擎開始點火有多少種方案？解：第一次點火僅有一種選擇，即點某個特定引擎的火；第二次點另一組某個引擎的火，有三種選擇；第三次有2種,。所以方案數(shù)為：（種）¨ 如果只指定從第一排先開始點火，不指定某一個，則方案數(shù)為（種）¨ 如果第一個引擎任意選，只要求點火過程是交錯的，則方案數(shù)為 （種）15試求從1到1 000 000的整數(shù)中，0出現(xiàn)了幾次？解：分別計算0出現(xiàn)在各個位上的次數(shù)。 （1）0出現(xiàn)在個位，此時符合條件的2位數(shù)有9個；3位數(shù)有個；4位數(shù)有個；5位數(shù)有個；6位數(shù)有個； （2）0出現(xiàn)在十位，此時符合條件的3位數(shù)有個；4位數(shù)有個；5位數(shù)有個；6位數(shù)有個； （3）0出現(xiàn)在百位，此時符合條件的4位數(shù)有個；5位數(shù)有個；6位數(shù)有個； （4）0出現(xiàn)在千位，此時符合條件的5位數(shù)有個；6位數(shù)有個； （5）0出現(xiàn)在萬位，此時符合條件的6位數(shù)有個； 另外1 000 000中有6個0。 所以，從1到1 000 000的整數(shù)中，0出現(xiàn)的次數(shù)總共有： （次）¨ 另法：先不考慮1 000 000本身，那么任一個000 000999 999之間的數(shù)都可以表示成如下形式：，其中每個是0到9的數(shù)字。因為每位數(shù)字可以有10種選擇，根據(jù)乘法法則，共有個“6位數(shù)”，又每個“6位數(shù)”由6個數(shù)字組成（包括無效0），所以共有個數(shù)字，又每個數(shù)字出現(xiàn)的概率相等， 所以0出現(xiàn)的次數(shù)應是，但習慣上在計算0的個數(shù)時，不包括無效0（即高位的0），因而要從中去掉無效0，其中：（1）1位數(shù)有9個（不包括0），其無效0共有個（即00000）；（2）2位數(shù)有90個，其無效0共個。依次類推，無效0的總數(shù)為 因為全為0時的6個0和1 000 000本身的6個0相互抵消，所以1到1 000 000之間的自然數(shù)中0出現(xiàn)的次數(shù)為（次）¨ 注意：1出現(xiàn)的次數(shù)為（要考慮1 000 000這個數(shù)的首位1），2，3，9各自出現(xiàn)的次數(shù)為。16n個男n個女排成一男女相間的隊伍，試問有多少種不同的方案？若圍成一圓桌坐下，又有多少種不同的方案？解：排成男女相間的隊伍：先將n個男的排成1行，共有種排法；再將n個女的往n個空里插，有種排法；由于可以先男后女，也可以先女后男，因此共有種排法；根據(jù)乘法法則，男女相間的隊伍共有：種方案。若圍成一圓周坐下，同理先將n個男的圍成一圓周，共有種排法，再將n個女的往n個空中插，有種排法，根據(jù)乘法法則，圍成圓周坐下，總的方案數(shù)有：種。17n個完全一樣的球，放到r個有標志的盒子，要求無一空盒，試證其方案數(shù)為。證明：因為沒有空盒，可先每盒放入一個球，再將剩余的球放入r個盒子中， 即將個無區(qū)別的球，放入r個不同的盒子中，每盒的球數(shù)不受限制， 因此方案數(shù)有：。¨ 另法：插空法。問題可看為：n個球排成1行，球與球之間形成個空，再在這個空中，插入個隔板，這樣就可形成r個盒子，每盒球不空的方案，其方案數(shù)為。18設，是k個素數(shù)，試求能整除盡數(shù)n的正整數(shù)數(shù)目。解：能整除數(shù)n的正整數(shù)即n的正約數(shù)，其個數(shù)為： 。19試求n個完全一樣的骰子能擲出多少種不同的方案？解：每個骰子有六個面，每個面的點數(shù)可以是中的一種。由于n個骰子完全一樣，故這樣相當于將n個完全一樣的球放到6個不同的盒子中，每盒球數(shù)不限。故方案數(shù)有（種）20凸十邊形的任意三個對角線不共點，試求這凸十邊形的對角線交于多少個點？又把所有的對角線分割成多少段？解：（1）從一個頂點可引出7條對角線，這7條對角線和其他頂點引出的對角線的交點情況如下：從右到左，和第一條對角線的交點有：個，和第二條的交點有，和第三條的交點有條，故和一個頂點引出的7條線相交的點為：，故和從10點引出的對角線交的點有個，但每個點重復了四次（因為每個點在兩條線上，而每條線又有兩個端點），故凸十邊形對角線交于個點。¨ 也可以直接這樣看：因為一個交點需要兩條對角線相交，而兩條對角線又需要多邊形的四個點構(gòu)成一四邊形。反之，從n個頂點中任取四個頂點，連成一四邊形，而四邊形的兩條對角線必須確定唯一的一個交點，故凸十邊形的對角線的交點共有：（個）（前提：任三個對角線不共點，否則，一個交點不能對應n邊形的唯一四個頂點）（2）由（1）知，一個點引出的7條對角線中，第一條線上有7個點，故將該線段分成8段；第二條線上有12個點，故將該線段分成13段，故從一個點出發(fā)的7條線上的段數(shù)為：?，F(xiàn)有10個點。故總的段數(shù)為：。但每段重復計算了2次（因為每條線有2個端點）故總的段數(shù)應為：。¨ 另法：一個交點給相交的兩條對角線各增加1段，所以對角線總的段數(shù)為： 對角線數(shù)2倍交點數(shù) （段）21試證一整數(shù)n是另一整數(shù)的平方的充要條件是除盡n的正整數(shù)的數(shù)目為奇數(shù)。證明：必要性：整數(shù)n可表示為，且為素數(shù)，則除盡n的正整數(shù)個數(shù)為：，若為偶數(shù)，則必存在為奇數(shù)，則n不可能寫成令一個數(shù)的平方。所以n是另一整數(shù)的平方的必要條件是除盡n的正整數(shù)數(shù)目為奇數(shù)。充分性：若除盡n的正整數(shù)的數(shù)目為奇數(shù)，則均為偶數(shù)，則 可寫成另一整數(shù)的平方。證畢。22統(tǒng)計力學需要計算r個質(zhì)點放到n個盒子里去，并分別服從下列假定之一，問有多少種不同的圖像？假設盒子始終是不同的。 （1）Maxwell-Boltzmann假定：r個質(zhì)點是不同的，任何盒子可以放任意個； （2）Bose-Einstein假定：r個質(zhì)點完全相同，每一個盒子可以放任意個。 （3）Fermi-Dirac假定：r個質(zhì)點都完全相同，每盒不得超過一個。解：（1）問題即：將r個不同的質(zhì)點放到n個不同的盒子，每個盒子放的質(zhì)點數(shù)不受限制，即相異元素允許重復排列，其方案數(shù)有： （2）問題即：將r個沒有區(qū)別的質(zhì)點放到n個不同的盒子，每個盒子方的質(zhì)點數(shù)不受限制，即相異元素允許重復組合，其方案數(shù)有： （3）問題即：將r個沒有區(qū)別的質(zhì)點放到n個不同的盒子，每盒不超過一個，即相異元素不允許重復的組合，其方案數(shù)有： 23從26個英文字母中取出6個字母組成一字，若其中有2或3個母音，問分別可構(gòu)成多少個字（不允許重復）？解：母音指元音，即a，e，i，o，u （1）有2個元音。先從5個元音中取出2個，再從剩下的21個字母中選出4個，再將6個字母進行全排列，則可構(gòu)成的字總共有： （個） （2）有3個元音。先從5個元音中取出3個，再從剩下的21個字母中選出4個，再將6個字母進行全排列，則可構(gòu)成的字總共有： （個）24給出的組合意義。證明：¨ 組合意義一：從個元素中取出個元素的組合數(shù)為：，且，其中第位置上的元素可取，當取時（），前邊的r個數(shù)可在這個數(shù)中取，故有種取法；后邊的個數(shù)可在這個數(shù)中取，故有種取法。根據(jù)乘法法則，當時，這樣的組合數(shù)為： 再根據(jù)加法法則，對進行求和，就有。¨ 組合意義二：（格路方法）等式左端：從點到點（），直接經(jīng)過點再到點的路徑數(shù)。從A到C的路徑數(shù)為：，從D到B的路徑數(shù)為：，根據(jù)乘法法則和加法法則，從A到B的路徑數(shù)有：。等式右端：從點到點的路徑數(shù)為： 25給出的組合意義。證明：（1）等式右端：從個元素中，任選個元素的組合方案數(shù)為：。 （2）等式左端：從不同元素中選取個元素，一定選元素，但不選元素的方案數(shù)。根據(jù)乘法法則，當k值取定時，這樣的方案數(shù)為從其余的個元素中任取r個的方案數(shù)，即，再根據(jù)加法法則，總的方案數(shù)有：26證明 。證明：考慮從m雙互不相同的鞋中取出n只，要求其中沒有任何兩只是成對的，求方案數(shù)。 一方面，先從m雙鞋中選取n雙，共有種選法，再從此n雙中每雙抽掉一只，有種取法，由乘法原理，總的方案數(shù)為：。 另一方面，先取出只左腳的鞋，再在其余的雙中取出只右腳的鞋，則總的方案數(shù)為： 所以，。¨ 另法：根據(jù) （）（）從而有： 27對于給定的正整數(shù)n，證明在所有中，當 時，取得最大值。證明：取與進行比較。， 當時，即， 當時，即， 因此，只有當或最接近時，取得最大值。28（1）用組合方法證明 和 都是整數(shù)。 （2）證明是整數(shù)。證明：（1）考慮個有區(qū)別的球放入n個不同的盒子里，每盒兩個，盒中球不計順序，則方案數(shù)為：，方案數(shù)是整數(shù)，所以是整數(shù)。同理，考慮個有區(qū)別的球放入n個不同的盒子里，每盒3個，盒中球不計順，則方案數(shù)為：，方案數(shù)是整數(shù)，所以是整數(shù)。 （2）考慮個不同的球放入n個相同的盒子，每盒n個，盒中球不計順序的方案。 先假設盒子是不同的，則這樣的方案數(shù)為：， 又盒子是相同的，所以方案數(shù)應為：， 方案數(shù)必然是整數(shù)，所以是整數(shù)。29（1）在2n個球中，有n個相同，求從這2n個球中選取n個的方案數(shù)。 （2）在個球中，有n個相同，求從這個球中選取n個的方案數(shù)。解：（1）問題即：從集合中，選取n個的方案數(shù)， 即多項式中的系數(shù)，即 從這2n個球中選取n個的方案數(shù)為種。 （2）問題即：從集合中，選取n個的方案數(shù)， 即多項式中的系數(shù)，即 30證明在由字母表生成的長度為n的字符串中， （1）0出現(xiàn)偶數(shù)次的字符串有個； （2），其中 。證明：（1）采用數(shù)學歸納法當時，0出現(xiàn)偶數(shù)次（0次），長度為1的字符串為“1”和“2”兩個字符串，而，故結(jié)論成立。假設當時，結(jié)論成立，即0出現(xiàn)偶數(shù)次，長度為k的字符串有個，當時，0出現(xiàn)偶數(shù)次，長度為的字符串包括兩部分： 在0出現(xiàn)偶數(shù)次，長度為k的字符串后面再增加一位不是0的數(shù)（只能是1或2），因此，這樣的字符串有個。 給0出現(xiàn)奇數(shù)次，長度為k的字符串后面再增加一個0， 因此，這樣的字符串有：。根據(jù)加法法則，0出現(xiàn)偶數(shù)次，長度為的字符串共有：，即時，結(jié)論也成立。 所以，根據(jù)數(shù)學歸納法，結(jié)論成立。（2）由（1）知，右端表示0出現(xiàn)偶數(shù)次的字符串數(shù)。 而左端代表的組合問題是：長度為n的字符串中，有0個0的字符串數(shù)有：， 有2個0的字符串數(shù)有：， ， 有q個0的字符串數(shù)有：，根據(jù)加法法則，可知，左端代表的是長度為n的字符串中0出現(xiàn)偶數(shù)次的字符串數(shù)，因此315臺教學儀器供m個學生使用，要求使用第1臺和第2臺的人數(shù)相等，有多少種分配方案？解： ¨ 方法一：先從m個學生中選取k個使用第1臺機器，再從剩下的個學生中選取k個使用第2臺機器，其余個學生可以任意使用剩下的3臺機器，按乘法原理，其組合數(shù)為，這里，于是，按加法原理，共有種使用方案。¨ 方法二：先從m個學生種選出2k個，再將選出2k個學生平均分到1、2臺機器上，其余的個學生可以任意使用剩下的3臺機器，按乘法法則，其組合數(shù)為，這里于是，按加法原理，共有種使用方案。 32由n個0及n個1組成的字符串，其任意前k個字符中，0的個數(shù)不少于1的個數(shù)的字符串有多少？解：（參見P21，例1.8.8）轉(zhuǎn)化為格路問題。即從點到，只能從對角線上方走，但可以碰到對角線的所有最短路徑數(shù)。顯然，第一步必然要走到點，因此可以轉(zhuǎn)換為從點到的所有滿足條件的路徑數(shù)，進一步，可以轉(zhuǎn)換為從點到，只能從對角線上方走，但不可以碰到對角線的所有路徑數(shù)，因為從點到的所有經(jīng)過對角線的路徑數(shù)與從點到點的所有路徑數(shù)是一一對應的，因此，所求的字符串有：（個）¨ 方法二：由n個1和n個0組成的2n位二進制數(shù)共有個(2n個不盡相異元素的全排列)，設所求的二進制數(shù)共有個，不符合要求的數(shù)有個。而不合要求的數(shù)的特征是從左向右掃描時，必然在某一位首次出現(xiàn)0的個數(shù)小于1的個數(shù)，即從左向右累計到第2k1位時出現(xiàn)k個0和個1。此時，后位上有個1，個0。將后部分的0改寫為1，1改寫為0。結(jié)果整個數(shù)變成由個和個0組成的2n位數(shù)z。即一個不合要求的數(shù)唯一對應于這樣的一個數(shù)z。反之，給定一個由個1和個0組成的2n位數(shù)z由于1比0多2個，故一定在某一位首次出現(xiàn)0的累計數(shù)少于1的累計數(shù)。依同法將此位后的0與1互換，使z變成由n個1和n個0組成的2n位數(shù)。所以，這兩種二進制數(shù)一一對應。即 故 。習題二（母函數(shù)及其應用）1求下列數(shù)列的母函數(shù) （1）； （2）； （3）；（4）；解：（1）母函數(shù)為：；  （2）母函數(shù)為：；¨ 方法二： （3）母函數(shù)為：；¨ 方法二： （4）母函數(shù)為：。¨ 方法二：2證明序列的母函數(shù)為 。證明：因為 令，則 ，而 故 又 所以 ¨ 方法二：已知的k-組合數(shù)為，其母函數(shù)為：序列的母函數(shù)為 3設，求序列的母函數(shù)。其中，是S的滿足下列條件的n組合數(shù)。（1）S的每個元素都出現(xiàn)奇數(shù)次；（2）S的每個元素都出現(xiàn)3的倍數(shù)次；（3）不出現(xiàn)，至多出現(xiàn)一次；（4）只出現(xiàn)1、3或11次，只出現(xiàn)2、4或5次；（5）S的每個元素至少出現(xiàn)10次。解：（1） （2） （3） （4） （5）4投擲兩個骰子，點數(shù)之和為r，其組合數(shù)是多少？解：用表示骰子的點數(shù)為i， （1）若兩個骰子不同，則問題等價于r的特殊有序2-分拆故相應的母函數(shù)為則點數(shù)之和為r的方案總數(shù)就是的系數(shù)。（2）若兩個骰子相同，則問題等價于r的特殊無序2-分拆而此問題又可轉(zhuǎn)化為求r的最大分項等于2，且項數(shù)不超過6的分拆數(shù)，即求方程的非負整數(shù)解的個數(shù)。相應的母函數(shù)為其中點數(shù)之和為r的方案數(shù)就是的系數(shù)。5投擲4個骰子，其點數(shù)之和為12的組合數(shù)是多少？解： 參考第4題。（第二版第5題）居民小區(qū)組織義務活動，號召每家出一到兩個人參加。設該小區(qū)共有n個家庭，現(xiàn)從中選出r人，問：（1）設每個家庭都是3口之家，有多少種不同的選法？當n=50時，選法有多少種？（2）設n個家庭中兩家有4口人，其余家庭都是3口人，有多少種選法？解：（1） （2） （第二版第6題）把n個相同的小球放入編號為的m個盒子中，使得每個盒子內(nèi)的球數(shù)不小于它的編號數(shù)。已知，求不同的放球方法數(shù)。解：對應母函數(shù)為：故6紅、黃、藍三色的球各8個，從中取出9個，要求每種顏色的球至少一個，問有多少種不同的取法？解：對應的母函數(shù)為： 從中取9個對應的組合數(shù)為的系數(shù)，即 （種） ¨ 方法二：原問題等價于從集合中取出9個元素，且每個元素至少取一個。現(xiàn)在先把元素a、b、c各取一個，然后再隨意選出6個，則問題轉(zhuǎn)變?yōu)閺募现腥〕?個元素，且每個元素個數(shù)不限，求重復組合的方案數(shù)。又由于每個元素的個數(shù)大于6，故從中取6個元素與從集合中取出6個元素的組合數(shù)一樣多，因此不同的取法為（種） 7將幣值為2角的人民幣，兌換成硬幣（壹分、貳分和伍分）可有多少種兌換方法？解：該題用1分、2分、5分的硬幣組成20分。是可重復的無序拆分： 其母函數(shù)為： 則不同的兌換方法為的系數(shù)，即 即有29種兌換方法。8有1克重砝碼2枚，2克重砝碼3枚，5克重砝碼3枚，要求這8個砝碼只許放在天平的一端，能稱幾種重量的物品？有多少種不同的稱法？解：該題屬于有限重復的無序拆分問題。對應的母函數(shù)為： 所以能稱123克等23種重量的物品。 總共的稱法為母函數(shù)的各項系數(shù)之和，再減去常數(shù)項，即總共有（種）不同的稱法。其中，稱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ù)：項即為稱克重量的一種方案。9證明不定方程的正整數(shù)解組的個數(shù)為。解：該問題即，求正整數(shù)r的n有序分拆。 問題可轉(zhuǎn)換為：將r個無區(qū)別的球，放入n個不同的盒子中，每盒至少1個的組合問題?？梢韵仍诿總€盒子中放1球，再將個無區(qū)別的球，放入n個不同的盒子中，每盒球數(shù)不限，則其方案數(shù)為：故該不定方程的正整數(shù)解組的個數(shù)為。¨ 方法二：問題可以視為將r個相同的1放入n個盒子。由于將之間的值互換，對應不同的解，所以盒子不同。設共有個解，則的母函數(shù)為所以 10求方程的大于1的整數(shù)解的個數(shù)。解：該題相當于將24的3有序分拆，并且要求每個分項大于1。 其母函數(shù)為： 所求的整數(shù)解的個數(shù)即為的系數(shù)：。11設，其中，。試證： （1），； （2）求出、的母函數(shù)，。證明：（1） （2） 因為 所以 同理， 所以， 解聯(lián)立方程組 ，即可得 ，12設，求序列的母函數(shù)，其中是S的滿足下列條件的n排列數(shù)：（1）S的每個元素都出現(xiàn)奇數(shù)次；（2）S的每個元素至少出現(xiàn)4次；（3）至少出現(xiàn)i次；（4）至多出現(xiàn)i次；解：（1）母函數(shù)為：； （2）母函數(shù)為：； （3）母函數(shù)為：； （4）母函數(shù)為：；13把23本書分給甲乙丙丁四人，要求這四個人得到的書的數(shù)量分別不超過9本、8本、7本、6本，問：（1）若23本書相同，有多少種不同的分法？（2）若23本書都不相同，又有多少種不同的分法？解：（1）對應的母函數(shù)為：所求的分法數(shù)就是的系數(shù)，即 （種） （2）對應的母函數(shù)為： 所求的分法數(shù)就是的系數(shù)，即148臺計算機分給3個單位，第一個單位的分配量不超過3臺，第二個單位不超過4臺，第三個單位不超過5臺，問共有幾種分配方案？解：對應的母函數(shù)為： 所求的分配方案數(shù)即的系數(shù)，即分配方案數(shù)為： （種）15用母函數(shù)證明下列等式成立： （1）； （2）。證明：（1）¨ 方法一：根據(jù)范德蒙恒等式令，即得¨ 方法二：因為，兩邊展開得 比較次方的系數(shù)，即得 （2）¨ 方法一：令， 則 ，且，令則即因為，所以，故 所以 。證畢。¨ 方法二：比較兩邊的系數(shù)，即可得：。¨ 方法三（組合意義法）等式右端：相當于從個不同的球中取個球的組合，其組合方案數(shù)為；等式左端：把這個球編號為，按取出的球中最小的編號，可分為如下的m+1類：如果取出的個球中最小編號是1，其余n個球要從去掉1號球后剩下的個球中選取，此類組合方案數(shù)為；如果取出的個球中最小編號是2，則1不能被選取，其余n個球要從去掉1，2號球后剩下的個球中選取，此類組合方案數(shù)為；，依次類推，如果取出的個球中最小編號是m，則不能被選取，其余n個球要從去掉號球后剩下的個球中選取，此類組合方案數(shù)為；如果取出的個球中最小編號是，則不能被選取，其余n個球要從去掉號球后剩下的n個球中選取，此類組合方案數(shù)為；因此，按加法原理，從個不同的球中取個球的組合方案數(shù)為。故等式兩邊相等。16證明自然數(shù)n分拆為互異的正整數(shù)之和的分拆數(shù)等于n分拆為奇數(shù)之和的分拆數(shù)。證明：將n分拆為互異的正整數(shù)之和的分拆數(shù)的母函數(shù)為： 將n分拆為奇數(shù)之和的分拆數(shù)的母函數(shù)為： 所以，兩種分拆的方案數(shù)相同。17求自然數(shù)50的分拆總數(shù)，要求分拆的每個分項不超過3。解：其母函數(shù)為： 則所求的分拆數(shù)為的系數(shù)，即習題三（遞推關系）1解下列遞推關系：（1）（2）（3）（4）（5）解：（1）對應的特征方程為：，解得。 所以齊次遞推方程的通解為：， 代入初始條件，得：， 解得：， 故 。 （2）對應的特征方程為：，解得：， 所以，齊次遞推方程的通解為：， 代入初始條件， 解得：，故。 （3）對應的特征方程為：，解得：， 所以，齊次遞推方程的通解為：， 代入初始條件， 解得：，故 。 （4）對應的特征方程為：，解得：， 所以，齊次遞推方程的通解為：， 代入初始條件， 解得：，故 。 （5）對應的特征方程為：，解得：， 所以，齊次遞推方程的通解為：， 代入初始條件，解得，故 2求由A，B，C，D組成的允許重復的排列中AB至少出現(xiàn)一次的排列數(shù)。解：¨ 方法一：我們只要求出n位排列中不出現(xiàn)AB的排列個數(shù)，則至少出現(xiàn)一次AB的排列個數(shù)為?？梢苑殖蓛刹糠郑涸趎位排列中不出現(xiàn)AB且在第n位出現(xiàn)A的排列數(shù)目。：在n位排列中不出現(xiàn)AB且在第n位出現(xiàn)B或C或D的排列的數(shù)目。因此，顯然，若在n位排列中不出現(xiàn)AB，則在前位中也不會出現(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中任一位；故可得遞推關系：令 ，方程 兩邊同乘于，即 將上面的式子進行累加，可得：，故 ，即方程 兩邊同乘于，即同樣，將上面的式子進行累加，可得故 ，即故可得關于的聯(lián)立方程組，解得： 故 ， 因此，所以 。¨ 方法二：設表示由A，B，C，D組成的允許重復的不出現(xiàn)AB的n位排列數(shù)目；由A，B，C，D組成的允許重復的不出現(xiàn)AB的n位排列數(shù)目，可分為兩個部分：（1）第n位是A，C或D，則前位不出現(xiàn)AB的排列數(shù)為，則此類排列數(shù)為；（2）第n位是B，前位形成的不出現(xiàn)AB的排列數(shù)有個。其中，要去掉第位是A的排列，這樣的排列由前位形成的不出現(xiàn)AB的個位排列，再加上AB形成，于是此類排列的數(shù)目為；根據(jù)加法法則，可得到遞推關系：對應齊次方程的特征方程為：，解得，故齊次方程的通解為：，代入初始條件：，解得：，故因此，由A，B，C，D組成的允許重復的且AB至少出現(xiàn)一次的n位排列數(shù)目為 。3求n位二進制數(shù)中相鄰兩位不出現(xiàn)11的數(shù)的個數(shù)。解：設所求的n位二進制數(shù)有個，對第1位數(shù)的數(shù)值有兩種可能： （1）0，則余下的位數(shù)，滿足條件的個數(shù)有個； （2）1，則第2位數(shù)只能為0，余下的位數(shù)，滿足條件的個數(shù)有個； 由加法法則，可得：，且， 由遞推關系反推，可得， 所以， 4利用遞推關系求下列和： （1） （2）（3）（4）解：（1）顯然， ， 對應的齊次方程的特征方程為：，解得， 所以對應的齊次方程對應的通解為：， 因為1是特征根，所以對應的特解為： 所以方程的通解為， 顯然，代入上式，可得 ，解得：，所以 ¨ 方法二：顯然， 類似，可得 ，兩式相減，可得， 同理，可得 ，兩式再相減，可得 ，同理，可得，兩式再相減，可得關于的齊次定解問題： 其特征方程為：，解得：， 故 ， 代入初始條件， 解得：，故¨ 方法三（快速求系數(shù)）通解為：， 初始條件：，代入得 ， 解得：， 所以，（2）顯然， 同理對應的齊次方程的特征根為1，通解為， 非齊次方程的特解為：， 所以，非齊次方程的通解為：， 初始條件為：，代入上式，可得 ，解得：，所以 ¨ 方法二：顯然，類似可得，兩式相減得，同理可得，兩式再相減得，同理得，兩式再相減，可得關于的齊次定解問題： 由（1）知，方程的通解為：，代入初始條件得：，解得：，故 ¨ 方法三（快速求系數(shù)）通解為：， 初始條件：，代入得 ， 解得：， 所以，（3）顯然，同理對應的齊次方程的特征根為1，特解為， 非齊次方程的特解為：， 所以，非齊次方程的通解為：， 初始條件為：，代入上式，可得 ，解得：，所以 ¨ 方法二：顯然，類似可得，兩式相減得，同理可得，兩式再相減得，同理得，兩式再相減，可得關于的齊次定解問題： 由（1）知，方程的通解為：，代入初始條件得：，解得：，故 ¨ 方法三（快速求系數(shù)）通解為：， 初始條件：，代入得 ， 解得：， 所以，（4）顯然，同理對應的齊次方程的特征根為1，特解為， 非齊次方程的特解為：， 所以，非齊次方程的通解為：， 初始條件為：，代入上式，可得 ，解得：，所以 ¨ 方法二： 顯然，類似可得，兩式相減得，同理可得，兩式再相減得，同理得，兩式再相減得，同理可得，兩式再相減，可得關于的齊次定解問題： 其特征方程為：，是五重特征根， 所以方程的通解為：，代入初始條件得：，解得：，故 ¨ 方法三（快速求系數(shù)）通解為：， 初始條件：，代入得 ， 解得：， 所以，5求n位四進制數(shù)中2和3必須出現(xiàn)偶數(shù)次的數(shù)目。解： 設符合條件的n位四進制數(shù)有個，2出現(xiàn)奇數(shù)次3出現(xiàn)偶數(shù)次的數(shù)有個，2出現(xiàn)偶數(shù)次3出現(xiàn)奇數(shù)次的數(shù)有個，兩者都出現(xiàn)奇數(shù)次的數(shù)有個。（1）對2和3出現(xiàn)偶數(shù)次的n位四進制數(shù)，考慮最高位，可分為三種情況： 最高位是0或1，則在后續(xù)的個數(shù)字中2和3還必須出現(xiàn)偶數(shù)次，這樣的四進制數(shù)共有個； 最高位是2，后位必須有奇數(shù)個2偶數(shù)個3，這樣的數(shù)有個； 最高位是3，后位必須有偶數(shù)個2奇數(shù)個3，這樣的數(shù)有個。各類情形，沒有重復的數(shù)。由加法法則，得滿足的遞推關系為：（2）對2出現(xiàn)奇數(shù)次3出現(xiàn)偶數(shù)次的n位四進制數(shù)，考慮最高位，可分為三種情況： 最高位是0或1，則在后續(xù)的個數(shù)字中2出現(xiàn)奇數(shù)次3出現(xiàn)偶數(shù)次，這樣的四進制數(shù)共有個； 最高位是2，后位必須有偶數(shù)個2偶數(shù)個3，這樣的數(shù)有個； 最高位是3，后位必須有奇數(shù)個2奇數(shù)個3，這樣的數(shù)有個。各類情形，沒有重復的數(shù)。由加法法則，得滿足的遞推關系為：（3）對2出現(xiàn)偶數(shù)次3出現(xiàn)奇數(shù)次的n位四進制數(shù)，考慮最高位，可分為三種情況： 最高位是0或1，則在后續(xù)的個數(shù)字中2出現(xiàn)偶數(shù)次3出現(xiàn)奇數(shù)次，這樣的四進制數(shù)共有個； 最高位是2，后位必須有奇數(shù)個2奇數(shù)個3，這樣的數(shù)有個； 最高位是3，后位必須有偶數(shù)個2偶數(shù)個3，這樣的數(shù)有個。各類情形，沒有重復的數(shù)。由加法法則，得滿足的遞推關系為：（4）對2出現(xiàn)奇數(shù)次3出現(xiàn)奇數(shù)次的n位四進制數(shù)，考慮最高位，可分為三種情況： 最高位是0或1，則在后續(xù)的個數(shù)字中2出現(xiàn)奇數(shù)次3出現(xiàn)奇數(shù)次，這樣的四進制數(shù)共有個； 最高位是2，后位必須有偶數(shù)個2奇數(shù)個3，這樣的數(shù)有個； 最高位是3，后位必須有奇數(shù)個2偶數(shù)個3，這樣的數(shù)有個。各類情形，沒有重復的數(shù)。由加法法則，得滿足的遞推關系為： 故可得聯(lián)立方程組： 初始條件為：， 對應的母函數(shù)分別為：， ，從而可以得到關于母函數(shù)的聯(lián)立方程： 解得： 則即的系數(shù)，所以 （） 6試求由a，b，c三個字母組成的n位符號串中不出現(xiàn)aa圖像的符號串的數(shù)目。解：假設符合條件的符合串的數(shù)目為，考慮第1位數(shù)的數(shù)值，有兩種情況： （1）第1位為a，則第2位只能是b或c，余下的位滿足條件的有個； 根據(jù)乘法法則，這類情況總共有個； （2）第1位為b或c，則余下的滿足條件的有個； 根據(jù)加法法則，可得遞推關系，且； 對應的特征方程為：，解得：， 因此，通解為，代入初始條件， ，解得，故 7利用遞推關系解行列式： 解：設行列式的值為，則 故可得到遞推關系： 對應齊次方程的特征方程為：， 解得：，對于通解，根據(jù)a與b的關系分情況討論： （1），則通解為，代入初始條件，得 ， 解得，所以行列式的值為；（）。 （2）：則通解為：，代入初始條件，得 ， 解得，所以行列式的值為： （） 8在方格的棋盤上，放有k枚相同的車，設任意兩枚不能相互吃掉的放法數(shù)為，證明滿足遞推關系： 證明：考慮第一行有兩種情況： （1）有1枚棋子，則余下的枚放在余下的棋盤上，有種放法；考慮棋子不能同行同列，棋盤上放了枚棋子后，要在第一行放1枚棋子，則該棋子可放的位置有：種，根據(jù)乘法法則，這類放法共有：（2）沒有棋子，則k枚棋子要放在余下的棋盤上，有放法；根據(jù)加法法則，可得。9在方格的棋盤中，令表示棋盤里正方形的個數(shù)（不同的正方形可以疊交），試建立滿足的遞推關系。解：設每個正方形方格的面積為單位1，當棋盤大小由變?yōu)闀r，所增加的正方形為（1）個面積為1的小正方形；（2）包含（1）中小正方形且面積為4的正方形有：個；（3）包含（1）中小正方形且面積為9的正方形有：個； （n）所有方格組成的最大的正方形（面積為），只有1個；因此，可以得到遞推關系： ，即滿足的遞推關系為：10過一個球的中心做n個平面，其中無3個平面過同一直徑，問這些平面可把球的內(nèi)部分成多少個兩兩無公共部分的區(qū)域？解：設這n個平面把球內(nèi)部分成個兩兩無公共部分的區(qū)域，顯然：，。當時，去掉所給的n個平面中的一個平面P，則剩下的平面把球分成 個區(qū)域，?，F(xiàn)把平面P放回原處，則P與其余個平面都相交，且所得的條交線都不同（因為無3個平面過同一直徑），這條交線把平面P分成部分，每部分把原來的一個區(qū)域劃分成兩個區(qū)域，故把平面P放回原處后增加了個區(qū)域，從而滿足遞推關系： 解得：11設空間的n個平面兩兩相交，每3個平面有且僅有一個公共點，任意4個平面都不共點，這樣的n個平面把空間分割成多少個不重疊的區(qū)域？解：設n個的平面把空間所分割成的不重疊的區(qū)域數(shù)為； 顯然， 當時，去掉所給的n個平面中的一個平面P，則剩下的平面把空間分割成 個區(qū)域，?，F(xiàn)把平面P放回原處，則P與其余個平面都相交，且所得的條交線兩兩相交（每3個平面只有一個公共點），且任意三條不共點（任意4個平面都不共點），這條交線將平面P分割成：（個）不重疊的區(qū)域（n條直線能將平面分割成個不重疊的區(qū)域，參見習題第13題）每部分把原來的一個區(qū)域劃分成兩個區(qū)域，故把平面P放回原處后增加了個區(qū)域，從而滿足遞推關系：下面解遞推方程，采用迭代法：（見第一章習題第25題，）12相鄰位不同為0的n位二進制數(shù)中一共出現(xiàn)了多少個0？解：假設符合條件的n位二進制數(shù)有個，出現(xiàn)的0的個數(shù)為， 考慮第一位數(shù)，有兩種情況： （1）第1位數(shù)為0，則第2位必為1，余下的位的二進制數(shù)有個， 故這類情況，共出現(xiàn)0的個數(shù)為：； （2）第1位數(shù)為1，則余下的位二進制數(shù)有個， 這類情況下，共出現(xiàn)0的個數(shù)位： 根據(jù)加法法則，可得到遞推關系：， 有遞推關系可反推得：，所以，令，則，對應的齊次方程的特征方程為，解得，所以非齊次方程的通解為：， 同理，的通解為：， 則非齊次方程的通解為： ， 代入初始條件，可得：， ， 解得：，所以，13平面上有兩兩相交，無3線共點的n條直線，試求這n條直線把平面分成多少個區(qū)域？解：設這n條直線，把平面分成個區(qū)域，顯然。 當時，去掉所給的n條直線中的一條直線L，則剩下的條直線把平面劃分成個區(qū)域?，F(xiàn)在把L放回原處，則L與其余條直線都相交，且所得的個交點都不同（無三線共點）。這個交點把直線L分成n段，每段把原來的區(qū)域劃分成兩個小區(qū)域，故把直線L放回原處后增加了n個區(qū)域，因此滿足遞推關系： ， 用迭代法解： 所有式子相加，便可得：14證明Fibonacci數(shù)列的性質(zhì)，當時， （1） （2） （3）（4）證明： （1）用數(shù)學歸納法： 時，命題成立； 時，命題成立； 假設當時，命題成立，即， 當時， 所以，時，命題也成立； 由歸納原理知，命題成立。¨ 方法二： （2） 證明：定義，則有，并且，因此有： 將上述式子兩端各自相加并代入，即可得：（3） 證明：與（2）類似，同理， 將上述式子兩端各自相加并代入，即可得：（4）證明：采用數(shù)學歸納法。 時，命題成立； 時，命題成立； 假設時，命題成立，即， 當時， 即時，命題也成立， 根據(jù)歸納法，命題成立。15證明： （1）當時， （2）當時，證明：用數(shù)學歸納法。（1）當時，等式成立；當時，等式成立；假設當時，等式成立，即，則，時有即當時，等式也成立，由歸納原理知，等式成立。（2）由Fibonacci數(shù)列的定義，反推得 當時，等式成立， 當時，等式成立；假設當時，等式成立，即，則，時有即當時，等式也成立，由歸納原理知，等式成立。16有2n個人在戲院售票處排隊，每張戲票票價為5角，其中n個人各有一張5角錢，另外n個人各有一張1元錢，售票處無零錢可換。現(xiàn)將這2n個人看成一個序列，從第一個人開始，任何部分子序列內(nèi)，都保證有5角錢的人不比有1元錢的人少，則售票工作能依次序進行，否則，只能中斷，而請后面有5角錢的人先上來買票。前一種情況，售票工作能順利進行，對應的序列稱為依次可進行的。問有多少種這樣的序列？解：將持有5角的人看為1，持有1元的人看為0，則該問題等價于： 在由n個1和n個0組成的2n位二進制數(shù)中，從左到右掃描，1的累計數(shù)不小于0的累計數(shù)，求這樣的二進制數(shù)的個數(shù)。 見P73例3.4.11。這樣的序列有：（種）17用表示具有整數(shù)邊長且周長為n的三角形的個數(shù)，證明 證明：三邊構(gòu)成三角形的充要條件是：任二邊之和都大于第三邊。（1）當n是偶數(shù)時一方面，對于任一周長為的整邊三角形，設其兩較短邊為a、b，較長邊為c（三邊可以相等，即可以a=b=c），則必有a+b>c。于是可以知道： ，從而三邊a+1，b+1，c+1可構(gòu)成