组合数学习题解答.doc

组合数学第一章：1、用六种方法求839647521之后的第999个排列。提示：先把999换算成递增或递减进位制数，加到中介数上，就不用计算序号了。解：字典序法递增进位制法递减进位制法 邻位对换法 839647521的中介数72642321673422211222437610121372999的中介数12121112121116701670839647521后999的中介数73104210675041101223036610123362839647521后999个的排列8421965378597134263895472163 8 4576921第二章例5：10个数字（0到9）和4个四则运算符(+,-,) 组成的14个元素。求由其中的n个元素的排列构成一算术表达式的个数。 因所求的n个元素的排列是算术表达式，故从左向右的最后一个符号必然是数字。而第n-1位有两种可能，一是数字，一是运算符。如若第n-1位是十个数字之一，则前n-1位必然构成一算术表达式。10an-1 如若不然，即第n-1位是4个运算符之一，则前n-2位必然是算术表达式。40an-2,根据以上分析，令an 表示n个元素排列成算术表达式的个数。则 a2=120指的是从0到99的100个数，以及0,1,.,9, 利用递推关系(2-8-1)，得a0=1/2 特征多项式x2-10x-40 。它的根是 解方程 得 例7：平面上有一点P，它是n个域D1,D2,.,Dn 的共同交界点，见图2-8-4现 取k种颜色对这n个域进行着色， 要求相邻两个域着的颜色不同。 试求着色的方案数。 令an 表示这n个域的着色 方案数。无非有两种情况 （1）D1和Dn-1有相同的颜色； （2）D1 和Dn-1所着颜色不同。 第一种情形，域有k-1种颜色可用，即D1Dn-1域所用颜色除外；而且从D1到Dn-2的着色方案，和n-2个域的着色方案一一对应。后一种Dn域有k-2种颜色可供使用；而且从D1 到Dn-1的每一个着色方案和n-1个域的着色方案一一对应。 利用(2-8-3)得a1=0,a0=k ，(2-8-3)的特征方程为 习题：4.求由A,B,C,D组成的允许重复的排列中 AB至少出现一次的排列数目。解 设an为所求个数，bn为不出现AB的串的个数an+bn=4n,bn=4bn-1-bn-2, / bn-2：前n-2个组成的串中不出现AB的串的个数，最后两位是AB.an=4an-1+bn-2, / bn-2：前n-2个组成的串中不出现AB的串的个数，最后两位是AB.b1=4,b2=15,b0=1,b3=56.x2-4x+1=0 解得x=。bn=S(2+)n+t(2-)nS=,t=6.试求由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，a1=3，a2=8，a0=1.x2-2x-2=0,解得x=。an=A(1+)n+B(1-)nA=,B=13. 相邻位不同为0的n位2进制数中一共出现了多少个0？解 设相邻位不同为0的n位2进制数的个数为hn 个，这些数中一共有an个0， 当n位二进制数最高位为1时,符合条件的n位二进制数的个数为hn-1 最高位为0时，次高位必为1符合条件的n位二进制数的个数为hn-2，h1=2,h2=3,h0=1.即hn是F数列 特征方程为： 解得a、b为2重根。 设 分析上式结构可得： 把n=2代入可解得： 代入an 可得方程组 解得 19. 求n位二进制数相邻两位不出现11的数的个数。解 设所求个数为an,第n位为0或1，是0，有an-1；是1，则n-1位为0,有an-2. 特征方程为,代入得所以20. 在n个文字，长度为k的允许重复的排列中，不允许一个文字连续出现三次，求这样的排列的数目。解 设所求为ak则 特征方程为 解得 可设 代入初值可解出A、B31. 求下图中从A点出发到n点的路径数。a0 a1 a2 a3 an-3 an-2 an-1 an n A b1 b2 b3 bn-3 bn-2 bn-1 bn解 把上方的点序列设为an 把下方的点序列设为bn 可得递推关系 34用腰的长度分别为1与的直角等腰三角形的砖及边长为1的正方形的砖给宽度为1长度为n的路铺面，有多少方案？在所有的方案中，小三角形的砖、大三角形的砖及正方形的砖各一共用了多少块？解1设所求的铺路的方案数为，路的右端右上角缺一块小三角形砖的铺路方案数为（注意：由方案的对称性可知，路的右下角为小三角形砖的方案数也是）a1=3，a2=33+2=11；b1=1，b2=4/ 按照路的右端所用砖的情况进行分类。右端是方形砖的方案数是an-1；右端右上角是小三角形砖的方案数是bn，右下角是小三角形砖的方案数也是bn /an=an-1+2bn(1) an-1: nbn:bn: n/ 右端是小三角形砖的方案数是an-1；右端是大三角形砖的方案数是bn-1 /由（1）可推得a0=a1-2b1=1。/ 注意：a0的值不直观，只能由递推式推得 /bn=an-1+bn-1(2) nn-1由（1），bn=(an-an-1)/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)的两个特征根是= ，=。设an=A +B。由a0，a1可建立方程组，设小三角形的砖在所有的方案中一共用了cn块，小三角形的砖在右端右上角缺一块小三角形砖的方案中一共用了dn块。c1=4，c2=28，c0=0d1=1，d2=8，d3=47，cn=cn-1+2dn+2bn(1)dn=cn-1+an-1+dn-1(2)由（1），dn=（cn-cn-1-2bn）/2，将此代入（2），得cn-4cn-1+cn-2=4an-1(3)因序列an的特征方程为x2-4x+1=0，可设序列cn的特征方程为(x2-4x+1)2=0。特征根为（2重根），（2重根）。可设cn=(En+F) +(Gn+H)(4)将（4）代入（3），得通过比较前的系数：求得，同理求得。将E，G的值代入（4），求得，因而求得(5)c3=4c2-c1+4a2=152，由（5）直接计算/ 这里的x表示对x就近取整 /设在所有的方案中正方形的砖共用了cn块，正方形的砖在路的右端右上角缺一块小三角形砖的方案中一共用了ln块。c1=1，c2=6，c3=31，c0=0；d1=0，d2=1，d3=7。cn=cn-1+an-1+2dn(1)dn=cn-1+dn-1(2)由（1）得dn=(cn-cn-1+-an-1)/2，将此代入（2），得 (3)设cn=(En+F) +(Gn+H)，将此代入（3），得比较系数，求得 再回（3），得 因而有用同样的方法可求得在所有的方案中，大三角形的砖总块数为设在所有的方案中大三角形的砖共用了cn块，大三角形的砖在路的右端右上角缺一块小三角形砖的方案中一共用了dn块。c1=0，c2=4，c3=10，c0=0；d1=0，d2=1，d3=3。cn=cn-1+2dn(1)dn=cn-1+b n-1+dn-1(2)求出：Cn=可求得在所有方案中所用砖的总块数为通过递推关系及直接计算可验证答案正确。解毕。第三章：容斥与鸽巢例从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数， 其中一个是另一个的倍数。证设n+1个数是 a1 , a2 , , an+1。每个数去掉一切2的因子， 直至剩下一个奇数为止。组成序列 r1 , r2, , rn+1。这n+1个数仍在 1 , 2n中，且都是奇数。而1 , 2n中只有n个奇数 . 故必有 ri = rj = r , 则,若ij ，则 ai 是 aj 的倍数。例5设 a1 , a2 , , am是正整数序列，则至少存在k和 l , 1k l m， 使得和 ak + ak+1 + + al 是m的倍数。证设,Sh rh mod m , 0rhm-1，h = 1 , 2 , , m . 若存在l , Sl0 mod m 则命题成立否则，1rhm-1但h = 1 , 2 , , m由鸽巢原理，故存在 rk = rh , 即Sk Sh，不妨设 h k则ShSk = ak+1 + ak+2 + + ah 0 mod m 例设 a1 , a2 , a3为任意个整数，b1b2b3为a1 , a2 , a3的任一排列， 则 a1b1 , a2b2 , a3b3中至少有一个是偶数证由鸽巢原理， a1 , a2 , a3必有两个同奇偶设这个数被除的余数为 xxy， 于是b1 , b2 , b3中被除的余数有个x，一个y这样a1b1 , a2b2 , a3b3 被除的余数必有一个为例设a1 , a2 , , a100是由 1和组成的序列 , 已知从其任一数开始的顺序10个数的 和不超过16即ai + ai+1 + + ai+9 16，1 i 91则至少存在 h 和 k ，k h，使得 ah + ah+1 + + ak = 39证令，j =1 , 2 , ,100 显然S1S2S100，且 S100=(a1 + +a10)+(a11 + +a20)+(a91 + +a100) 根据假定有S1001016=160，作序列S1, S2 , , S100 , S1 +39, , S100+39 .共200项其中最大项 S100+39160+39由鸽巢原理，必有两项相等 而且必是前段中某项与后段中某项相等设 Sk=Sh + 39，kh,SkSh =39 即 ah + ah+1 + + ak = 39 5.设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7， c1c2c3c4c5c6c7试证存在 整数i和j，1ij7，使得下列之一必定成立：ai=aj=bi=bj， ai=aj=ci=cj，ai=aj=ci=cj 证：显然，每列中必有两数字相同，共有种模式， 有或两种选择故共有2种选择2=6现有7列， 即必有列在相同的两行选择相同的数字，即有一矩形，四角的数字相等 6. 在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于 证把正方形分成四个(1/2)(1/2)的正方形 如上图.则这点中必有两点落在同一个小正方形内而小正方 形内的任两点的距离都小于7在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2证：把边长为的三角形分成四个边长为1/2的三角形，如上图：则这点中必有两点落在 同一个小三角形中小三角形中任意两点间的距离都小于1/210. A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B作原料， III不允许用A作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料）解 按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区棋盘多项式为：R()=R()R()=(1+x)(1+3x+x2 )=1+4x+4x + x 3故方案数3!42!+4 1!1 0!114m+1行列的格子同m种颜色着色，每格着一种颜色，其中必有一个4角同色的矩形。证每列有(m+1)行，只有m种颜色，故一列中必有两格同色同色的个格子的行 号有种取法有m种色，故有m 种同色模式，现有m +1列，必有两列的同色模式相同即由这两列的对应行上有 个格子同色，正好是一个矩形的个角上的格子得证 17. 在平面直角坐标系中至少任去多少个整点才能保证存在3个点构成的三角形的重心是整点？解设(x，y)是整点，每个分量模3后有 如下表的结果：若有个点模后的结果落在上表中的同 一格中，则这个点的重心是整点若有点占满一行，则点重心是整点；有点占满一列，则点重心是整点；若存在一组均匀分布，则有3点重心是整点由上表可知，若只有8个点，也不能保证有点的重心是整点（因为若每个格子都有 点，则只占有个格子，无法保证上面的要求）下面假设存在个点，其中任点的 重心都不是整点则这9个点，至少占有5个格子（因 为每格中最多有2个点，否则有3个点的重 心为整点），每行最多有格，又=3， 所以每行都有点 同理，每列都有点 不妨设第一行2点，第二行2点，第三行1点 前2 行有两种模式：或这样第三行的点无论在哪一列都构成占满一列或构成一组均匀分布满足前面说的 三点重心是整点的情况故9个点能保证其中存在个点的重心是整点第四章：正多面体及足球的转动群一、 正四面体 （顶点数：4 棱数：6）1、 以顶点为目标的转动群：1）以顶点面心为轴 （1）1（3）1 8个2）以棱中棱中为轴 （2）2： 3个3）不动 （1）4： 1个2、 以棱为目标的转动群：1）以顶点面心为轴 （3）2： 8个2）以棱中棱中为轴 （1）2（2）2：3个3）不动 （1）6： 1个3、 以面为目标的转动群：1）以顶点面心为轴 （1）1（3）1： 8个2）以棱中棱中为轴 （2）2： 3个3）不动 （1）4： 1个二、 正八面体（顶点数：6 棱数：12）1、 以顶点为目标的转动群：1）以顶点顶点为轴 （1）2（4）1：6个（1）2（2）2：3个2）以棱中棱中为轴 （2）3： 6个3）以面心面心为轴 （3）2： 8个4）不动（1）6： 1个2、 以棱为目标的转动群：1）以顶点顶点为轴 （4）3：6个（2）6：3个2）以棱中棱中为轴 （1）2（2）5： 6个3）以面心面心为轴 （3）4： 8个4）不动（1）12： 1个3、 以面为目标的转动群：1）以顶点顶点为轴 （4）3：6个（2）6：3个2）以棱中棱中为轴 （2）3： 6个3）以面心面心为轴 （1）2（3）2： 8个4）不动（1）8： 1个三、 正二十面体（顶点数：12 棱数：30）1、 以顶点为目标的转动群：1）以顶点顶点为轴 （1）2（5）2：24个2）以棱中棱中为轴 （2）6： 15个3）以面心面心为轴 （3）4： 20个4）不动 （1）12： 1个2、 以棱为目标的转动群：1）以顶点顶点为轴 （5）6： 24个2）以棱中棱中为轴 （1）2（2）14：15个3）以面心面心为轴 （3）10： 20个4）不动 （1）30： 1个3、 以面为目标的转动群：1）以顶点顶点为轴（5）4：24个2）以棱中棱中为轴 （2）10： 15个3）以面心面心为轴（1）2（3）6： 20个4）不动 （1）20： 1个四、 正方体（顶点数：8 棱数：12）1、 以顶点为目标的转动群：1）以顶点顶点为轴 （1）2（3）2：8个2）以棱中棱中为轴 （2）4： 6个3）以面心面心为轴 （4）2： 6个（2）4： 3个4）不动 （1）8： 1个2、 以棱为目标的转动群：1）以顶点顶点为轴 （3）4： 8个2）以棱中棱中为轴 （1）2（2）5：6个3）以面心面心为轴 （4）3： 6个（2）6： 3个4）不动 （1）12： 1个3、 以面为目标的转动群：1）以顶点顶点为轴 （3）2： 8个2）以棱中棱中为轴 （2）3： 6个3）以面心面心为轴 （1）2（4）1：6个（1）2（2）2：3个4）不动 （1）6： 1个五、 正十二面体（顶点数：20 棱数：30）1、 以顶点为目标的转动群：1）以顶点顶点为轴 （1）2（3）6：20个2）以棱中棱中为轴 （2）10： 15个3）以面心面心为轴 （5）4： 24个4）不动 （1）20： 1个2、 以棱为目标的转动群：1）以顶点顶点为轴（5）6：20个2）以棱中棱中为轴 （1）2（2）14： 15个3）以面心面心为轴 （5）6： 24个4）不动 （1）30： 1个3、 以面为目标的转动群：1）以顶点顶点为轴（3）4：20个2）以棱中棱中为轴（2）6： 15个3）以面心面心为轴 （1）2（5）2： 24个4）不动 （1）12： 1个六、 足球（顶点数：60 棱数：90 五边形：12 六边形：20）1、 以顶点为目标的转动群：1）以五边行面心五边行面心为轴 （5）12： 24个2）以棱中棱中为轴（2）30： 15个3）以六边行面心六边行面心为轴 （3）20： 20个4）不动 （1）60： 1个2、 以棱为目标的转动群：1）以五边行面心五边行面心为轴 （5）18： 24个2）以棱中棱中为轴（1）2（2）44： 15个3）以六边行面心六边行面心为轴 （3）30： 20个4）不动 （1）90： 1个例1等边三角形的3个顶点用红，兰，绿3着色，有多少种方案？解在3维空间考虑，3顶点的置换群S3。(3)12个;(1)1(2)13个;(1)31个;l=(231+332+33)/6=10例2甲烷CH4的4个键任意用H,C1,CH3, C2H5 连接，有多少种方案？解CH4的结构是一个正4面体，C原子居于正4面体的中心。正4面体的转动群按转动轴分类：顶点-对面的中心：(1)(3) 8个；棱中-棱中： (2) 3个；不动：(1) 1个；6条棱,每条棱看作一有向边，正向重合与反向重合共62=12个位置，故转动群的群元有12个。l=1142+44/12=44+64/3=36。 例4正6面体的6个面分别用红，蓝两种颜色着色，有多少方案？解：正6面体的转动群用面的置换表示：面心-面心90。(1)2(4)16个180。(1)2(2)23个顶点-顶点120。(3)28个棱中-棱中180。(2)36个不动(1)61个1223+324+822+26/24=10例5用2种颜色给正6面体的8个顶点着色，有多少方案？解：用顶点的置换表示：面心-面心90。(4)26个180。(2)43个顶点-顶点120。(1)2(3)28个棱中-棱中180。(2)46个不动(1)81个1724+622+28/24=34+3+32/3=23例6在正6面体的每个面上任意做一条对角线，有多少方案？解：在每个面上做一条对角线的方式有2种，可参考面的2着色问题。但面心-面心的转动轴转90。时，无不动图象。除此之外，都可比照面的2着色。所求方案数：面心-面心90。(1)2(4)16个0 (无不动图象)180。(1)2(2)23个324顶点-顶点120。(3)28个822棱中-棱中180。(2)36个623不动(1)61个260+324+822+623+26/24=6+4+6+8/3=8枚举：（6 ，0） 1个 6个面上的对角线构成个四面体 （5，1） 1个 （4，2） 1个 （4，1，1） 1个 （3，3） 4 个 （Y Y）1个 （ ）1个 （ ） 2个例7骰子的6个面分别有1,6点，有多少种不同的方案？解6!个图象的目标集,只有单位元有6!个不动点(图象)其他23个群元不动点。由Burnside引理有C1(e)/24=6!/24=30个方案。C1(p1)=C1(p2)=C1(p23)=02点,3点,6点各有两种取向1点,4点,5点各有一种取向故应有3023=240种方案。例810根红、10根蓝、10根绿火柴搭一个正20面体，有多少方案？解：正20面体有正3角形组成，12个顶点，30条棱，20个面置换群为：不动：（1）301个（30！/10！10！10！）*230（30根火柴的可重组合） （火柴头两个方向）顶点顶点（5）624个 （12个顶点，6个轴，4个转动） 6圈（6个轮换，每个轮换5根火柴，5根火柴颜色必须相同，才有不动图象）（6！/2！2！2！）*26面心面心（3）10 20个 （20个面，10个轴，2个转动）（10个轮换，每个轮换3根火柴，3根火柴颜色必须相同，才有不动图象,故无不动图象）棱中棱中 （1）2（2）1415个 （火柴有方向，无不动图象）方案数： L=(30！/10！10！10！)*230+24*(6！/2！2！2！)*26)/606.由b、r、g三种颜色的5颗珠子镶成的圆环，共有几种不同的方案?解：正5边形的运动群绕心转72。(5)12个 144。(5)12个翻转180。(1)(2)25个不动(1)51个不同方案数为m=(35+431+533)/10=3911.在正四面体的每个面上都任意引一条高，有多少方案？解：除了绕顶点-对面的中心轴旋转均不会产生不变的图象外,绕其他轴的旋转相当于正4面体的面3着色。正4面体的转动群用面的置换表示：顶点-对面的中心：(1)(3) 2*4= 8个；棱中-棱中： (2) 2 3个；不动： (1)4 1个；可得不同的方案数为M=34+0832+332/12=912.一幅正方形的肖像与一个立方体的面一样大，6副相同的肖像贴在立方体的6个面上有多少种贴法？解：除了绕面心面心轴旋转任何度数均不会产生不变的图象外，绕其他轴的旋转都相当于正六面体的面4着色。正6面体的转动群用面的置换表示：不动 (1)6 1个面心-面心 90。(1)2(4)1 6个180。 (1)2(2)2 3个顶点-顶点 120。(3)2 8个棱中-棱中 180。 (2)3 6个参照讲义4.6例4可得不同的方案数为M=46+0643+0344+842+643/24=19214.足球由正5边形与正6边形相嵌而成。一个足球由多少块正5边形与正6边形组成？把一个足球所有的正6边形都着以黑色，正5边形则着以其它各色，每个5边形的着色都不同，有多少种方案？解：5边形面心与体心连一直线从另一5边形面心穿出。该直线为对称轴。欠角=360。(108。+2120。)=12。;720。/12。=60(个顶点);603/2=90(条棱);60/5=12(个5边形);602/6=20(个6边形)一个顶点通过一个转动可与任一顶点重合，重合的方式只有1种，故转动群的阶为60。因为5边形着色均不同，所以除不变置换的任意旋转都不会产生不变图象，12个5边形着不同颜色共12!种方案。所以共有12!/60=7983360种方案。附（例题）：用相同的火柴棍搭一个足球，有多少方案？解：相当于对棱（火柴棍）二着色（不能照搬）。置换群为：不动（1）901个5边形面心面心72。倍数 （5）18 24个（12个5边形，6个轴，4个转动） 18圈6边形面心面心120。倍数（3）3020个（20个6边形，10个轴，2个转动） 30圈棱中棱中（6边形边界）180。 （1）2（2）44 15个 （60个5边形的棱，90-60=30，30/2=15，故15个转动） 方案数：l=(290+24*218+20*230+0)/60=*火柴有方向，棱中棱中转动时无不动图象*16.用8个相同的骰子垛成一个正6面体，有多少方案？解：相当于正六面体每个角上放一个骰子。骰子按讲义4.6中关于正立方体的不同旋转均不会产生重合现象，共24种方案。因此本题相当于正六面体的顶点24着色。但绕顶点-顶点的对称轴旋转不会产生重合的图象。参照习题11可得不同的方案数为M=248+6242+3244+08244+6244/24=4586595984。 17.正六面体的6个面和8个顶点分别用红、蓝两种颜色的珠子嵌入。试问有多少种不同的方案数?(旋转使之一致的方案看作是相同的)。解：本题相当于把讲义4.6例4例5合并起来,8个顶点6个面共14个元素的置换群。面心-面心90。(1)2(4)1(4)26个180。(1)2(2)2(2)43个顶点-顶点120。(3)2(1)2(3)28个棱中-棱中180。(2)3(2)4 6个不动 (1)6(1)8 1个方案数为：625+328+826+627+214/24 =776定义 凸多面体与一个顶点相关的面角之和与360。的差称为该顶点的欠角。定理凸多面体各顶点欠角的和为720。(用欧拉定理证)用正5边形搭成的正多面体:(5-2)180。/5=108。,360。-3108。=36。720。/36。=20(个顶点)一个顶点3条棱，重复度为2：203/2=30条棱一个顶点相关3个面,重复度为5：203/5=12个面用正3角形搭成的面最多的正多面体: 360。-560。=60。720。/60。=12(个顶点)一个顶点关联5条棱,重复度为2：125/2=30条棱。一个顶点关联5个面,重复度为3：125/3=20个面正三角形可组成正四、八、20面体。正4面体：4个顶点、6条棱、4个面；正8面体：6个顶点、12条棱、8个面；正20面体：12个顶点、30条棱、20个面。足球：欠角=360。(108。+2120。)=12。720/12 =60(个顶点)603/2=90(条棱)60/5=12(个5边形)602/6=20(个6边形) (正20面体砍去12个顶点) 第六章：/*单纯表格法与改善的单纯表格法的区别在于前者计算所有的Pj，j1 , 2 , , n+m后者先算B1，P0，再算CBB1，找出一个满足jcjCBB1Aj0的Aj，只计算Pj B1Aj,两者都通过计算min i/ijij 0来确定退出基Ak，通过行变换将Pj变成ek，同时用同样的行变换将B1变成B1，P0变成P0，从而进入下一轮迭代*/*在改善的单纯形表格法中，因为每次的高斯消元均对P0和B-1进行操作，这样每次先进行高斯消元后，均可进行CB*B-1的计算，进而应用 入j= Cj- (CB*B-1)*Aj，得到每个入的值，对于MAX要判断全部为=0*用大M法时，求最大值时M0。Moni ：按照字典序法、递增进位制法、递减进位制法和邻位对换法分别求全排列817249365之后的第99个全排列。字典序法递增进位制法递减进位制法邻位对换法原中介数7050130137510100001015730014450399对应进位制数40114011130130新中介数70510320375141110010202300144633对应排列817329645857239461124639857712948365a，b，c，d，e构成的n位字符串中要求同一字符不能连续出现3次，这样的字符串有多少个?在所有这样的串中同一字符连续出现2次的情况一共出现了多少次?解：(1)设所求的字符串数为Un个，按最后两个字符是否相同进行分类：相同： 4Un-2不相同：4Un-1即：Un=4Un-1+4Un-2特征方程为：x2-4x-4=0两个特征根为：=2+2 =2-2初值：U1=5；U2=25；U3=120 -U0=5/4设Un=An+Bn A+B=5/4 A+B=5解得：A=5(2+)/16 B=5(2-)/16 Un=5(2+)/16n+5(2-)/16n(2) 设在所有这样的串中同一字符连续出现2次的情况一共出现了Vn次, 按最后两个字符是否相同进行分类：相同： 4Vn-2+4Un-2 不相同：4Vn-1即：Vn=4Vn-1+4Vn-2+4Un-2- Vn-4Vn-1-4Vn-2=4Un-2 (1)特征方程为：（x2-4x-4）2=0两个特征根为：=2+2(2重根)； =2-2(2重根)。初值：V1=0;V2=5;V3=40;V4=280可设Vn=（En+F）n+(Gn+H) n (2)将(2)代入(1)得： （En+F）n+(Gn+H) n -4E（n-1）+Fn-1+G（n-1）+H n-1 -4E（n-2）+Fn-2+G（n-2）+H n-2 = 4(An-2+Bn-2)4En-1+8En-2=4An-2 4Gn-1+8Gn-2=4Bn-2 求出：E=G=5/32 由V1=0 和V0=0(推出)，求出：F=-5/64;H=5/64. Vn=(5/32*n-5/64)n+(5/32*n+5/64)n3、求下列有禁区的棋盘布子的方案数。解：禁区的棋盘多项式为： （1+3x+x2）2 (1+4x+2x2)=1+10x+37x2+62x3+47x4+16x5+2x6 方案数：=6！-10*5！+37*4！-62*3！+47*2！-16*1！+2*0！ =720-1200+888-372+94-16+2 =1164、证明：在平面直角坐标系中，33个整点中必有9个整点的重心仍是整点。证：先证明9个整点中必有3个整点的重心的仍是整点。（证明方法请参照第三章习题17解答）33个整点中必有9个3点组，每组的重心仍是整点。而这9个重心中必有3个的重心仍是整点，从而就证明了33个整点中必有9个整点的重心仍是整点。附：第三章习题1717. 在平面直角坐标系中至少任去多少个整点才能保证存在3个点构成的三角形的重心是整点？解设(x，y)是整点，每个分量模3后有 如下表的结果：若有个点模后的结果落在上表中的同 一格中，则这个点的重心是整点若有点占满一行，则点重心是整点；有点占满一列，则点重心是整点；若存在一组均匀分布，则有3点重心是整点由上表可知，若只有8个点，也不能保证有点的重心是整点（因为若每个格子都有 点，则只占有个格子，无法保证上面的要求）下面假设存在个点，其中任点的 重心都不是整点则这9个点，至少占有5个格子（因 为每格中最多有2个点，否则有3个点的重 心为整点），每行最多有格，又=3， 所以每行都有点 同理，每列都有点 不妨设第一行2点，第二行2点，第三行1点 前2 行有两种模式：或这样第三行的点无论在哪一列都构成占满一列或构成一组均匀分布满足前面说的 三点重心是整点的情况故9个点能保证其中存在个点的重心是整点5、用外形相同的10根红火柴，10根蓝火柴，10根黄火柴搭一个正20面体，有 多少方案?解：20面体由正三角形组成，12个顶点，20个面，30条棱。以棱为目标的转动群：不动:(1)301个顶点对顶点旋转72 144(5)624个 面心对面心旋转120（不存在不动）(3)1020个棱中对棱中 （无）(1)2(2)1415个转动群阶数：|G|=1+24+20+15=60 (等于棱数乘以2)方案数等于：l=230*(30!/10!10!10!)+24*26* (6!/2!2!2!)/606、min z=x1+x2+x3x1-2x2-2x1-x2-x3-32x2+x34x1,x2,x30解：引入松弛变量x4、x5、x6;约束条件变为： x1-2x2- x4=-2 x1-x2-x3- x5=-3 2x2+x3- x6=4 式乘以-1；式乘以-1；加入人工变量x7;约束条件变为： x1 x2 -1 2 0 0 1 0 0 x3 2 -1 1 1 0 0 1 0 x6 = 3 0 2 1 -1 0 0 1 x4 4 x5 x7用二阶段法(1)第一阶段 minzx7，用改善单纯形法求得一个顶点过程如下BCBCBB-1C0000001P0P1P2P3P6P4P5P7A4002-1(2)001001A5003-1110010A7114021-1001z=40-2BCBCBB-1C0000001P0P1P2P3P6P4P5P7A20-111/21001/200A5002-1/2010-1/210A7112(1)01-1-1012z=2-1BCBCBB-1C0000001P0P1P2P3P6P4P5P7A20 10 2011/2-1/2001/2A50 00 3003/2-1/2-3/211/2A10 102101-1-101Z=00由上表得一允许解：x1=2;x2=2; x3= x4= x5= x6=0,以（2，2，0，0，0，0）为起始点，开始第二阶段，如下表：BCBC111000P0P1P2P3P6P4P5A2 12011/2-1/200A503003/2-1/2-3/212A1 12101-1-102 400-1/2A1退出，A3加入BCBC111000P0P1P2P3P6P4P5A2 11-1/2100-1/20A500-3/2001012A3 12101-1-102 31/20013/20第二阶段计算结果如下：所以问题的解为：x1=0; x2=1;x3=2时，minz=3。大M法设min z=x1+x2+x3+6x7 M=6 结果如下表：BCBCBB-1C1110006P0P1P2P3P6