第二章作業答案7.證明，對任意給定的52個整數，存在兩個整數，要么兩者的和能被100整除，要么兩者的差能被100整除。證明用100分別除這52個整數，得到的余數必為0,1,…,99這100個數之一。將余數是0的數分為一組，余數是1和99的數分為一組，…，余數是49和51的數分為一組，將余數是50的數分為一組。這樣，將這52個整數分成了51組。由鴿巢原理知道，存在兩個整數分在了同一組，設它們是a和b。若a和b被100除余數相同，則能被100整除。若a和b被100除余數之和是100，則能被100整除。11.一個學生有37天用來準備考試。根據過去的經驗，她知道她需要不超過60小時的學習時間。她還希望每天至少學習1小時。證明，無論她如何安排她的學習時間（不過，每天都是整數個小時），都存在連續的若干天，在此期間她恰好學習了13小時。證明設從第一天到第i天她共學習了小時。因為她每天至少學習1小時，所以和都是嚴格單調遞增序列。因為總的學習時間不超過60小時，所以，。,是1和73之間的74個整數，由鴿巢原理知道，它們中存在相同的整數，有和使得，，從第天到第i天她恰好學習了13小時。14.一只袋子裝了100個蘋果、100個香蕉、100個桔子和100個梨。如果我每分鐘從袋子里取出一個水果，那么需要多少時間我就能肯定至少已拿出了1打相同種類的水果？解由加強形式的鴿巢原理知道，如果從袋子中取出個水果，則能肯定至少已拿出12個相同種類的水果。因此，需要45分鐘。17.證明：在一群個人中，存在兩個人，他們在這群人中有相同數目的熟人（假設沒有人與他/她自己是熟人）。證明因為每個人都不是自己的熟人，所以每個人的熟人的數目是從0到的整數。若有兩個人的熟人的數目分別是0和，則有人誰都不認識，有人認識所有的人，這是不可能的。因此，這n個人的熟人的數目是個整數之一，必有兩個人有相同數目的熟人。第三章作業答案6.有多少使下列性質同時成立的大于5400的整數？(a)各位數字互異。(b)數字2和7不出現。解因為只能出現數字0,1,3,4,5,6,8,9，所以整數的位數至多為8。①考慮8位整數。最高位不能為0，因此8位整數有個。②考慮7位整數。最高位不能為0，因此8位整數有個。③考慮6位整數。最高位不能為0，因此8位整數有個。④考慮5位整數。最高位不能為0，因此8位整數有個。⑤考慮4位整數。若千位數字大于5，有個。若千位數字等于5，則百位數字必須大于等于4，有個。根據加法原理，符合條件的整數的個數為8.15人圍坐一個圓桌。如果B拒絕挨著A坐，有多少種圍坐方式？如果B只拒絕坐在A的右側，又有多少種圍坐方式？解15人圍坐一個圓桌，有種圍坐方式。若B固定坐在A的左側，則可將看作一個整體，有種圍坐方式。若B固定坐在A的右側，則可將看作一個整體，有種圍坐方式。因此，B不挨著A坐的圍坐方式有種，B不坐在A的右側的圍坐方式有種。11.從15個球員的集合中選人組成11個球員的足球隊，其中5人只能踢后衛，8人只能踢邊衛，2人既能踢后衛又能踢邊衛。假設足球隊有7個人踢邊衛4個人踢后衛，確定足球隊可能的組隊方法數。解設甲和乙既能踢后衛又能踢邊衛。若甲和乙均不入選，組隊方法數為。若甲和乙均入選，組隊方法數為++。若甲入選且乙不入選，組隊方法數為+。若乙入選且甲不入選，組隊方法數也為+。因此，組隊方法數總共為++++=112021.一位秘書在距離家以東9個街區、以北7個街區的一座大樓里工作。每天他都要步行16個街區去上班。(a)對他來說可能有多少不同的路線？(b)如果在他家以東4個街區、以北3個街區開始向東方向的街區在水下（而他又不會游泳），則有多少條不同的路線？解(a)用E表示向東步行1個街區，用N表示向北步行1個街區。因為該秘書需要向東步行9個街區，向北步行7個街區，總共步行16個街區，因此他的上班路線是多重集的排列。這樣的排列的個數為11440。(b)若他從水下的街區走過，則他先要走到離家以東4個街區、以北3個街區的地方，再向東走一個街區，最后走到工作的大樓。他從家走到離家以東4個街區、以北3個街區的地方的路線的數目是多重集的排列數，即35。他從離家以東5個街區、以北3個街區的地方走到工作的大樓的路線的數目是多重集的排列數，即70。所以，如果他從水下的街區走過，則他可能有的路線數是。因此，如果他不從水下的街區走過，則他可能有的路線數是。26.確定多重集的10-排列的個數。解S的有1個a，4個b，5個c的10-排列的個數為。S的有3個a，2個b，5個c的10-排列的個數為。S的有3個a，4個b，3個c的10-排列的個數為。S的有2個a，3個b，5個c的10-排列的個數為。S的有2個a，4個b，4個c的10-排列的個數為。S的有3個a3個b4個c的10-排列的個數為。S的10-排列的個數為。31.方程有多少滿足，，，的整數解？解進行變量代換：，，，則方程變為原方程滿足條件的解的個數等于新方程的非負整數解的個數。新方程的非負整數解的個數為第五章作業答案8.用二項式定理證明證明由二項式定理知道令，得18.求和解法1對任意非負整數n和k，，即，因此，解法2由二項式定理知道兩邊分別求積分得所以20.求整數a，b和c，使得對所有的m求級數的和。解令，，因為，所以。令，，因為，所以。令，，所以。25．應用組合學論證方法，證明二項式系數的Vandermonde卷積：對所有的正整數，和n，作為特殊情形，推導恒等式（5-11）。證明設，，，，則。我們可以從集合A中取出k個元素，再從集合B中取出個元素，把它們合起來構成S的有n個元素的子集。因為A的有k個元素的子集有個，因為B的有個元素的子集有個，所以S的有n個元素的子集個數為。37.在的展開式中的系數是什么？解由多項式定理知道令為，為，為，n為9，得到因此，的系數是42.用牛頓二項式定理近似計算。解第六章作業答案3.求出從1到10000既不是完全平方數也不是完全立方數的整數個數。解設S是從1到10000的整數的集合，是從1到10000的完全平方數的集合，是從1到10000的完全立方數的集合。因為，所以。因為，所以。因為一個整數既是完全平方數也是完全立方數的充分必要條件是它是完全六次方數，，所以。從1到10000既不是完全平方數也不是完全立方數的整數個數6.面包店出售巧克力的、肉桂的和素的炸面包圈，并在一特定時刻有6個巧克力、6個肉桂和3個素炸面包圈。如果一個盒子裝12個面包圈，那么可能有多少種不同的盒裝面包圈組合？解用a，b，c分別表示巧克力的、肉桂的和素的炸面包圈。本題要求的是多重集的12-組合的個數。設S為的所有12-組合的集合，則。設為的所有至少有7個a的12-組合的集合，為的所有至少有7個b的12-組合的集合，為的所有至少有4個c的12-組合的集合。每個的5-組合再加上7個a就得到一個至少有7個a的12-組合，所以的至少有7個a的12-組合的個數等于的5-組合的個數，。同樣可得到，。的至少有7個a和7個b的12-組合的個數，的至少有7個a和4個c的12-組合的個數，的至少有7個b和4個c的12-組合的個數，的至少有7個a、7個b和4個c的12-組合的個數。因此，T的12-組合的個數9.確定方程滿足，，，的整數解的個數。解引入新變量則方程滿足，，，的整數解的個數等于方程滿足，，，的整數解的個數。設S是方程的所有非負整數解的集合，則。設為方程的所有滿足的非負整數解的集合，為方程的所有滿足的非負整數解的集合，為方程的所有滿足的非負整數解的集合，為方程的所有滿足的非負整數解的集合，則，，。若，則。因此，方程滿足，，，的整數解的個數24.把六個非攻擊型車放到具有如下所述禁止位置的6行6列棋盤上的方法數是多少？(c)××××××××解禁放位置可分成兩個“獨立”部分，左上角的部分，包含5個位置，右下角的部分，包含3個位置。用表示把k個非攻擊型車都放在禁止位置的方法數。。若在部分的禁止位置放兩個非攻擊型車，則有種方法；若在部分的禁止位置放兩個非攻擊型車，則有1種方法；若在部分和部分的禁止位置各放一個非攻擊型車，則有種方法。因此，。若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分的禁止位置放三個非攻擊型車，則有1種方法。因此，。若在部分的禁止位置放三個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分和部分的禁止位置各放兩個非攻擊型車，則有種方法。因此，。若在部分的禁止位置放三個非攻擊型車，在部分的禁止位置放兩個非攻擊型車，則有1種方法，。把六個非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數是26.計算的排列的個數，其中；；；以及。解所要求的排列個數等于把六個非攻擊型車放到具有如下所述禁止位置的6行6列棋盤上的方法數。×××××××××禁放位置可分成兩個“獨立”部分，左上角的部分，包含5個位置，右下角的部分，包含4個位置。用表示把k個非攻擊型車都放在禁止位置的方法數。。若在部分的禁止位置放兩個非攻擊型車，則有4種方法；若在部分的禁止位置放兩個非攻擊型車，則有2種方法；若在部分和部分的禁止位置各放一個非攻擊型車，則有種方法。因此，。若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法；若在部分的禁止位置放兩個非攻擊型車，在部分的禁止位置放一個非攻擊型車，則有種方法。因此，。若在部分和部分的禁止位置各放兩個非攻擊型車，則有種方法。因此，。。把六個非攻擊型車放到具有上述禁止位置的6行6列棋盤上的方法數是27.8個女孩圍坐在旋轉木馬上。她們可以有多少種方法改變座位，使得每個女孩前面的女孩都與原先的不同？解令S為的全部個循環排列的集合，為出現模式的循環排列的集合（），為出現模式的循環排列的集合。若且是集合中的不同整數，則。。因此，她們可以有1625種方法改變座位。第七章作業答案1.設表示斐波那契序列。通過用小的n值為下列每一個表達式賦值，猜測一般公式，然后用數學歸納法和斐波那契遞歸證明之。（c）（d）解(c) 對于小的n值，列出和的值如下。n0 1 2 3 4 5 6 7 80 1 1 2 3 5 8 13 210 0 1 4 12猜測：當時，，結論成立。當時，，結論成立。設且，則(d) 對于小的n值，列出和的值如下。n0 1 2 3 4 5 6 7 80 1 1 2 3 5 8 13 210 1 2 6 15 40 104 273 714猜測：當時，，結論成立。設，則14.求解初始值，，和的遞推關系，（）。解特征方程為。因為，所以是該方程的一個根。因此，一般解為（） （） （） （） 解該方程組得到 因此，18.求解非齊次遞推關系（）解對應齊次遞推關系的特征方程為，它的特征根為4。設該非齊次遞推關系的特解為，則，因而，因此。該非齊次遞推關系的一般解為。令，得，解得。因此，。26.求解非齊次遞推關系（）解法一對應齊次遞推關系的特征方程為，它的特征根為4。設該非齊次遞推關系的特解為，則，解得。該非齊次遞推關系的一般解為。令，得。因此，。解法二該序列的生成函數。因此，。30.確定蘋果、桔子、香蕉和梨的袋裝水果的袋數的生成函數，其中各袋要有偶數個蘋果，最多兩個桔子，3的倍數個香蕉，最多一個梨。然后從該生成函數求出的公式。解生成函數因此，。32.令是由定義的序列（）。確定該序列的生成函數。解兩邊求導數得到 兩邊再求導數得到 兩邊乘得到 因此，該序列的生成函數32.令是由定義的序列（）。確定該序列的指數生成函數。解該序列的指數生成函數41.確定所有的數字至少是4的n位數的個數，其中4和6每個都出現偶數次，5和7每個至少出現1次，但對于數字8和9則沒有限制。解設為滿足條件的n位數的個數，序列的指數生成函數是 因此，第八章作業答案1.設在圓上選擇個（等間隔的）點。證明將這些點成對連接起來所得到的n條線段不相交的方法數等于第n個Catalan數。證明設為將圓上的個點成對連接起來得到n條不相交線段的方法數。我們證明序列與Catalan數序列滿足同樣的遞推關系和初始條件。設圓上的個點順時針依次排列為，若連接線段，則其左邊和右邊的點不能相互連接，那樣會與相交。左邊的點的數目和它右邊的點的數目都應當是偶數，即k是奇數。若左邊的點的數目是，則右邊的點的數目就是。隨著k從1變到，i從0變到。因此，序列滿足遞推關系令，則。由定理7.6.1知道序列滿足遞推關系因此，又有，序列與Catalan數序列滿足同樣的遞推關系和初始條件。8.求前n個正整數的五次冪的和。解計算序列的差分表如下。0 1 32 243 1024 3125 … 1 31 211 781 2101 … 30 180 570 1320 … 150 390 750 … 240 360 … 120 …其差分表的第0條對角線為0，1，30，150，240，120，0，0，…因此12.證明第二類Stirling數滿足關系(a)，(b)