第6章组合数学初步

第6章组合数学初步组合数学是既古老又年轻的数学分支，它的渊源可以追溯到公元前2200年的大禹治水时代，大禹治水时，就已观察到神龟背上的3阶幻方。中外历史上许多著名的数学游戏是它古典部分的主要内容。例如数学游戏幻方问题：给定自然数1，2，…，将其排成n阶方阵，要求每行、每列和每条对角线上各数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻和。图6.1是一个3阶幻方，其幻和等于15。图6.13阶幻方816357492首先人们要问：1)存在性问题：即n阶幻方是否存在？2)计数问题：如果存在，对某个确定的n，这样的幻方有多少种？3)构造问题：即枚举问题，亦即如何构造n阶幻方？组合数学就是研究上述提出的问题。特别是近年来，随着电子计算机科学、计算数学、通信以及许多学科的发展，组合数学这门历史悠久的学科得到了迅速发展。计算机的运行需要编程来控制，然而编程的基础往往是求解问题的组合学算法。组合数学主要研究离散对象的安排或配置方案的存在性、计数、枚举构造和优化等问题。同时用计算机解决某个问题如果有多种算法可供选择时，就要考虑算法的复杂度问题。衡量时间复杂度的一个重要指标就是算法的运算次数，即求出在最坏情况下的运算次数或按概率分布的平均运算次数。而衡量空间复杂度的主要指标就是所占用的存储空间大小。为此，就要用到组合数学的方法和技巧。因此，组合数学已成为计算机学科各专业的基础知识。§6.1计数基本原理人们把所研究的对象叫做元素，把某些元素的总体叫做集合，只有有限个元素的集合称为有限集。在通常情况下，组合数学研究的对象是有限集。组合计数问题是求n元集合中满足某些给定条件的子集的个数。常常用到下面两个基本原理。6.1.1加法原理和乘法原理6.1.1加法原理和乘法原理如果完成一件事情有两个方案，而第一种方案有m种方法，第二种方案有n种方法可以实现，只要选择任何方案中的某一种方法，就可以完成这件事情，并且这些方法两两互不相同，则完成这件事情共有m+n种方法。若用集合语言，加法原理则可以描述为：设有限集合A有m个元素，B有n个元素，且A与B不相交，则A与B的并共有m+n个元素。如果我们用符号表示有限集合A的元素的个数，上述可描述为定理6.1

设A，B为有限集，，则

.一般情况有定理6.2

设n个有限集合，满足，则

例6.1某班有男生18人，女生12人，从中选出一名代表参加会议，问共有多少种选法？解：用集合A表示男生，B表示女生，则该班中的学生要么属于A，要么属于B.根据加法原理，全班共有18+12=30个学生，故有30种选法。例6.2

在所有六位二进制数中，至少有连续4位是1的有多少个？解：所有满足要求的二进制数分成如下3类：（1）恰有4位连续的1.它们可能是*01111，011110，11110*，其中“*”可能取0或1.故在此情况下，共有5个不同的六位二进制数。（2）恰有5位连续的1.它们可能是011111，111110，共有2个。（3）恰有6位连续的1.即111111，共有1种可能。（4）综合以上分析，由加法原理知共有5+2+1=8个满足题意要求的六位二进制数。乘法原理

如果完成一件事情需要两个步骤，而第一步有m种方法，第二步有n种方法去实现，则完成该件事情共有种方法。乘法原理也可以用集合语言描述为：设有限集合A有m个元素，B有n个元素，，记(a，b)为一有序对，所有有序对构成的集合称为A和B的积集（或笛卡尔乘积），记作，那么共有个元素。定理6.3

设A，B为有限集，，则

一般情况有定理6.4

设n个有限集合，则

例6.3

仍设某班有男生18人，女生12人，现要求从中分别选出男女生各一名代表全班参加比赛,问共有多少种选法?解：仍像例6.1那样,用集合A表示男生，B表示女生，那么根据乘法原理，共有种选法。6.1.2包含排斥原理包含排斥原理是计数中常用的一种方法，先举一例说明如下。例，求不超过20的正整数中为2或3的倍数的数。不超过20的数中2的倍数有10个：

2,4,6,8,10,12,14,16,18,20不超过20的数中3的倍数有6个：

3,6,9,12,15,18但其中为2或3的倍数的数只有13个，而不是10+6=16个，即

2,3,4,6,8,9,10,12,14,15,16,18,20其中6,12,18同时为2和3的倍数。若计算10+6=16，则重复计算了一次6，12，18。我们知道加法原理是指时，若时，会怎样？包含排斥原理回答了这个问题。正如上面的例子，这时，将计算了两回，所以

定理6.5

设A，B为有限集，则

.如果A，B是有限集U的子集，若记，则，由集合的德摩根定律，，定理6.5可写成定理6.5可推广为或当集合A，B是有限集U的子集时，则有定理6.6

设n个有限集合，则或当n个集合是有限集U的子集时，则例6.5

一个学校只有3门课程：数学、物理、化学。已知修这3门课的学生分别有170、130、120人；同时修数学、物理两门课的学生有45人；同时修数学、化学的有20人；同时修物理、化学的有22人；同时修三门课的学生有3人。假设学校的学生至少修一门课程，问这个学校共有多少学生？解：令：A为修数学课的学生集合；

B为修物理课的学生集合；

C为修化学课的学生集合；由题意，，，由包含排斥原理知

。即该学校共有336人。例6.6

求从1到1000不能被5、6和8整除的整数个数。解：为解决这个问题我们引入一个概念。对于实数x，代表不超过x的最大整数。此外，我们将两个整数a，b或三个整数a，b，c的最小公倍数相应地记为lcm(a,b)或lcm(a,b,c).令：U是由前1000个正整数组成的集合。A1是前1000个正整数中能被5整除的整数集合。A2是前1000个正整数中能被6整除的整数集合。A3是前1000个正整数中能被8整除的整数集合。于是集合中的整数可同时被5、6整除，当且仅当它能被lcm(5,6)整除。由于lcm(5,6)=30，lcm(5,8)=40，lcm(6,8)=24.

于是于是这样，由包含排斥原理知，从1到1000不能被5、6和8整除的整数个数为§6.2鸽笼原理鸽笼原理(又叫抽屉原理)指的是一个简单明了的事实：为数众多的一群鸽子飞进不多的鸽笼里，则至少有一个鸽笼飞进了两只或更多的鸽子。这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学的历史上起了很重要的作用。6.2.1鸽笼原理鸽笼原理的简单形式可以描述为：定理6.7

如果把n+1个物品放在n个盒子中，那么至少有一个盒子中有两个或更多的物品。证明：倘若每个盒子中至多有一个物品，那么n个盒子中至多有n个物品，而我们共有n+1个物品，矛盾。故定理成立。例如，在13个人中必有两人生日的月份是相同的，在367个人中必有两人在同一天过生日。鸽笼原理只断言存在一个盒子，该盒子中有两个或两个以上的物品，但它并没有指出是哪个盒子，要想知道是哪一个盒子，则只能逐个检查这些盒子。所以，这个原理只能用来证明某种安排的存在性，而对找出这些安排却毫无帮助。例6.7

从1到200的所有整数中任取101个，则这101个整数中至少有一对数，其中的一个一定能被另一个整除。证明：设是被选出的101个整数，对任一，都可以唯一地写成如下的形式：，其中为正整数，为奇数。例如：，

.由于，所以只能取1，3，5，…，199这100个奇数，而共有101项，由鸽笼原理知，存在，使得

不妨设，则

=整数，即能被整除。6.2.1鸽笼原理的加强形式

定理6.8

设q1,q2,…,qt是正整数，把件物品放入t个盒子里，则存在某一i(1≤i≤t)使第i个盒子里至少装qi件物品。证明：倘若对所有的i(1≤i≤t)均有第i个盒子至多装有qi-1件物品，从而这t个盒子装有的物件总数至多为从而产生矛盾。所以定理成立。当q1=q2=…=qt=r时，上述原理可叙述为：如果把t(r-1)+1件物品装入t个盒子中，则至少有一个盒子至少有r件物品。这种情况的另一种提法为：如果t个整数q1,q2,…,qt的算术平均数大于r-1，则qi(1≤i≤t)中至少有一个不能小于r.证明：若不然，则qi≤r-1(1≤i≤t).因此，

从而产生矛盾。例6.8

证明每个长为n2+1的实数序列,,…,含有一个长为n+1的递增子序列或长为n+1的递减子序列。证明：倘若不存在长为n2+1的递增子序列，我们将证明一定存在长为n+1的递减子序列。令qk是以ak为首元素的最长递增子序列的长度，则1≤qk≤n.由鸽笼原理的加强形式，取r=n+1，知n2+1个数qk（1≤k≤n2+1），当1≤mk≤n时，至少有n+1个数相等。设此时必有（1≤i≤n）.若不然，存在某一i，使，取以元素开始的最长子序列，然后把放在这个子序列的前面，就得到一个以为首元素的递增子序列。这样与矛盾。故(1≤i≤n)从而是一个长为n+1的递减子序列。从上面的几个例子可以看出，尽管鸽笼原理很简单，但它却能解决一些看似很复杂的组合问题。在将其运用到具体的问题时，需要一定的技巧去构造具体问题中的“鸽子”与“鸽笼”。§6.3排列与组合大量的计数问题呈现如下的类型：(1)对元素的有序的摆放数或有序的选择数进行计数

a)没有重复元素。

b)允许元素重复。(2)对元素的无序的摆放数或无序的选择数进行计数

a)没有重复元素。

b)允许元素重复。6.3.1基本的排列与组合集合的排列n元集合S的一个r排列是指先从S中选出r个元素，然后将其按次序排列。一般用P(n,r)或表示n元集合的r排列数。定理6.9对于满足的正整数n和r，有证明：要构造n元集合的一个r排列，我们可以在n个元素中任取一个作为第一项，有n种取法；在取定第一项后，第二项可以从剩下的n-1个元素中任选一个，有n-1中取法；……；同理，在前r-1项取定后，第r项有n-r+1种取法。由乘法原理知显然，有⑴P(n,r)=0(r>n);⑵P(n,1)=n(n≥1);⑶全排列数P(n,n)=n!.我们规定0!=1.例6.9

大家所熟知的“15迷宫”是将标有数字1到15的15个可以滑动的小正方形装在一个4×4的正方形框架上，剩下一个小的空方块。游戏是将15个小方块从任一排列方式移动成如图6.2所示的初始位置。现在问：这15个小方块在4×4地框架上有多少种不同的排列方式？解原问题就是求将1，2，…，15放在4×4框架中的16个小方块上而剩下一个空方块的方式数。我们将空方块看作16，则原问题就变为1，2，…，16放入16个各小方块中的方式数，它等于{1,2,…,16}的全排列数。即有P(16,16)=16!种不同的排列方式。图6.2123456789101112131415例6.10A单位有7位代表，B单位有3位代表，排成一列合影，要求B单位3人排在一起。问有多少种不同的排列方案？解:B单位3个人的某一排列作为一个元素。参加A单位进行排列，可得方案数为(7+1)!=8!.

且B单位的3人有3!种排列.

由乘法原理，总排列方案数为8!×3!.例6.11若例6.10中B单位的3人不能相邻，且A单位的2人排在两端，问有多少种不同的排列方案。解:A单位7人共有7!种排列。设A1A2A3A4A5A6A7是A的一个排列。两端固定后，B单位3人中的第一人有6种选择

A1*A2*A3*A4*A5*A6*A7即上面*的位置，第二位为了不与第一位相邻，故只有5种选择。第三位有4种选择。故排列总数为

7!×6×5×4=604800前面考虑的排列是在直线上进行的或者确切的说，是r线排列。若在圆周上进行排列，结果又如何呢？在一个r圆排列的任意两个相邻元素之间都有一个位置，共有r个位置。从这r个位置处将该圆排列断开，并拉直成线排列。或者换个说法，将r个r线排列

a1a2…ar-1ar,a2a3…ara1,…,ara1…ar-2ar-1的首位相连围成圆排列，得到的是同一个r圆排列。因此，下面的定理成立：定理6.10n元集合的r圆排列数为例6.1210个男生和5个女生聚餐，围坐在圆桌旁，任意两个女生不相邻的坐法有多少种？解:先把10个男生排成圆形，有种方法。固定一个男生的排法，把5位女生插在10个男生之间，每两个男生之间只能差一个女生，而且5个女生之间还存在着排序问题，故可有P(10,5)种排法。由乘法原则知，共有9!×P(10,5)种坐法。集合的组合n元集合S的r组合是指从S中取出r个元素的一种无序选择，其组合数记为或C(n,r)或.定理6.11若0≤r≤n，则证明:设S是一n元集合，任取S的一个r组合，将该r组合中的r个元素进行排列，便可得到P(r,r)=r!个S中的r排列。而且S中的任一r排列都可恰好通过将S中的某一r组合排序而得到。所以，有，即

.显然，有⑴，；⑵(r>n).

例6.13

系里欲将6名保送研究生推荐给3个单位，每个单位2名，问有多少种方案？

解:推荐给某个单位的两名学生的顺序是无关紧要的，这是一个组合问题。我们先从6名学生中选出2名给第一个单位，有种选法。然后从余下的4名学生中选出2名给第二个单位，有种选法。余下的2名学生给第三个单位。每一步不同的选法对应着不同的方案，由乘法原理，共有种方案。6.3.2多重集合的排列与组合多重集合的排列前面讲的n元集合的r排列，是指从n个各不相同的元素里，每次取出r个互不相同的元素进行排列，然而在现实生活中，并不一定是对不同的元素进行排列。例如，对一组数据排序就是求它的一个排列，而在这些数据中可能出现相同的数。为此，我们引入多重集合的概念。多重集合同一般集合一样，是一组对象的整体，只不过不像一般集合那样必须要求集合中每个元素互不相同。例如：

M={a,a,a,b,c,c,d,d,d,d}是一个10个元素的多重集合，其中有3个a，1个b，2个c,4个d。通常，我们将M表示为

M={3·a，1·b，2·c，4·d}.一般记多重集合为

M={k1·a1，k2·a2，…，kn·an}其中，a1,a2,…,an为M中所有的互不相同的元素，ki是正整数，称ki为ai的重数,表示M中有ki个ai（1≤i≤n），ki也可以是，表示M中有无限多个ai.多重集合S的排列同一般集合的r排列一样，也是从S中选出r个元素的有序选择。定理6.12多重集合M={·a1，·a2，…,·ak}的r排列数为kr.证明:

在构造M的一个r排列时第一项有k种选择，第二项有k种选择……，第r项有k种选择。由于M中的每个元素都是无限重的，所以r排列中的任一项都有k种选择，且不依赖于前面已选择的项，故M的r排列数为kr.由上面的证明易知，若M中每个元素的重数至少为r，则定理的结论仍然成立。定理6.13多重集合M={k1·a1，k2·a2，…，kn·an}的全排列数为证明:集合M中共有k1+k2+…+kn个元素，a1占集合M的全排列中的k1个位置，选取a1所占位置的方法数为；在确定了k1个a1的位置后，还有k2+…+kn个位置，a2,占其中的k2个位置，从中选取k2个a2的位置的方法数为；类似的，依次选取位置安排a3，a4，…，an，由乘法原理知，M的全排列数为

例6.14求不多于四位的二进制数的个数。解:此问题相当于多重集合的4排列问题，由定理6.12知，所求的二进制数个数为24＝16.例6.15设S={3·a,2·b,4·c},求S的8排列的个数。解:S的8排列可分为以下三类：⑴{2·a,2·b,4·c}的8排列，数目为⑵{3·a,1·b,4·c}的8排列，数目为⑶{3·a,2·b,3·c}的8排列，数目为因此S的全部8排列的个数为

420+280+560＝1260多重集合的组合多重集合M的r组合是指从M中无序的选出r个元素。定理6.14多重集合M＝{·a1,·a2,…,·ak}的r组合数为

.证明:设多重集合M的某个r组合为

{x1·a1,x2·a2,…,xk·ak},（6.3.1）则有x1+x2+…+xk=r，（6.3.2）其中，x1,x2,…,xk为非负整数。反之，若给出方程（6.3.2）的一组非负整数解x1,x2,…,xk，则对应与M的一个r组合（6.3.1）。所以M的r组合与方程（6.3.2）的非负整数解构成一一对应，从而将求M的r组合的问题化为求方程（6.3.2）的非负整数解。方程x1+x2+…+xk=r的一个非负整数解可以表示成长为k-1+r的0,1序列

00…0，其中，0的个数为k-1个。该0,1序列是集合{(k-1)·0,r·1}的一个全排列。方程（6.3.2）的解与集合{(k-1)·0,r·1}的全排列之间是一一对应的，从而多重集合M的r组合数为

例6.16方程：x1+x2+x3+x4=20的整数解的个数是多少？其中

x1≥3，x2≥1，x3≥0，x4≥5

解：我们引入新变量

y1=x1-3,y2=x2-1,y3=x3,y4=x4-5此时方程变为

y1+y2+y3+y4=11诸xi的下界能够满足当且仅当这些yi是非负的。新方程的非负整数解的个数是同理我们可知含有k种元素且重数为n1，n2，…，nk的多重集

S={n1·a1,n2·a2,…,nk·ak}的r-组合数和方程

x1+x2+…+xk=r的整数解的个数相同，其中

0≤x1≤n1,0≤x2≤n2,…,0≤xk≤nk.6.3.3二项式系数表达式表示n元集合的r组合数，它具有许多很奇妙的性质，关于它有许多恒等式。由于它出现在下面所介绍的二项式定理中，所以称其为二项式系数。在进行产生计算机算法分析时，经常要用到二项式系数，因此有必要对其熟练掌握。定理6.15（二项式定理）设n为一正整数，则对任意的x和y，有证明：将展开，直到没有括号为止。在展开时，每个因子中均可取x或y，因而共有2n项，这些项都可以写成xryn-r(0≤r≤n)的形式。我们可以在n个x+y因子中选出r个，从这r个因子中取x，而在另外的n-r个因子中取y，如此得到xryn-r项，所以xryn-r的系数等于n个因子的组合数，即.因此

推论n为一正整数，则对任意的x，

证明：只要在二项式定理中令y=1即可。二项式系数的基本性质当n,r均为非负整数，且n≥r时，有一些最基本的性质：（1）对称关系；（2）递推关系

(n≥r≥1)；注意：在证明二项式系数的性质或恒等式时，一般可利用下面三种方法。

1）用二项式系数的表达式。

2）利用二项式系数的组合意义。

3）利用二项式定理。性质（1）对称关系的证明。证一：利用二项式系数的表达式证二：利用二项式系数的组合意义表示n元集合A的r元组合数，或表示n元集合的r元子集的个数。同理，表示集合A的n-r元子集的个数。设A1是A的r元子集，则A-A1是A的n-r元子集，且这种关系显然是1-1对应的。所以A的r元子集地个数等于A的n-r元子集的个数。因此证三：利用二项式定理同理

=，所以=因此性质（2）递推关系，(n≥r≥1)的证明。利用的组合意义来证：N元集合的r元子集可以分成两类：第一类r元子集含

，第二类r元子集不含

。第一类r元子集中的任一个去掉

后，就是的r-1元子集；反过来，任给一个的r-1元子集，添上后就是A的r元子集，故二者之间有一一对应关系。因而，第一类r元子集共有。第二类r元子集就是的r元子集，共有个。所以

(n≥r≥1)；由性质（2）可得图6.3所示的著名的杨辉三角形。许多关于的性质都可以通过仔细考察杨辉三角形而得到。例如（3）单峰性当n为偶数时，有

当n为奇数时，有

组合恒等式有关二项式系数的恒等式至今已发现的就有上千个，而且还在不断的发展。这些组合恒等式在许多算法分析中起着重要的作用，这里给大家介绍常用的几个。等式1证明：在二项式定理中令x=y=1即可。等式2证明：在在二项式定理中令x=-1,y=1,得

将上式整理一下即得等式2.由等式1，可推得：且推得：等式3证明：对等式等式两边在x=1处求导数，得6.4.1递推关系实例例6.17Hanoi塔问题现有A，B，C三根立柱以及n个大小不等的中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.3所示。要把n个圆盘从A柱上搬到C柱上，并保持原来的顺序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上。问至少要搬多少次？解：记T(n)为n个圆盘从A柱搬到C柱所需的最小次数。整个搬动过程可以分成三个阶段：（1）将套在A柱上面的n-1个圆盘从A柱按要求搬到B柱，搬动次数为T(n-1);（2）把A柱上最下面的那个圆盘搬到C柱上，搬动次数为1；（3）把B柱上的n-1个圆盘按要求搬到C柱上，搬动次数为T(n-1).由加法原理知:T(n)=2T(n-1)+1,又T(0)=0，所以有如下带有初值的递推关系：

例6.18Fibonacci数列序列1，1，2，3，5，8，13，21，34，…中，每个数都是它前两者之和，这个序列称为Fibonacci数列。它在算法分析和近代优化理论中起着重要作用，又具有很奇特的数学性质。该数列来源于1202年由意大利著名数学家Fibonacci提出的一个有趣的兔子问题：有雄雌一对小兔，一个月后长大，两月起往后每月生（雄雌）一对兔。小兔亦同样如此。设一月份只有一对小兔，问一年后共有多少对兔子？更一般此问题可以变为n个月后共有多少对兔子？将开始有的一对小兔的月份视为第一个月，用Fn表示在第n个月的兔子数，显然F1=F2=1.其次，可以看出：Fn=前一个月兔子数+本月新增兔子数=Fn-1+Fn-2因为只有前两个月的兔子到本月恰好能生出一对小兔。所以{Fn}定解问题为6.4.2递推关系求解我们先讨论一元常系数线性齐次递推关系的求解。一元常系数线性齐次递推关系是指形如：H(n)=a1H(n-1)+a2H(n-2)+…+akH(n-k)其中n=k，k+1，…；a1，a2，…，ak是常数；ak≠0的递推关系。对上述递推关系，只需初始值H(0),H(1),…,H(k-1)给定，就可唯一确定，故递推关系称为k阶的。上式也可以写成H(n)-a1H(n-1)+a2H(n-2)+…+akH(n-k)=0(*)我们称方程为递推关系(*)的特征方程。它的k个根q1,q2,…,qk称为该递推关系的特征根。其中qi(i=1,2,…,k)是复数。不难看出，因为ak≠0，所以0不是递推关系(*)的特征根。引理6.1设q是一个非零的复数，则H(n)=qn是递推关系(*)的一个解当且仅当q是它的一个特征根。证明：H(n)=qn是递推关系(*)的解

qn-a1qn-1-a2qn-2-…-akqn-k=0

qn-k(qk-a1qk-1-a2qk-2-…-ak)=0

qk-a1qk-1-a2qk-2-…-ak=0(q≠0)

q是递推关系(*)的特征根。引理6.2设h1(n)和h2(n)是递推关系(*)的两个解，c1和c2是任意常数，则c1h1(n)+c2h2(n)也是递推关系(*)的解。证明：把c1h1(n)+c2h2(n)代入(*)式的左边得[c1h1(n)+c2h2(n)]-a1[c1h1(n-1)+c2h2(n-1)]-…-ak[c1h1(n-k)+c2h2(n-k)]=[c1h1(n)-a1c1h1(n-1)-…-akc1h1(n-k)]]+[c2h2(n)-a1c2h2(n-1)-…-akc2h2(n-k)]=c1[h1(n)-a1h1(n-1)-…-akh1(n-k)]+c2[h2(n)-a1h2(n-1)-…-akh2(n-k)]（h1(n)和h2(n)是(*)的解）=0所以c1h1(n)+c2h2(n)是递推关系(*)的解。由两个引理可以知道，如果q1,q2,…,qk是递推关系(*)的特征根，且c1,c2,…,ck是任意常数，那么

H(n)=c1q1n+c2q2n+…+ckqkn是递推关系(*)的解。如果对于递推关系(*)的每个解h(n)都可以选择一组常数c1’,c2’,…,ck’使得

h(n)=c1’q1n+c2’q2n+…+ck’qkn成立，则称c1q1n+c2q2n+…+ckqkn是递推关系(*)的通解，其中c1,c2,…,ck为任意常数。定理6.15设q1,q2,…,qk是递推关系(*)的k个互不相同的特征根，则

H(n)=c1q1n+c2q2n+…+ckqkn是递推关系(*)的通解。证明：由前面的分析可知H(n)是递推关系(*)的解。设h(n)是这个递推关系的任意一个解，则h(n)由k个初值h(0)=b0,h(1)=b1,…,h(k-1)=bk-1唯一地确定，所以有

如果方程组有唯一解c1’,c2’,…,ck’，这说明可以找到k个常数c1’,c2’,…,ck’使得h(n)=c1’q1n+c2’q2n+…+ck’qkn成立，从而证明了c1q1n+c2q2n+…+ckqkn是该递推关系的通解。考察此方程组，把它写成矩阵形式

它的系数矩阵是著名的范德蒙矩阵，因为当i≠j时，qi≠qj，可以证明系数矩阵是满秩矩阵，这也就是说方程组有唯一解。例6.19

求解Fibonacci数列的递推关系解：这个递推关系为常系数线性齐次递推关系，其特征方程是x2-x-1=0，特征根是，所以通解是因为，代入初值来确定c1和c2，得到方程组解这个方程组得,所以满足初值条件的特解是

n=0,1,….

对于k阶常系数线性齐次递推关系，当特征根q1,q2,…,qk都不相等时，我们已经给出了求通解的方法。但是当q1,q2,…,qk中有重根时，这种方法就不适用了。例6.20

求解递推关系：解：它的特征方程是x2-4x-4=0，特征根是q1=q2=2。由定理6.15可知2n是它的解。但必须找一个与2n线性无关的解，不妨尝试n2n，把它代入原递推关系得

n2n-4(n-1)2n-1+4(n-2)2n-2=n2n-(n-1)2n+1+(n-2)2n=2n[n-2(n-1)+(n-2)]=0.这说明n2n也是解，且它与递推关系的另一解2n线性无关，所以原递推关系的通解是

H(n)=c12n+c2n2n实际上设递推关系：

H(n)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0(n≥k，ak≠0)的特征方程是

xk-a1xk-1-a2xk-2-…-ak=0令

P(x)=xk-a1xk-1-a2xk-2-…-ak，

Pn(x)=xn-kP(x)=xn-a1xn-1-a2xn-2-…-akxn-k如果q是P(x)的二重根，则q也是Pn(x)的二重根，那么q也是Pn(x)的微商的根，其中

=nxn-1-a1(n-1)xn-2-a2(n-2)xn-3-…-ak(n-k)xn-k-1因此q是