《组合数学习题解答》由会员分享，可在线阅读，更多相关《组合数学习题解答（33页珍藏版）》请在金锄头文库上搜索。
1、组合数学1第一章：1、用六种方法求 839647521 之后的第 999 个排列。提示：先把 999 换算成递增或递减进位制数，加到中介数上，就不用计算序号了。解：字典序法 递增进位制法递减进位制法 邻位对换法 839647521的中介数72642321673422211222437610121372999 的中介数121211 121211 1670 1670839647521后 999 的中介数73104210675041101223036610123362839647521后 999 个的排列842196537 859713426 389547216 3 8 457692 1第二章例 5
2、：10 个数字（0 到 9）和 4 个四则运算符(+,-, ,) 组成的 14 个元素。求由其中的 n个元素的排列构成一算术表达式的个数。 因所求的 n 个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字。而第n-1 位有两种可能，一是数字，一是运算符。如若第 n-1 位是十个数字之一，则前 n-1 位必然构成一算术表达式。 10a n-1如若不然，即第 n-1 位是 4 个运算符之一，则前 n-2 位必然是算术表达式。 40an-2,根据以上分析，令 an 表示 n 个元素排列成算术表达式的个数。则 a2=120 指的是从 0 到 99 的 100 个数，以及0,1, .,9,利用
3、递推关系(2-8-1)，得 a0=1/2特征多项式 x2-10x-40 。它的根是 解方程 得 组合数学2例 7：平面上有一点 P，它是 n 个域 D1,D2,.,Dn 的共同交界点，见图 2-8-4 现 取 k 种颜色对这 n 个域进行着色， 要求相邻两个域着的颜色不同。 试求着色的方案数。 令 an 表示这 n 个域的着色 方案数。无非有两种情况 （1）D 1 和 Dn-1 有相同的颜色；（2）D 1 和 Dn-1 所着颜色不同。第一种情形，域有 k-1 种颜色可用，即 D1Dn-1 域所用颜色除外；而且从 D1 到 Dn-2 的着色方案，和 n-2 个域的着色方案一一对应。后一种 Dn
4、域有 k-2 种颜色可供使用；而且从 D1 到 Dn-1 的每一个着色方案和 n-1 个域的着色方案一一对应。 利用(2-8-3)得 a1=0,a0=k ，(2-8-3)的特征方程为 习题：4.求由 A,B,C,D 组成的允许重复的排列中 AB 至少出现一次的排列数目。 解 设 an 为所求个数，b n 为不出现 AB 的串的个数 an+bn=4n,bn=4bn-1-bn-2, / bn-2：前 n-2 个组成的串中不出现 AB 的串的个数，最后两位是 AB.组合数学3an=4an-1+bn-2, / bn-2：前 n-2 个组成的串中不出现 AB 的串的个数，最后两位是 AB.b1=4,b2
5、=15,b0=1,b3=56.x2-4x+1=0 解得x= 。2bn=S(2+ )n+t(2- )n4321tStS= ,t=32111 nnnb32324a6.试求由 a,b,c 三个文字组成的 n 位符号串 中不出现 aa 图像的符号串的数目。 解 设不出现 aa 的字符串的排列数为 an 在所有符合要求的 n 位串中，最后一位是 a,则 n-1 位是 b 或 c，有 2an-2;最后一位不是a，则是 b 或 c, 有 2an-1.故有an=2an-1+2an-2，a 1=3，a 2=8，a 0=1.x2-2x-2=0,解得x= 。3an=A(1+ )n+B(1- )n331BAA= ,B
6、=3412422nnna13. 相邻位不同为 0 的 n 位 2 进制数中一共出现了多少个 0？ 解 设相邻位不同为 0 的 n 位 2 进制数的个数为 hn 个，这些数中一共有 an 个 0，当 n 位二进制数最高位为 1 时,符合条件的 n 位二进制数的个数为 hn-1最高位为 0 时，次高位必为 1 符合条件的 n 位二进制数的个数为 hn-2，h 1=2,h2=3,h0=1.21nnh即 hn 是 F 数列 组合数学4特征方程为： 解得 a、b 为 2 重根。 设 分析上式结构可得： 把 n=2 代入可解得： 代入 an可得方程组 解得19. 求 n 位二进制数相邻两位不出现 11 的
7、数的个数。 解 设所求个数为 an,第 n 位为 0 或 1，是 0，有 an-1；是 1，则 n-1 位为 0,有 an-2.5,3,2, 21 n组合数学5特征方程为 ,012x251 ,251xnnBAxa213代入得2251BA所以 22)()(5nnna20. 在 n 个文字，长度为 k 的允许重复的排列中，不允许一个文字连续出现三次，求这样的排列的数目。 解 设所求为 ak 则 特征方程为 解得 可设 代入初值可解出 A、B31. 求下图中从 A 点出发到 n 点的路径数。 解 把上方的点序列设为 an 把下方的点序列设为 bn可得递推关系 a0 a1 a2 a3 an-3 an-
8、2 an-1 an nA b1 b2 b3 bn-3 bn-2 bn-1 bn组合数学634用腰的长度分别为 1 与 的直角等腰三角形的砖及边长为 1 的正方形的砖给宽度为21 长度为 n 的路铺面，有多少方案？在所有的方案中，小三角形的砖、大三角形的砖及正方形的砖各一共用了多少块？解 1 设所求的铺路的方案数为 ，路的右端右上角缺一块小三角形砖的铺路方案数为na（注意：由方案的对称性可知，路的右下角为小三角形砖的方案数也是 ）nb nba1=3，a 2=33+2=11；b 1=1，b 2=4an=an-1+2bn (1) bn=an-1+bn-1 (2)由（1） ，b n=(an-an-1)
9、/2，将此代入（2） ，得(an-an-1)/2= an-1 +(an-1-an-2)/2，即an-4 an-1+ an-2=0 (3)(3)的特征方程是x2-4x+1=0 (4)(4)的两个特征根是 = ， = 。3232设 an=A +B 。由 a0，a 1 可建立方程组n31BAan-1: nbn:bn:n/ 按照路的右端所用砖的情况进行分类。右端是方形砖的方案数是 an-1；右端右上角是小三角形砖的方案数是bn，右下角是小三角形砖的方案数也是 bn /nn-1/ 右端是小三角形砖的方案数是 an-1；右端是大三角形砖的方案数是 bn-1 /由（1）可推得 a0=a1-2b1=1。/ 注
10、意： a0 的值不直观，只能由递推式推得 /组合数学7，321，31A，231B，6A63Bnann3设小三角形的砖在所有的方案中一共用了 cn 块，小三角形的砖在右端右上角缺一块小三角形砖的方案中一共用了 dn 块。c1=4，c 2=28，c 0=0d1=1，d 2=8，d 3=47，cn=cn-1+2dn+2bn (1)dn=cn-1+an-1+dn-1 (2)由（1） ，d n=（c n-cn-1-2bn）/2 ，将此代入（2） ，得cn-4cn-1+cn-2=4an-1 (3)因序列a n的特征方程为x2-4x+1=0，可设序列c n的特征方程为(x2-4x+1)2=0。特征根为 （2
11、 重根） ， （2 重根） 。可设cn=(En+F) +(Gn+H) (4)nn将（4）代入（3） ，得/4)2()2( )1(1422 11的 表 达 式 已 求 出nnnn nn aHGFE HGFE 通过比较 前的系数： 121 )3(6144nnn求得 ，3E同理求得 。1G组合数学8将 E，G 的值代入（4） ，求得， ，因而求得31F31H(5)nnnc 93)(9)(c3=4c2-c1+4a2=152，由（5）直接计算 152079.152)3(33 c/ 这里的x表示对 x 就近取整 /设在所有的方案中正方形的砖共用了 cn 块，正方形的砖在路的右端右上角缺一块小三角形砖的方案
12、中一共用了 ln 块。c1=1，c 2=6，c 3=31，c 0=0；d1=0，d 2=1，d 3=7。cn=cn-1+an-1+2dn (1)dn=cn-1+dn-1 (2)由（1）得dn=(cn-cn-1+-an-1)/2，将此代入（2） ，得(3)(63)(634 21212121 nnnnn acc 设 cn=(En+F) +(Gn+H) ，将此代入（3） ，得)(63)(63)2)2 )1(42121 11 nn nnnHGFE HGFE比较系数，求得 再回（3） ，得， 因而有， 61361HFnnnc)183()18(用同样的方法可求得在所有的方案中，大三角形的砖总块数为设在所有
13、的方案中大三角形的砖共用了 cn 块，大三角形的砖在路的右端右上角缺一块小三角形砖的方案中一共用了 dn 块。c1=0，c 2=4，c 3=10，c 0=0；d1=0，d 2=1，d 3=3。组合数学9cn=cn-1+2dn (1)dn=cn-1+b n-1+dn-1 (2)求出：Cn= nn)9361()9361(可求得在所有方案中所用砖的总块数为 nn)1832()1832( 通过递推关系及直接计算可验证答案正确。 解毕。第三章：容斥与鸽巢例从 1 到 2n 的正整数中任取 n+1 个，则这 n+1 个数中，至少有一对数， 其中一个是另一个的倍数。证设 n+1 个数是 a1 , a2 ,
14、, an+1。每个数去掉一切 2 的因子， 直至剩下一个奇数为止。组成序列 r1 , r2, , rn+1。这 n+1 个数仍在 1 , 2n中，且都是奇数。而1 , 2n中只有 n 个奇数 . 故必有 ri = rj = r , 则 ,若 i j ，则 ai 是 aj 的倍数。例 5设 a1 , a2 , , am 是正整数序列，则至少存在 k 和 l , 1k l m， 使得和 ak + ak+1 + + al 是 m 的倍数。证 设 ,Sh rh mod m , 0r hm-1 ，h = 1 , 2 , , m . 若存在 l , Sl0 mod m 则命题成立否则，1r hm-1但 h
15、 = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即Sk S h，不妨设 h k则ShS k = ak+1 + ak+2 + + ah 0 mod m 例设 a1 , a2 , a3 为任意个整数，b 1b2b3 为 a1 , a2 , a3 的任一排列， 则 a1b 1 , a2b 2 , a3b 3 中至少有一个是偶数证由鸽巢原理， a1 , a2 , a3 必有两个同奇偶设这个数被除的余数为 xxy， 于是 b1 , b2 , b3 中被除的余数有个 x，一个 y这样 a1b 1 , a2b 2 , a3b 3 被除的余数必有一个为例设 a1 , a2 , , a100 是由 1 和组成的序列
