組合數(shù)學作業(yè)答案

1、第二章作業(yè)答案7. 證明，對任意給定的52個整數(shù)，存在兩個整數(shù)，要么兩者的和能被100整除，要么兩者的差能被100整除。證明 用100分別除這52個整數(shù)，得到的余數(shù)必為0, 1, 99這100個數(shù)之一。將余數(shù)是0的數(shù)分為一組，余數(shù)是1和99的數(shù)分為一組，余數(shù)是49和51的數(shù)分為一組，將余數(shù)是50的數(shù)分為一組。這樣，將這52個整數(shù)分成了51組。由鴿巢原理知道，存在兩個整數(shù)分在了同一組，設它們是a和b。若a和b被100除余數(shù)相同，則能被100整除。若a和b被100除余數(shù)之和是100，則能被100整除。11. 一個學生有37天用來準備考試。根據過去的經驗，她知道她需要不超過60小時的學習時間。她還希

2、望每天至少學習1小時。證明，無論她如何安排她的學習時間（不過，每天都是整數(shù)個小時），都存在連續(xù)的若干天，在此期間她恰好學習了13小時。證明 設從第一天到第i天她共學習了小時。因為她每天至少學習1小時，所以和都是嚴格單調遞增序列。因為總的學習時間不超過60小時，所以，。, 是1和73之間的74個整數(shù)，由鴿巢原理知道，它們中存在相同的整數(shù)，有和使得，從第天到第i天她恰好學習了13小時。14. 一只袋子裝了100個蘋果、100個香蕉、100個桔子和100個梨。如果我每分鐘從袋子里取出一個水果，那么需要多少時間我就能肯定至少已拿出了1打相同種類的水果？解 由加強形式的鴿巢原理知道，如果從袋子中取出個水

3、果，則能肯定至少已拿出12個相同種類的水果。因此，需要45分鐘。17. 證明：在一群個人中，存在兩個人，他們在這群人中有相同數(shù)目的熟人（假設沒有人與他/她自己是熟人）。證明 因為每個人都不是自己的熟人，所以每個人的熟人的數(shù)目是從0到的整數(shù)。若有兩個人的熟人的數(shù)目分別是0和，則有人誰都不認識，有人認識所有的人，這是不可能的。因此，這n個人的熟人的數(shù)目是個整數(shù)之一，必有兩個人有相同數(shù)目的熟人。第三章作業(yè)答案6. 有多少使下列性質同時成立的大于5400的整數(shù)？(a) 各位數(shù)字互異。(b) 數(shù)字2和7不出現(xiàn)。解 因為只能出現(xiàn)數(shù)字0, 1, 3, 4, 5, 6, 8, 9，所以整數(shù)的位數(shù)至多為8。 考

4、慮8位整數(shù)。最高位不能為0，因此8位整數(shù)有個。 考慮7位整數(shù)。最高位不能為0，因此8位整數(shù)有個。 考慮6位整數(shù)。最高位不能為0，因此8位整數(shù)有個。 考慮5位整數(shù)。最高位不能為0，因此8位整數(shù)有個。 考慮4位整數(shù)。若千位數(shù)字大于5，有個。若千位數(shù)字等于5，則百位數(shù)字必須大于等于4，有個。根據加法原理，符合條件的整數(shù)的個數(shù)為8. 15人圍坐一個圓桌。如果B拒絕挨著A坐，有多少種圍坐方式？如果B只拒絕坐在A的右側，又有多少種圍坐方式？解 15人圍坐一個圓桌，有種圍坐方式。若B固定坐在A的左側，則可將看作一個整體，有種圍坐方式。若B固定坐在A的右側，則可將看作一個整體，有種圍坐方式。因此，B不挨著A坐

5、的圍坐方式有種，B不坐在A的右側的圍坐方式有種。11. 從15個球員的集合中選人組成11個球員的足球隊，其中5人只能踢后衛(wèi)，8人只能踢邊衛(wèi)，2人既能踢后衛(wèi)又能踢邊衛(wèi)。假設足球隊有7個人踢邊衛(wèi)4個人踢后衛(wèi)，確定足球隊可能的組隊方法數(shù)。解 設甲和乙既能踢后衛(wèi)又能踢邊衛(wèi)。若甲和乙均不入選，組隊方法數(shù)為。若甲和乙均入選，組隊方法數(shù)為+。若甲入選且乙不入選，組隊方法數(shù)為+。若乙入選且甲不入選，組隊方法數(shù)也為+。因此，組隊方法數(shù)總共為+=112021. 一位秘書在距離家以東9個街區(qū)、以北7個街區(qū)的一座大樓里工作。每天他都要步行16個街區(qū)去上班。(a) 對他來說可能有多少不同的路線？(b) 如果在他家以東4

6、個街區(qū)、以北3個街區(qū)開始向東方向的街區(qū)在水下（而他又不會游泳），則有多少條不同的路線？解 (a) 用E表示向東步行1個街區(qū)，用N表示向北步行1個街區(qū)。因為該秘書需要向東步行9個街區(qū)，向北步行7個街區(qū)，總共步行16個街區(qū)，因此他的上班路線是多重集的排列。這樣的排列的個數(shù)為11440。(b) 若他從水下的街區(qū)走過，則他先要走到離家以東4個街區(qū)、以北3個街區(qū)的地方，再向東走一個街區(qū)，最后走到工作的大樓。他從家走到離家以東4個街區(qū)、以北3個街區(qū)的地方的路線的數(shù)目是多重集的排列數(shù)，即35。他從離家以東5個街區(qū)、以北3個街區(qū)的地方走到工作的大樓的路線的數(shù)目是多重集的排列數(shù)，即70。所以，如果他從水下的街區(qū)

7、走過，則他可能有的路線數(shù)是。因此，如果他不從水下的街區(qū)走過，則他可能有的路線數(shù)是。26. 確定多重集的10-排列的個數(shù)。解 S的有1個a ，4個b， 5個c的10-排列的個數(shù)為。S的有3個a ，2個b， 5個c的10-排列的個數(shù)為。S的有3個a ，4個b ，3個c的10-排列的個數(shù)為。S的有2個a， 3個b， 5個c的10-排列的個數(shù)為。S的有2個a， 4個b， 4個c的10-排列的個數(shù)為。S的有3個a 3個b 4個c的10-排列的個數(shù)為。S的10-排列的個數(shù)為。31. 方程有多少滿足，的整數(shù)解？解 進行變量代換：，則方程變?yōu)樵匠虧M足條件的解的個數(shù)等于新方程的非負整數(shù)解的個數(shù)。新方程的非負整

8、數(shù)解的個數(shù)為第五章作業(yè)答案8. 用二項式定理證明證明 由二項式定理知道令，得18. 求和解法1 對任意非負整數(shù)n和k，即，因此，解法2 由二項式定理知道兩邊分別求積分得所以20. 求整數(shù)a，b和c，使得對所有的m求級數(shù)的和。解 令，因為，所以。令，因為，所以。令，所以。25 應用組合學論證方法，證明二項式系數(shù)的Vandermonde卷積：對所有的正整數(shù)，和n，作為特殊情形，推導恒等式（5-11）。證明 設，則。我們可以從集合A中取出k個元素，再從集合B中取出個元素，把它們合起來構成S的有n個元素的子集。因為A的有k個元素的子集有個，因為B的有個元素的子集有個，所以S的有n個元素的子集個數(shù)為。3

9、7. 在的展開式中的系數(shù)是什么？解 由多項式定理知道令為，為，為，n為9，得到因此，的系數(shù)是42. 用牛頓二項式定理近似計算。解 第六章作業(yè)答案3. 求出從1到10000既不是完全平方數(shù)也不是完全立方數(shù)的整數(shù)個數(shù)。解 設S是從1到10000的整數(shù)的集合，是從1到10000的完全平方數(shù)的集合，是從1到10000的完全立方數(shù)的集合。因為，所以。因為，所以。因為一個整數(shù)既是完全平方數(shù)也是完全立方數(shù)的充分必要條件是它是完全六次方數(shù)，所以。從1到10000既不是完全平方數(shù)也不是完全立方數(shù)的整數(shù)個數(shù)6. 面包店出售巧克力的、肉桂的和素的炸面包圈，并在一特定時刻有6個巧克力、6個肉桂和3個素炸面包圈。如果一

10、個盒子裝12個面包圈，那么可能有多少種不同的盒裝面包圈組合？解 用a，b，c分別表示巧克力的、肉桂的和素的炸面包圈。本題要求的是多重集的12-組合的個數(shù)。設S為的所有12-組合的集合，則。設為的所有至少有7個a的12-組合的集合，為的所有至少有7個b的12-組合的集合，為的所有至少有4個c的12-組合的集合。每個的5-組合再加上7個a就得到一個至少有7個a的12-組合，所以的至少有7個a的12-組合的個數(shù)等于的5-組合的個數(shù)，。同樣可得到，。的至少有7個a和7個b的12-組合的個數(shù)，的至少有7個a和4個c的12-組合的個數(shù)，的至少有7個b和4個c的12-組合的個數(shù)，的至少有7個a、7個b和4個

11、c的12-組合的個數(shù)。因此，T的12-組合的個數(shù)9. 確定方程滿足， ， ， 的整數(shù)解的個數(shù)。解 引入新變量 則方程滿足， ， ， 的整數(shù)解的個數(shù)等于方程滿足， ， ， 的整數(shù)解的個數(shù)。設S是方程的所有非負整數(shù)解的集合，則。設為方程的所有滿足的非負整數(shù)解的集合，為方程的所有滿足的非負整數(shù)解的集合，為方程的所有滿足的非負整數(shù)解的集合，為方程的所有滿足的非負整數(shù)解的集合，則，。若，則。因此，方程滿足， ， ， 的整數(shù)解的個數(shù)24. 把六個非攻擊型車放到具有如下所述禁止位置的6行6列棋盤上的方法數(shù)是多少？(c) ×××××××&#

12、215;解 禁放位置可分成兩個“獨立”部分，左上角的部分，包含5個位置，右下角的部分，包含3個位置。用表示把k個非攻擊型車都放在禁止位置的方法數(shù)。若在部分的禁止位置放兩個非攻擊型車，則有種方法；若在部分的禁止位置放兩個非攻擊型車，則有1種方法；若在部分和部分的禁止位置各放一個非攻擊型車，則有種方法。因此，。若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分的禁止位置放三個非攻擊型車，則有1種方法。因此，。若在部分的禁止位置放三個非攻擊型車，在部分的禁止位置放一個非攻擊型車，

13、則有種方法；若在部分和部分的禁止位置各放兩個非攻擊型車，則有種方法。因此，。若在部分的禁止位置放三個非攻擊型車，在部分的禁止位置放兩個非攻擊型車，則有1種方法，。把六個非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數(shù)是26. 計算的排列的個數(shù)，其中； ； ； 以及。解 所要求的排列個數(shù)等于把六個非攻擊型車放到具有如下所述禁止位置的6行6列棋盤上的方法數(shù)。×××××××××禁放位置可分成兩個“獨立”部分，左上角的部分，包含5個位置，右下角的部分，包含4個位置。用表示把k個非攻擊型車都放在禁止位置的方法

14、數(shù)。若在部分的禁止位置放兩個非攻擊型車，則有4種方法；若在部分的禁止位置放兩個非攻擊型車，則有2種方法；若在部分和部分的禁止位置各放一個非攻擊型車，則有種方法。因此，。若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法。因此，。若在部分和部分的禁止位置各放兩個非攻擊型車，則有種方法。因此，。把六個非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數(shù)是27. 8個女孩圍坐在旋轉木馬上。她們可以有多少種方法改變座位，使得每個女孩前面的女孩都與原先的不同？解 令S為的全部個循環(huán)排列的集合

15、，為出現(xiàn)模式的循環(huán)排列的集合（），為出現(xiàn)模式的循環(huán)排列的集合。若且是集合中的不同整數(shù)，則。因此，她們可以有1625種方法改變座位。第七章作業(yè)答案1. 設表示斐波那契序列。通過用小的n值為下列每一個表達式賦值，猜測一般公式，然后用數(shù)學歸納法和斐波那契遞歸證明之。（c）（d）解 (c)對于小的n值，列出和的值如下。n 01234567801123581321001412猜測： 當時，結論成立。當時，結論成立。設且，則(d)對于小的n值，列出和的值如下。 n 0123456780112358132101261540104273714猜測：當時，結論成立。設，則14. 求解初始值，和的遞推關系，（）。

16、解 特征方程為。因為，所以是該方程的一個根。因此，一般解為（）（）（）（）解該方程組得到因此，18. 求解非齊次遞推關系 （）解 對應齊次遞推關系的特征方程為，它的特征根為4。設該非齊次遞推關系的特解為，則，因而，因此。該非齊次遞推關系的一般解為。令，得，解得。因此，。26. 求解非齊次遞推關系 （）解法一 對應齊次遞推關系的特征方程為，它的特征根為4。設該非齊次遞推關系的特解為，則，解得。該非齊次遞推關系的一般解為。令，得。因此，。解法二 該序列的生成函數(shù)。因此，。30. 確定蘋果、桔子、香蕉和梨的袋裝水果的袋數(shù)的生成函數(shù)，其中各袋要有偶數(shù)個蘋果，最多兩個桔子，3的倍數(shù)個香蕉，最多一個梨。然

17、后從該生成函數(shù)求出的公式。解 生成函數(shù)因此，。32. 令是由定義的序列（）。確定該序列的生成函數(shù)。解 兩邊求導數(shù)得到兩邊再求導數(shù)得到兩邊乘得到因此，該序列的生成函數(shù)32. 令是由定義的序列（）。確定該序列的指數(shù)生成函數(shù)。解 該序列的指數(shù)生成函數(shù)41. 確定所有的數(shù)字至少是4的n位數(shù)的個數(shù)，其中4和6每個都出現(xiàn)偶數(shù)次，5和7每個至少出現(xiàn)1次，但對于數(shù)字8和9則沒有限制。解 設為滿足條件的n位數(shù)的個數(shù)，序列的指數(shù)生成函數(shù)是因此，第八章作業(yè)答案1. 設在圓上選擇個（等間隔的）點。證明將這些點成對連接起來所得到的n條線段不相交的方法數(shù)等于第n個Catalan數(shù)。證明 設為將圓上的個點成對連接起來得到n

18、條不相交線段的方法數(shù)。我們證明序列與Catalan數(shù)序列滿足同樣的遞推關系和初始條件。設圓上的個點順時針依次排列為，若連接線段，則其左邊和右邊的點不能相互連接，那樣會與相交。左邊的點的數(shù)目和它右邊的點的數(shù)目都應當是偶數(shù)，即k是奇數(shù)。若左邊的點的數(shù)目是，則右邊的點的數(shù)目就是。隨著k從1變到，i從0變到。因此，序列滿足遞推關系令，則。由定理7.6.1知道序列滿足遞推關系因此，又有，序列與Catalan數(shù)序列滿足同樣的遞推關系和初始條件。8. 求前n個正整數(shù)的五次冪的和。解 計算序列的差分表如下。0132243102431251312117812101301805701320150390750240360120其差分表的第0條對角線為0，1，30，150，240，120，0，0，因此12. 證明第二類Stirling數(shù)滿足關系(a) ，(b) ，(c) ，(