组合

第1章 排列与组合 经过勘误和调整，已经消除了全部的文字错误，不过仍有以下几个题目暂时没有找到解答： 1.8 1.9 1.16 1.41（答案略） 1.42（答案略） 1.1 从{1,2,…,50}中找一双数{a,b}，使其满足： [解] (a) 将上式分解，得到 a = b–5，a=0时，b＝5，6，7，…,50。满足a=b-5的点共50-4=46个点. a = b+5，a=5时，b＝0，1，2，…,45。满足a=b+5的点共45-0+1=46个点. 所以，共计 个点. (b) 。 1.2 5个女生，7个男生进行排列， (a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？ (c) 两男生A和B之间正好有3个女生的排列是多少？ [解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。 （7＋1）!×5!=8!×5!＝40320×120=4838400 (b) 先将男生排列有7!种，共有8个空隙，将5个女生插入，故需从8个空 中选5个空隙，有 种选择。将女生插入，有5!种方案。故按乘法原理，有： 7!× ×5!=33868800(种)方案。 (c) 先从5个女生中选3个女生放入A，B之间，有 种方案，在让3个女生 排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有 (7+1)! = 8! 由于A，B可交换，如图 **A***B** 或 **B***A** 故按乘法原理，有： 2× ×3!×8!=4838400（种） 1.3 m个男生，n个女生，排成一行，其中m，n都是正整数，若 (a) 男生不相邻(m≤n+1)； (b) n个女生形成一个整体； (c) 男生A和女生B排在一起； 分别讨论有多少种方案. [解] (a) 先将n个女生排列，有n!种方法，共有n+1个空隙，选出m个空隙，共有 种方法，再插入男生，有m!种方法，按乘法原理，有： n!× ×m!＝n!× ×m!= 种方案。 (b) n个女生形成一个整体，看作一个人，与m个男生做重排列，然后，n个女生内部再作排列，按乘法原理，有(m+1)!×n!种方案。 (c) 男生A和女生B排在一起，看作一人，和其余n-1+m-1=n+m-2个人一起，作排列，共有(n+m-2+1)=(n+m-1)!种方法，A，B两人内部交换，故有2×(n+m-1)!种方案。 1.4 26个英文字母进行排列，要求x和y之间有5个字母的排列数. [解] 选入26－2＝24个字母中选取5个字母，有 种方法，5个字母内部排列，有5!种方案，再将X*****Y这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X与Y可交换，故按乘法原理，有： 2× ×5!×20!=2× ×5!×20!=40×24! ≈ 40× × 又因为：ln40+0.5(lg +lg48)+24(lg24–lge) ≈1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481) =25.39325777 所以，结果为 ＝2.473191664× 1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字. [解] 3000~8000中各位不同的奇数，分类讨论： 首位3，1×8×7×4（末位不能取3） 首位4，1×8×7×5（末位全取） 首位5，1×8×7×4 首位6，1×8×7×5 首位7，1×8×7×4 从而，由加法原理，得： 8×7×（4＋5＋4＋5＋4）=56×22＝1232个。 1.6 计算 [解] (参见p14) 1.7 试证 被2n除尽. [证] 故能被 整除。 1.8 求1040和2030的公因数. [解] 1.9 试证n2的正除数的数目是奇数. [解] 1.10 证明任一正整数n可惟一地示成如下形式： [证].(1)可表示性： 令M={(am-1,am-2,,a2,a1):0aii，i=1,2,,m-1}，显然M=m!； N={0,1,2,,m!-1}，显然N=m!，其中m是大于n的任意整数。 定义函数f : MN f(am-1,am-2,,a2,a1)=am-1(m-1)!+am-2(m-1)!++a22!+a11! (*) 显然，0= 0(m-1)!+0(m-1)!++02!+01! am-1(m-1)!+am-2(m-1)!++a22!+a11! (m-1)(m-1)!+(m-2)(m-1)!++22!+11! = m!-1 （见P14） 即0 f(am-1,am-2,,a2,a1)m!-1 由于f是用普通乘法和普通加法所定义的，故从而f无歧义。从而有一确定的数K（0Km!-1），使 K=f(am-1,am-2,,a2,a1) 为证N中的任一数均可表示成上边(*)的形式，只要证明f是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f是单射函数即可。 否则，设存在某数K0N,有(am-1,am-2,,a2,a1)(bm-1,bm-2,,b2,b1)均属于M，使 K0=f(am-1,am-2,,a2,a1)且K0=f(bm-1,bm-2,,b2,b1) 由于不相等,故必有某个j(m-1)，使ajbj。不妨设这个j是第一个不使相等的，即ai=bi ，ajbj且ajbj，从而由 am-1(m-1)!+am-2(m-1)!++a22!+a11!= bm-1(m-1)!+bm-2(m-1)!++b22!+b11! 就可有 (bj-aj)j!+(bj-1-aj-1)(j-1)!++(b2-a2)2!+(b2-a1)1!=0 但是 (bj-aj)j!+(bj-1-aj-1)(j-1)!++(b2-a2)2!+(b2-a1)1! (bj-aj)j!-[bj-1-aj-1(j-1)!++b2-a22!+b2-a11!] j!-[(j-1)(j-1)!++22!+11!] =j!-(j!-1) =1 矛盾，这说明f是单射函数。 由于M=N=m!有限，故f是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由nN，都有(am-1,am-2,,a2,a1)M，使得 n=am-1(m-1)!+am-2(m-1)!++a22!+a11! 这就证明了任何n可表示成以上形式。 (2)唯一性： 用证明单射的方法，就可以证明表示法的唯一性(表示方法见 P14)，留给读者。 1.11 证明 ，并给予组合解释. [证].(参见 P28 (1-8-4)) 组合意义：（等式右边）由n个元素中取出r+1个元素组合（有C(n,r+1)种），再从每个组合中取出1个（有r+1种），全部结果为C(n,r+1)(r+1)。（等式左边）由此所得的全部结果相当于从n个元素中直接取1个元素（有n种），但有重复，其重复数等于剩下的n-1个元素中取r个元素的组合C(n-1,r)，故nC(n-1,r)= (r+1)C(n,r+1)。 1.12 试证等式： [证].证法一：根据二项式定理，(参见 P29 (1-8-5)) (1+x)n=1+C(n,1)x+C(n,2)x2++ xn 两边对 求导，有 n(1+x)n-1=C(n,1)+2C(n,2)x++ nxn-1 令x=1，即得 。 证法二： 组合意义：设有n个不同的小球，并有A、B两个合子，A合中恰好放入一个球，B合中可放入任意多个球。有两种放球方法： (1)（等式左边）先从n个球中选取k个，再从这k个球中任选一个放入A合，剩下的k-1个球全部放入B合中，方案数共为 ； (2)（等式右边）先从n个球中任选一个放入A合，剩下的n-1个球每个都有两种可能，要么放入B合，要么不放，方案数共为n2n-1； 显然，两种放球方法等效，两种放球方案数相等，即 。 1.13 有n个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数. [解] 设这n个不同的数为 。 若假定第一组取k1个数，第二组取k2个数，并且令m=k1+k2(m2)，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n个数中任选m个数(有C(n,m)种选法)，再从这m个数中从大到小取k1个数作为第一组数(有k1=1,2,,m-1共m-1种取法)，将其余k2个数作为第二组数，即可。故总方案数为 （参见第3题等式）。 1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少种方案？ [解] 第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,……。 即方案数为132211=12。 1.15 试求从1到1 000 000的整数中，0出现的次数. [解] (参见P8)从1到1 000 000的整数中，0出现的次数相当于10-99，100-999，1000-9999, 10000-99999,100000-999999,以及1 000 000中的0的个数。 10-99中的零的个数为： 100-999中的零的个数为： 1000-9999中的零的个数为： =27+486+2 187 =2 700 10000-99999中的零的个数为： =36+972+8 748+26 244 =36 000 100000-99999中的零的个数为： =45+1 620+21 870+131 220+295 245 =450 000 1，000，000中的0的个数为： 6 故1到1，000，000的整数中0的个数为： 9+180+2 700+36 000+450 000+6=488 895。 1.16 n个完全一样的球放到r个有标志的盒（n≥r）中，无一空盒，试问有多少种方案？ [解] 1.17 n和r都是正整数，而且r≤n，试证下列等式： [解] (a) 方法一 方法二（组合意义） 等式左边：从n个元素种取r个元素做排列有 种，就是等式左边； 等式右边：先从n个元素中拿出一个元素排在首位，有n种方法，然后再从剩下的n-1个元素中取r-1个元素做后面r-1位的排列，有 种方法，按乘法原理，共有n 种方法。 (b) 方法一 方法二（组合意义法） 等式左边：从n个元素中取r个元素做r位排列，有 种方案。 等式右边：先从n个元素中取r-1个元素做r-1位排列，有 种方法；再从剩下的n-r+1个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有 (c) 方法一 方法二：（组合意义法） 等式左边：从n个元素中取r个元素做r位排列，其方案数为 ； 等式右边：从n个元素中先取出一个元素放在第一位，有n种方法，再从剩下的n-1个元素种取出r个元素放在第2位，…，第r位，第r+1位，有 种方法，这样就多了一位，故应除去第r+1位的选取方法，共有n-r种选法，故总方案为 。 (d) 方法一 方法二：（组合意义） 等式左边：从n+1个不同的元素中取r个元素进行r位排列。其方案为 ； 等式右边：(a) 不取某特定元素b，则r个元素需从剩下的n个元素中取，然后做r位排列，共有 种方案。 (b) 取定某特定元素b，则其余r-1个元素需从剩下的n个元素中取，先做r-1位排列，共有 种方法，再将特定元素b插入这r-1个元素形成的r个空隙中，有r种方法，故按乘法原理，共有r 种方案。 (e) 方法一 （根据(d)可得） 方法二：组合意义（同样根据d） 等式左边：从n+1个不同元素取r个元素做r位排列，其方案数为： 等式右边：设 是n-r+1个特定元素。 (a) 不取特定元素 ，剩下的r个元素做全排列，有 =r!种方案。 (b)(1)：取特定元素 ，但不取特定元素 ，于是先在剩下的r个元素中取r-1个元素做排列，有 种方法，然后将 插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r 种方案。 (2)：取特定元素 ，但不取特定元素 ，于是先在剩下的r+1个元素中取r-1个元素做排列，有 种方法，然后，将 插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r 种方案。 …… (n-r)：取特定元素 ，但不取特定元素 ，于是先在剩下的n-1个元素中取r-1个元素做排列，有 种方法，然后，将 插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r 种方案。 (n-r+1）：取特定元素 ，先在剩下的n个元素中取r-1个元素做排列，有 种方法，然后，将 插入这r-1个元素的r个空隙，共有r种方法，故按乘法原理，有r 种方案。 最后，按加法原理，共有： 1.18 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？ [解] 先将5个球进行全排列，有5!种方法，再将三个空格插入5个球的6个空隙中，有 种方法，然后将这/////////////////////////////////////////////////////////元素的排列一对一的放入8个盒子中，即完成了每盒最多一球，空盒不相邻的放球要求，总方案有： （种） 1.19 n+m位由m个0，n个1组成符号串，其中n≤m+1，试问不存在两个1相邻的符号串的数目。 [解]：先将m个0排成一排，再将n个1插入m个0的m+1个空隙（因为n≤m+1,这可实现）,就得到了无相邻的n+m位0-1符号串，其方案数为 。 1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位.试问有多少种方案？ [解] 甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2，至多为4。 1.21 一个盒子里有7个无区别的白球，5个无区别的黑球. 每次从中随机取走一个球，已知前面取走6个，其中3个是白的. 试问取第6个球是白球的概率. [解] 已知前面取走6个球，有3个白球，则有3个黑球。 故总的取球方案是 ； 第六个球是白球的方案是 因此取出第6个球是白球的概率 1.22 求下图中从0到P的路径数： (a) 路径必须过A点； (b) 路径必须过道路AB； (c) 路径必须过A和C； (d) 道路AB封锁（但A，B两点开放）. [解] O(0,0), A(3,2), B(4,2), P(8,5), C(6,3) (a) 路分为两段：先从O到A，再从A到P，则有： (b)路分为三段：先从O到A，再从A到B；再从A到B；然后从B到P； (c) 路分为三段：先从O到A；再从A到C；然后从C到P； (d) (采用排除法) 从O到P的满足不过AB的路 ＝ 从O到P的路－从O到P经过AB的路，因此： 1.23 另s={1,2,3…,n+1},n≥2 ，试证： [证] 而 ，故 1.24 A={(a, b)|a, b∈Z, 0≤a≤9,0≤b≤5} (a) 求x-y平面上以A作顶点的长方形的数目. (b) 求x-y平面上以A作顶点的正方形数目. [解] (a) 先选定横作标，再选定纵坐标，其方案数为： (b) 求x－y平面上以A作顶点的正方形数目。 按边长分类： 边长为1的正方形：9×5＝45 边长为2的正方形：(9-1)×(5-1)=32 边长为3的正方形：(9-2)×(5-2)=21 边长为4的正方形：(9-3)×(5-3)=12 边长为5的正方形：(9-4)×(5-1)=5 故总的以x－y平面上A点作顶点的正方形的数目，按加法原理可得数目为115. 1.25 平面上有15个点P1, P2, … , P15，其中P1, P2, P3, P4, P5共线，此外不存在3点共线的. (a) 求至少过15个点中两点的直线的数目. (b) 求由15个点中3点组成的三角形的数目. [解] (a) (采用排除法) 至少过15个点中两点的直线数目＝在15个点中任选2个点将有一条直线－从 ～ 中选2点构成直线＋ ～ 所在的直线l (b) (采用排除法) 由15个点中3点组成的三角形的数目＝任在15个点中取3点构成三角形的数目－在5个点 ～ 中取3点构成的“三角形”的数目 1.26 S={1, 2, … , 1000}，a，b∈S，使ab≡0 mod 5，求数偶{a, b}的数目. [解] 因为 所以 ab＝5k （k是整数） 1≤a≤1000, 1≤b≤1000 1≤ab≤1000000 1≤5k≤1000000 1≤k≤200000 所以满足 且1≤a,b≤1000的{a,b}的数目为200000 1.27 6位男宾，5位女宾围一圆桌而坐 (a) 女宾不相邻有多少种方案？ (b) 所有女宾在一起有多少种方案？ (c) 一女宾A和两位男宾相邻又有多少种方案？ [解] (a) 先将6位男宾作圆排列有 在将5位女宾插入6个空格，每格一人，共有6×5×4×3×2×1＝720 按乘法原理：有120×720＝86400 (b) 5位女宾在一起，可看作一人，与6位男宾一起，先做圆排列，有 =6!=720 然后5位女宾内部作线排列，有5!＝120。 所以，总方案为：720×120＝86400 (c) 先将6个男宾做圆排列，共有 =120种方法。 再将女宾A随便插入6个空格中的一个，有6种方法。 然后将剩下的4个女宾插入5个空格中，但每个空格不限人数，故相当于将4个有区别的球放入5个不同的盒子中的放球方案(可重组合)，共有 =5×6×7×8＝1680。 所以，按乘法原理，有120×6×1680＝1209600种方案。 1.28 k和n都是正整数，kn位来宾围着k张圆桌而坐，试求其方案数. [解] 先将k×n个来宾分成k堆，每堆n个人，有 再将每堆n个人做圆排列，有 ＝(n-1)!,共有 种方法。 故按乘法原理，有 1.29 从n个对象中取r个作圆排列，求其方案数目. 已知1≤r≤n. [解] 每一个r个人围成的圈（圆排列） 即每一个r圈相当于r个r排列。故不同的方案数为 若不计顺逆方向，则为 。 1.30 试证下列等式 [证] (a) 方法一 方法二：组合意义法： 一方面，从n个元素中取出r个元素，然后再做排列，故按乘法原理，其数目为 另一方面：先从n个元素中取出1个元素，排在第一位，再从剩下的n-1个元素中取出r-1个元素，并将这r-1个元素排在第2～r位，故按乘法原理，其方案数为 这两方面的组合意义相同，故有 因此，有： (b) 方法一 方法二：组合意义 一方面：从n个元素中取出r个元素来，然后，在做排列，故按乘法原理，其方案数为 另一方面：先从n个元素中先取出r-1个元素，将其排排列再第1～r-1位，再从剩下的n-r+1个元素中取出1个元素排在第r位。故按乘法原理，其方案数为： ； 这两方面的组合意义相同，故有 ＝ 所以，有： (c) 方法一 方法二：组合意义 一方面，从n个元素中取出n-r个元素，然后再做排列，按乘法原理，其方案数为： 另一方面，选从n个元素中取出1个元素排再第一位，再从剩下的n-1个元素中选取n-r+1个元素，排在第2～n-r位。故按乘法原理，其方案数为 这两方面的组合意义相同，可得： 故有： 1.31 试证任意r个相邻数的连乘： 被r！除尽. [证] 由于 是从n+r个元素中选取r个元素的组合数，故当然是整数，因此，(n+1)(n+2)…(n+r)可以整除r!，其商为组合数 。 1.32 在a, b, c, d, e, f, x, x, x, y, y的排列中，要求y必须夹在两个x之间，问这样的排列数等于多少？ [解] 由于y必须乘在两个x之间，故两个y只能夹在仅有的三个x之间，形成图象xyxyx，形成6个空档。其余的6个元素a,b,c,d,e,y,只能放在这6个空格处，这相当于将6个不同的小球放入6个不同的盒子中，允许空盒，且盒内还要排列的方案数。故： 1.33 已知r, n, k都是正整数，r≥nk，将r个无区别的球放在n个有标志的盒子里，每盒至少k个球，试问有多少种方案？ [解] 先将nk个球放入n个有标志的盒中，每盒k个球，其方案为1。 再将剩下的r-nk个球放入这n个盒中，每盒球数不限，其方案数为 故总的方案为 1.34 在r, s, t, u, v, w, x, y, z的排列中求y居x和z中间的排列数. [解] 由于y必须居于x和z之间，故形成图象xyz，形成4个空格。其余r,s,t,u,v,w这6个元素，只能放在这4个空格处，这相当于将6个不同的小球放入4个不同的盒子中，允许空盒，且盒内还要进行排列的方案数。故有： 方法2： 将9个字母进行全排列，有9!中排列，而x,y,z这3个字母形成的3!个排列只看作一种排列xyz，故有： 1.35 凸十边形的任意三条对角线不共点. 试求这凸十边形的对角线交于多少个点？ [解] 从一个顶点可引出7条线和第一条（从右到左）交的有17，和第二条交的有26条 故和一个顶点引出的7条线相交的点为： 17+26+35+44+53+62+71=84 故和从10点引出的对角线交的点有个8410=840，但每个点重复了四次（因为每个点在两条线上，而每条线有两个端点）。故凸10 边形（这样的）对角线交于 个点。 故也可为 1.36 试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整数. [证] “必要性”。若整数n是另一个整数的平方，则n一定可写成如下形式： （参见P7例4） 其中P1,P2,,Pe是e个不同的素数。由于第9题可得，除尽n的正整数数目为 (21+1)(22+1)(2e+1)为奇数。 “充分性”。若除尽正整数n的正整数的数目为奇数。则n一定是某个正整数的平方，否则，n不是平方数，则n一定是可分解成如下形式： 其中P1,P2,,Pe是e个不同的素数，且1,2,,e中至少有一个奇数（否则n为平方数）。于是(21+1)(22+1)(2e+1)必为偶数，与充分性假设矛盾。 1.37 给出 的组合意义. [证] 组合意义一： 从(n+r+1)个元素{1,2,,n+r+1}中取出 个元素i1i2irir+2ir+2 in+r+1-m 的个数是 。其中第r+1个位置上的元素ir+1可取r+1,r+2,,r+1+m。 当ir+1取(r+1+k)时(k=0,1,2,,m)，前边r个数i1,i2,,ir可在{1,2,,r+1+(k-1)}这(r+k)个数里取，故有 种取法；后边[(n+r+1-m)-(r+1)]=n-m个数ir+2,,in+r+1-m可在{r+1+k+1, ,n+r+1}这[(n+r+1)-(r+1+k)]=n-k个数中取，故有 。根据乘法原理，当ir+1=r+1+k时，这样的组合数为 。根据加法原理，对k=0,1,2,,m作和，就有 。 注：参见《 Combinatorial Problems and Exercise》 by L.Lovasz 0143.7 L896c P18-42 (i) P96 P172 (i)The number of those(n+r+1-m)-tuples of{1,2,,n+r+1}Whose element is r+k+1is . Summing for k=0,1,2,,m,we get the result. 组合意义二：（格路方法） 等式左端：从点A(-r-1,0)到点C(-1,k)(k=0,1,2,,m)直接经过点D(0,k)再到点B(n-m,m)的路径数(参见本题图1)； 等式右端：从点A(-r-1,0)到点B(n-m,m)的路径数。 1.38 给出 的组合意义. [证].组合意义一： 等式右端是从n+r+1个元素 中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P25等式3的组合意义)： (1) r+1个元素的组合中含有 的，相当于从n个元素 中取r个组合，其组合数为 （即A）。 (2)r+1个元素的组合中不含有 ，但又含有元素 的。即一个(r-1)-组合。依 来分，不外乎含 和不含 ；不含 的又依 分，不外乎含 和不含 。不含 而含 的组合，相当于从n-1个元素 中取r个元素的组合，然后加上 而成，其组合数为 。 (3)r+1个元素的组合中不含 和 ，但含有元素 的。即不含 的依 来分，不外乎含 和不含 。不含 而含 的组合，相当于从n-2个元素 中取出r个元素的组合，然后再加上 而成，其组合数为 。 取出的r+1个组合元素中不含 ，但含有元素 的。即不含 的，又依 来分，不外乎含有 和不含有 。不含 而含 的组合，相当于从n-(n-r-1)=r+1个元素 中取出r个元素的组合而加上 而成，其组合数为 。 (4)由 组成的(r+1)-组合的组合数为 。而且 组合意义二： 等式右端：从n+1个不同元素a1,a2,,an,an+1,中任选r+1个元素的组合方案数； 等式左端：从n+1个不同元素a1,a2,,an,an+1,中选取r+1个元素，一定选元素ar+k+1(k=0,1,2,,n-r)，但是不选元素ar+k+2,,an,an+1的组合方案数。 1.39 证明 [证].借助P28等式4，可知： (nr) (r=0,1,2,,n) 从而有 (用了P29等式5) 组合意义一： 等式右端可看作从m个元素中取出n个元素进行组合。然后对这取出的n个元素进行染色（红，白）的所有方案，它为 ； 等式左端可看作先从m个元素中取出k个元素（个数为 ），全部染以红色。再从剩下的(m-k)个元素中取出(n-k)个元素（个数为 ），全部染以白色。根据乘法原理，从m个元素中取出n个元素，k个染上红色，(n-k)个染上白色的方案数为 ，k=0,1,2,,n； 而从m个元素中取出n个元素染以红白两色的方案可分解成有0个，1个，…，n个染以红色的总和。故根据加法原理，17题成立。 组合意义二： 等式右端：将从m个不同的小球中任意选出的n个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数； 等式左端：先从m个球中任选k个球放入第一个合子里(k=0,1,2,,n)，再从剩下的m-k个球中任选n-k个球放入第二个合子里，然后对k从0到n求和，就得到了所有可能的放球方案数。 1.40 从n个人中选r个围成一个圆圈，问有多少种不同的方案？ [解].每一个r个人围成的圈（圆排列） 即每一个r圈相当于r个r排列。故不同的方案数为 若不计顺逆方向，则为 。 1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列的算法. [解].（略） 1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法. (b) 写出按照邻位对换法由给定排列生成其下一个排列的算法. [解].（略） 1.43 对于给定的正整数n，证明，当 时，C(n,k)的最大值. [证] 取C(n,k)与C(n,k-1)进行比较。C(n,k)/C(n,k-1)=(n-k+1)/k。 当kn/2时，(n-k+1)/k1，即C(n,k)C(n,k-1)； 当kn/2时，(n-k+1)/k1，即C(n,k)C(n,k-1)； 因此，得到当k=n/2或最接近n/2时，C(n,k)取得最大值。 1.44 (a) 用组合方法证明 和 都是整数. (b) 证明 是整数. [证] (a)考虑2n个不同的球放入n个不同的合子里，每合两个的方案数。这个方案数应该是整数。 对2n个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n个合子内部的排列共重复计算了2n次，故总的重复因子是2n。因此，把2n个不同的球放入n个不同的合子里，每合两个的方案数是 。所以， 是整数。 同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。 对3n个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=23。n个合子内部的排列共重复计算了2n3n次，故总的重复因子是2n3n。因此，把3n个不同的球放入n个不同的合子里，每合3个的方案数是 。所以， 是整数。 (b)考虑n2个不同的球放入n个相同的合子里，每合n个的方案数。这个方案数应该是整数。 对n2个球进行排列的方案数为(n2)!。而把n个球放入同一个合子里不计顺序，重复因子是n!。n个合子内部的排列共重复计算了(n!)n次，故重复因子是(n!)n。另外，由于n个合子相同，放入不同的合子是没有区别的，其重复因子是n!。故此，总的重复因子是(n!)n+1。因此，把n2个不同的球放入n个相同的合子里，每合n个的方案数是 。所以， 是整数。 1.45 (a) 在2n个球中，有n个相同. 求从这2n个球中选取n个的方案数. (b) 在3n+1个球中，有n个相同. 求从这3n+1个球中选取n个的方案数. [解] (a)相当于从n个不同的小球中取出m个小球(0mn),再从n个相同的小球中取出n-m个小球，m=0,1,2,,n的方案数。 根据加法原理，这个方案数应该是：C(n,0)+ C(n,1)++ C(n,n)=2n。 同理，考虑3n个不同的球放入n个不同的合子里，每合3个的方案数。这个方案数应该是整数。 (b)相当于从2n+1个不同的小球中取出m个小球(0mn),再从n个相同的小球中取出n-m个小球，m=0,1,2,,n的方案数。 根据加法原理，这个方案数应该是：C(2n+1,0)+ C(2n+1,1)++ C(2n+1,n)。 1.46 证明在由字母表{0, 1, 2}生成的长度为n的字符串中 (a) 0出现偶数次的字符串有 个； (b) [证] (a)方法一：采用（串值）数学归纳法 ［基始］当n=1时，0出现偶数次，长度为1的字符串有 =2个（即1和2两个长度为1的字符串）。所证结论成立； ［归纳假设］当n=m(1mk)时，假设所证结论成立。即，0出现偶数次，长度为m的字符串有 个； ［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分： (1)给0出现偶数次，长度为k的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有 2=3k+1个； (2)给0出现奇数次，长度为k的字符串后面再增加一位是0的数，因此，按乘法原理，由归纳假设，此种字符串有 1= 个； 所以，按加法原理，0出现偶数次，长度为k+1的字符串共有 (3k+1)+ = 个。所证结论成立； 归纳完毕。 方法二：采用指数型母函数方法 设：an—0出现偶数次，长度为n的字符串的个数，则{an}的指数型母函数 所以， （规定a0=1）。 (b)利用组合意义法来证 考虑0出现偶数次，长度为n的字符串的个数。根据上面(a)，已证其个数为 ； 另一方面，相当于先从n个位置中选取2m(02mn)个（有 种选择）放置上数0,再在剩下的n-2m个位置上放置数1或2（有2n-2m种放法），按乘法原理，是 个，m=0,1,2,,q ( )的方案数。 按加法原理，此方案数为 。因此，我们有 。 1.47 5台教学机器m个学生使用.使用第1台和第2台的人数相等，有多少种分配方案？ [解] 先从m个学生中选取k个使用第1台机器，再从剩下的m-k个学生中选取k个使用第2台机器，其余m-2k个学生可以任意使用剩下的3台机器，按乘法原理，其组合数为C(m,k) C(m-k,k)3(m-2k)。这里k=0,1,2,,q ( )，于是，按加法原理，共有 种使用方案。 1.48 在由n个0及n个1构成的字符串中，在任意前k个字符中，0的个数不少于1的个数的字符串有多少？ [解] 转化为格路问题（弱领先条件—参见P36例4该例是强领先条件）。即从(0,0)到(n,n)，只能从对角线上方走，但可以碰到对角线。它可看作是从(0,1)到(n,n+1)的强领先条件（只能从对角线上方走，但不可以碰到对角线）的格路问题。更进一步的，它可看作是从(0,0)到(n,n+1)的强领先条件的格路问题(因为此种格路第一步必到(0,1)格点)。故这样的字符串有 1.49 在1到n的自然数中选取不同且互不相邻的k个数，有多少种选取方案？ [解] 设：g(n,k)为从1~n中选取不同且互不相邻的k个数的方案数。 于是，按这k个数中有无数n而分为两种情况：(1)若选n，则必不能选n-1，故此种方案数为g(n-2,k-1)；(2)若不选n，则可以选n-1，故此种方案数为g(n-1,k)；所以，按加法原理，总的方案数g(n,k)=g(n-2,k-1)+g(n-1,k)。 且只有当n2k-1时，g(n,k)0；否则g(n,k)=0。因此，可给定初始值： g(2k-1,k)=1，g(2k-2,k)=0。 1.50 (a) 在由5个0，4个1组成的字符串中，出现01或10的总次数为4的字符串，有多少个？ (b) 在m个0，n个1组成的字符串中，出现01或10的总次数为k的字符串，有多少个？ [解] (a)先将5个0排成一列：00000，一个1若插在两个0中间，就形成一个“010”，则同时出现“01”和“10”，计数为2；若插在两端，则仅出现一个01”或“10”，计数为1。 现在要出现01”或“10”的总次数为4，可有两种办法： (1)先把两个1插入五个0所形成的四个空档内，再将剩下的两个1放在已插入的1的前面，比如：011100100。按乘法原理，有C(4,2)C(2+2-1,2)= C(4,2)C(3,2)种方案； (2)先把一个1插入五个0所形成的四个空档内，然后取两个1分别插入两端，剩下的一个1放在已插入的1的前面，比如：100011001。按乘法原理，有C(4,1)3种方案； 最后，按加法原理，总的方案数为C(4,2)C(3,2)+C(4,1)3=30。 (b)若k为奇数，则只有一种办法：先把 个1插入m个0所形成的m-1个空档内，然后取一个1插入头或尾，最后将剩下的 个1放在已插入的 个1的前面，形成出现k个01或10的格局。按乘法原理，总的方案数为 ； 若k为偶数，则现在可有两种办法： (1)先把 个1插入m个0所形成的m-1个空档内，再将剩下 的个1放在已插入的 个1的前面，形成出现k个01或10的格局。按乘法原理，有 = 种方案； (2)先把 个1插入m个0所形成的m-1个空档内，然后取两个1分别插入两端，再将剩下的 个1放在已插入的 个1的前面，形成出现k个01或10的格局。按乘法原理，有 = 种方案； 最后，按加法原理，总的方案数为 + 。 1.51 从N={1, 2, … , 20}中选出3个数，使得没有两个数相邻，有多少种方案？ [解] 方法一（采用排除法） 在20个数中选取3个数都不相邻的方案数； 从1～20这20个数中选取3个数，总数为 然后在其中去掉有3个数相邻的方案数，也要去掉有两个数相邻的方案数。这样，就是在20个数中选取3个数都不相邻的方案数。 设选取的3个数 ， ， 。 如果这三个数相邻，若 ≤ ≤ ，则1≤ ≤18。故此种方案有18个。 如果有两个数相邻，不妨设是 ，且 ≤ ，则1≤ ≤19，但是，当 ＝1或19时， ＝2或20， 只有3和18不能选，故 有3个数不能选，17种选择方案；当 ≠1或19时， 有4个数不能选。故 有16种选择，因此，此种方案数为： 2×17＋17×16 故此，从1～20这20个数种选取3个互不相邻的数的方案数为： 方法二（采用一一对应技术） 设：A:从1～20这20个数中选取三个数 ， ， ，使得无两数相邻的方案集。 B：从1～18这18个数中选取三个数 ， ， ，使得三数可相邻的方案集。 这里， < < 且 － ≥2， － ≥2 设： < < 且 － ≥1， － ≥1 建立双射函数h：A→B，使得： h( , , )=( , , ) 其有逆函数 :B→A, （ ， ， ）＝（ ， ， ） 故此，根据一一对应技术，有 1.52 从N={1, 2, … , n}中选出k个数，使之没有两数相邻，求不同方案数. [解] （采用一一对应技术） 设：A：从1～n这n个数中选取k个数 ， ，…， ，使之无二数相邻的方案集。 B：从1～n-k+1这n-k+1个数中选取k个数 ， ，…， ，二数可相邻的方案集。 这里：① ， （i＝1～k-1） ② ， （i=1~k-1） 建立双射函数：h：A→B h( , ,…, )=( , ,…, ) 其逆函数为： :B→A 故此，根据一一对应技术，有： 1.53 把n个无区别的球放进有标志1, 2, … , n的n个盒子中，每个盒子可放多于一个球，求有多少种方案？ [解] （采用一一对应技术） 设：A：将n个无区别的球放进n个有区别的盒子中，每盒球数不限的方案集。 B：n个“*”，n-1个隔档“1”构成的线性图案集。 于是一种放球方案与一种图案一一对应，根据一一对应技术，有 1.54 m个1，n个0进行排列，求1不相邻的排列数. 设n>m. [解] n个0有n+1个空隙（内外都计），选取m个空隙（可以选取，因为m0, 特征方程： 特征根： 通解： 初值： ， 解得 故此， 于是， （2）若 <0,则有： 从而 初值： ， 解得 故此， 于是， 2.38​ 利用置换 解 ， 。 【解】：（置换法）将置换 代入递推方程，有 整理，得： 特征方程： 特征根： 齐次通解： 非齐次特解： 代入非齐次方程，有： 即 从而非齐次得特解为： 故非齐次的通解为： 由初值 得， ，故 ，从而 ，即 于是有 ，从而 2.39​ 利用置换 解 ， 。 【解】：（置换法）将置换 代入递推方程，有 整理，得： 特征方程： 特征根： 齐次通解： 非齐次特解： （因为 ，1是一重特征根） 代入非齐次方程，有： 从而非齐次特解为： 故非齐次的通解为： 于是将 代回，有 由初值 得 ，从而 因此，有 2.40解下列递推关系： （a） , , ； （b） ， , ； （c） , ； 【解】：（a）（置换法）令 代入递推方程，有 整理，得： 特征方程： 特征根： ， 齐次通解： 非齐次特解： 代入非齐次方程，有： ， 整理，有 ，故 从而非齐次的特解为： 故非齐次的通解为： 由初值 得， ，故 得， ，故 代入有 ，故 ，即 因此， 于是， （b）（置换法）令 代入递推方程，有 整理，得： 特征方程： 特征根： ， 齐次通解： 非齐次特解： 代入非齐次方程，有： ， 整理，有 ，故 从而非齐次的特解为： 故非齐次的通解为： 由初值 得， ，故 得， ，故 代入有 ，故 ，即 因此， 于是， （c） 特征方程： 特征根： 齐次通解： 非齐次特解： 代入非齐次方程，有： 故 , 从而，从而非齐次的特解为： 故非齐次的通解为： 令A为A＋B后，有 利用 ，有 ，知 ， 从而 2.41设 满足： ，其中： ， 和 都是常数，试证该序列满足三阶奇次线性常系数奇次递推关系，且有特征多项式 。 【解】：满足特征多项式为 的递推关系为 ① 整理为 ② 将关于序列 的递推关系： ③ 代入②，有 这说明序列 满足三阶奇次线性常系数奇次递推关系①，且有特征多项式 。 2.42设 满足 ， 满足 ， ， ，试证序列 满足四阶奇次线性常系数奇次递推关系。 【解】：方法一（特征系数法） 由于序列 满足递推关系： ① 故显然也满足递推关系： 这里 ， 为任意常数 整理为： ② 由于序列 满足递推关系： ③ 故显然也满足递推关系 这里 ， 为任意常数 整理为： ④ 令 ，解之得 ， 将此代入②，④有 ⑤ ⑥ 将⑤＋⑥，并注意到 ，我们有 ⑦ 这就是序列 满足的四阶线性常系数奇次递推关系。 方法二（特征根法） 递推关系 特征方程： 特征根： 故其通解： 递推关系 特征方程： 特征根： 故其通解： 于是 因此序列 满足的四阶线性常系数奇次递推关系。 其特征多项式为 整理为 再整理为 因此，对应的四阶线性常系数奇次递推关系为 2.43在习题2.42中，若 ，试证之。 【解】：（特征根法） 递推关系 特征方程： 特征根： 故其通解： 递推关系 特征方程： 特征根： 故其通解： 于是 因此序列 满足的四阶线性常系数奇次递推关系。 其特征多项式为 整理为 再整理为 因此，对应的四阶线性常系数奇次递推关系为 2.44设 和 均满足递推关系 ，试证： (a) 满足一个三阶奇次线性常系数奇次递推关系； (b) 二阶线性常系数奇次递推关系。 【证】：(a)（特征根法） 二阶奇次线性常系数奇次递推关系 的特征方程为 ① 甲. 设其特征根为 ， ， ，则有： 于是 这说明 满足一个三阶奇次线性常系数奇次递推关系， 其特征方程为： 或者 由于 ， ，故 因此有 故此 满足如下的三阶奇次线性常系数奇次递推关系 2.​ 设其特征根为 是一个二重根，则： 于是 这说明 满足一个三阶奇次线性常系数奇次递推关系， 其特征方程为： 由于 ， ， 因此有 故此 满足如下的三阶奇次线性常系数奇次递推关系 (b)甲. 因此，这说明 满足一个二阶奇次线性常系数奇次递推关系 其特征方程为 整理为： 由于 ， ，有 于是 故此序列 满足一个二阶奇次线性常系数奇次递推关系为： 乙. 因此，这说明 满足一个二阶奇次线性常系数奇次递推关系 其特征方程为 整理为： 由于 ， ， 于是 故此序列 满足一个二阶奇次线性常系数奇次递推关系为： 2.45设 是Fibonacci序列，是找出常数a，b，c，d，使 。 【解】：（1）先求常数a,b,c,d： 令 ，有 ； ，有 ； ，有 ； ，有 注意到 ， ， ， ， ， ， ， ， ，得到 解得 解之得， 2.46对所有的正整数a,b,c,恒有 【证】：利用数学归纳法，易证： ， （参见2.75(a)的证明） 于是，我们有 2.71 [证] (采用数学归纳法) 方法一： 其中m和n都是正整数。 [证] 2.73 已知非负整数 [解] 2.79 从1,2,…,n中取r个数，要求两两不相邻，试问有多少种可能。 2.80 上题中若附加条件不包含1和n两个数，求相同问题 (Contect