组合数学作业答案.doc

第二章作业答案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个a 3个b 4个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值，列出和的值如下。n 01234567801123581321001412猜测： 当时，结论成立。当时，结论成立。设且，则(d)对于小的n值，列出和的值如下。 n 0123456780112358132101261540104273714猜测：当时，结论成立。设，则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个正整数的五次幂的和。解 计算序列的差分表如下。0132243102431251312117812101301805701320150390750240360120其差分表的第0条对角线为0，1，30，150，240，120，0，0，因此12. 证明第二类Stirling数满足关系(a) ，(b) ，(c) ，(d) ，证明 (a) 设，因为将个物体放入1个盒子中，只有一种方法，所以。(b) 设，A是n-元集，则A的非空真子集的个数为。任取A的非空真子集B，将B中元素放入一个盒子，而将其他元素放入另一个盒子，就得到一种将A中元素放入两个非空盒子的方法。显然，B和它的补集对应同一种方法，即每种方法都对应A的两个子集。因此，。(c) 设。若，则。下面考虑的情况。将n个物体放入个非空盒子中，必然有一个盒子中有两个物体，而其余盒子中只有一个物体。设A是n-元集，任取A的2-组合B，将B中元素放入一个盒子，将其余元素各放进一个盒子，就得到将n个物体放入个非空盒子中的方法。因此，可在A的2-组合和将n个物体放入个非空盒子中的方法之间建立一一对应。所以，。(d) 设。若，。下面考虑的情况。将n个物体放入个非空盒子中，有两种可能。一种情况是，有一个盒子中放入3个物体，其余盒子中各放入一个物体，这种情况发生的次数是。另一种情况是，有两个盒子中各放入2个物体，其余盒子中各放入一个物体。从这n个物体中任取出四个，设它们是，a可与之一在一个盒子中。因此，这种情况发生的次数是。所以，。13. 令X是p-元集并令Y是k-元集。证明，把X映射到Y上的函数的个数等于证明 设。将看作k个不同盒子，若，则把X中元素x放入盒子，这在X映射到Y上的函数和将X中元素放入k个不同非空盒子的方法之间建立了一一对应。因此，把X映射到Y上的函数的个数等于。