组合数学 第二章第三节

1,第2章递推关系与母函数,2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列2.4优选法与Fibonacci序列的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于常系数非齐次递推关系2.8整数的拆分2.9ferrers图像2.10拆分数估计2.11指数型母函数2.12广义二项式定理2.13应用举例2.14非线性递推关系举例2.15递推关系解法的补充,2,2.7关于线性常系数非齐次递推关系,如下面的递推关系：,称为k阶线性递推关系，其中若c1,c2,ck都是常数，则称为常系数线性递推关系，若bn=0，则称为是齐次的，否则为非齐次的。,3,2.10任意阶齐次递推关系,设r1,r2,rs是线性常系数齐次递推关系,的不同的特征根，并设hi是ri的重根数，i=1,2,3,s。则,4,Fibonacci递归算法:,intfibonacci(intn)if(n=1|n=2)return(1);elsereturn(fibonacci(n-1)+fibonacci(n-2);,2.1递推关系,时间复杂性：f(n)=f(n-1)+f(n-2)+1,5,2.7关于线性常系数非齐次递推关系,如果序列xn和yn满足非齐次递推关系，,对应的齐次递推关系。,则序列zn=xn-yn满足其对应的齐次递推关系。,证明：略,6,2.7关于线性常系数非齐次递推关系,特解与一般解:,例2：某人有n元钱，一次可买1元的矿泉水，也可以买2元的（啤酒、方便面）的一种，直到所有的钱花完为止(买东西的顺序不同，也算不同方案)，求n元钱正好花完的买法方案数。,解：递推关系：an=an-1+2an-2a1=1,a2=3,特征方程x2-x-2=0的根r1=-1，r2=2,7,定理1若fn是线性常系数非齐次递推关系的特解，则这个线性常系数非齐次递推关系的解有如下形式：an=fn+对应的线性常系数齐次递推关系的解。,证明：fn是特解，设sn是一个解,令tn=sn-fn,2.7关于线性常系数非齐次递推关系,则序列ti是线性常系数齐次递推关系的解,sn=tn+fn证毕,8,2.7关于线性常系数非齐次递推关系,一阶、二阶线性常系数非齐次递推关系,(1)右端项为常数h,an+ban-1=c(n),(2)右端项为hmn,h为常数，m为已知整数。,an+ban-1+can-2=c(n),9,下面讨论若干特殊右端项的找特解的办法。,(1)猜解法:,猜an解的可能情况?,2.7关于线性常系数非齐次递推关系,an+ban-1=hmn,h为常数，m为已知整数。,10,下面讨论若干特殊右端项的找特解的办法。,(1)猜解法:,设an=kmn,2.7关于线性常系数非齐次递推关系,an+ban-1=hmn,h为常数，m为已知整数。,kmn+bkmn-1=hmn,km+bk=hm,m等于-b时无效,m是特征方程的根时无效,11,设an=kmn,2.7关于线性常系数非齐次递推关系,an+ban-1+can-2=hmn,h为常数，m为已知整数。,kmn+bkmn-1+ckmn-2=hmn,km2+bkm+ck=hm2,分母为零时无效,m是特征方程的根时无效,12,例1,假定特解为：,两边同除以4n-2：,2.7关于线性常系数非齐次递推关系,13,特征方程,2.7关于线性常系数非齐次递推关系,14,例2,假定特解为：c3n,代入递推关系。,无解！对于这种情况怎么处理?,2.7关于线性常系数非齐次递推关系,15,故导致二阶齐次递推关系，（1）式的解必然是（2）式的解，但（2）式解不一定是（1）式的解。,(2)划为高阶齐次递推关系，通过比较推测递推关系的特解,an-ban-1=hmn,an-1-ban-2=hmn-1,an-ban-1=hmn,(1)man-1-mban-2=hmn,an-(b+m)an-1+bman-2=0（2）,2.7关于线性常系数非齐次递推关系,16,若b=m,则解为:,（2）式的特征方程是：x2-(b+m)x+bm=0,它有两个特征根b和m。,若bm,则解为:,2.7关于线性常系数非齐次递推关系,an=k1bn+k2mn,an=(k1+k2n)mn,17,分别讨论如下：,(a)若bm,则an-ban-1=hmn的解必可写成如下形式。an=k1bn+k2mn,定理1可知，非齐次递推关系的解可表示为齐次递推关系的解加上特解fn。,比较可得：fn=k2mn,k2是待定系数，,代入递推关系an-ban-1=hmn，k2mn-bk2mn-1=hmn,k2=hm/(m-b),因此fn=hm/(m-b)mn是特解,2.7关于线性常系数非齐次递推关系,18,解:,2.7关于线性常系数非齐次递推关系,例3:,19,(b)若b=m,即an-ban-1=hbn其中b和h都是已知常数。,但当b=m时，对应的二阶齐次递推关系an-(b+m)an-1+bman-2=0的解为：an=(l+kn)bn,2.7关于线性常系数非齐次递推关系,所以fn=knbn令an=knbn，an-1=k(n-1)bn-1代入递推关系。knbn-k(n-1)bn=hbn,则kn-k(n-1)=h,k=h,20,2.7关于线性常系数非齐次递推关系,例4:,21,因此：,那么特解为：,例5：,特征方程为：,与所对应的二阶齐次递推关系的解比较:,2.7关于线性常系数非齐次递推关系,22,将其代入非齐次递推关系，得,可得k=3/5,因此特解为：,2.7关于线性常系数非齐次递推关系,23,例6：,2.7关于线性常系数非齐次递推关系,假设特解,无解,24,例6：,2.7关于线性常系数非齐次递推关系,假设特解,25,定理2对于如下非齐次递推关系。,的特征方程：,的m重根，则递推关系的特解有以下形式：,若b(n)是p次多项式，如果r是线性齐次递推关系，,2.7关于线性常系数非齐次递推关系,若r不是K(x)=0的根，则特解是m=0时的形式。,26,例7an+3an-1-10an-2=(-7)nn,对应的特征方程,有两个特征根：2和-5，-7不是特征根，故m=0，按定理，他的特解可写为：,代入递推关系式：,2.7关于线性常系数非齐次递推关系,27,特解:,因此一般解为：,2.7关于线性常系数非齐次递推关系,28,例2.43an-3an-1+2an-2=6n2，a0=6,a1=7,右端项6n2可以看作是(1)n6n2,有两个特征根：1和2。,m=1,p=2,代入递推关系求出系数：,2.7关于线性常系数非齐次递推关系,*,29,例题1:求长度为n的0,1符号串，不出现00的符号串总数。,考虑一行n列方格，用红蓝两种颜色染色，不允许两红色方格相邻。,2.7关于线性常系数非齐次递推关系,30,66.求矩阵,设第n-1项的乘积为,解：,2.7关于线性常系数非齐次递推关系,31,只要求出K即可,2.7关于线性常系数非齐次递推关系,32,bm时,代入初值得k=1,2.7关于线性常系数非齐次递推关系,33,64.从n个文字中取k个文字作允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。,2.7关于线性常系数非齐次递推关系,64.从k个文字中取n个文字作允许重复的排列，但不允许一个文字连续出现3次，求这样的排列的数目。,34,首先，假设取n个文字作允许重复的排列，不允许一个字连续出现3次的排列数为an,假设取n-1个文字最后一位为