递推关系和生成函数

《递推关系和生成函数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章递推关系和生成函数讨论内容：本章讨论涉及一个整数参数（n）的某些计数问题的代数求解方法。简言之，用代数方法求解计数问题。方法：递推关系（线性齐次/非齐次递推关系）和生成函数（&指数生成函数）；简言之，计数问题的代数表示方法。7.1某些数列数列：按一定次序排列的一列数称为数列。第1项（首项），第2项，…，第n项。如：第一节：算术序列和几何序列1、常见的序列有两种：算术序列：例如等差数列，几何序列：例如等比数列，联系：算术级数、几何级数（以表示成a*x^y，即x的y次方的形式增长。通常情况下，x=2，也就是常说的翻几（这个值为y）番）。如图：20序列求和：算术序列的部分和（等差）

2、：几何序列的部分和（等比）：20例：确定平面一般位置上的n个互相交叠的圆所形成的区域数。互相交叠&一般位置：n个圆彼此两两相较于两个不同的点，且这些点互不重叠。解：初值：推导递推关系：ln-1个圆，形成区域hn-1。l放入第n个圆，与其余n-1个圆，互相交叠（与每个圆交于两个不同点，且这些点不重叠），则一共产生了2*（n-1）个交点；则产生弧线段2*（n-1）条：p1p2、p2p3、……p2（n-1）-1p2（n-1）、p2（n-1）p1（将空白平面一分为2），每个弧线段将原来的区域一分为2；则导致新增加了2*（n-1）个区域。20所以（累加消元）：得：第二节：斐波那契数列与Pas

3、cal三角形1、斐波那契序列：0，1，1，2，3，5，8，13，21，34，55，89，144，233……即：例：兔子繁殖问题：一月：（小兔）二月：（大兔）三月：四月：20五月：解：l找初值：主要用于方便运算，在某些实际的例子中可能没有意义。l找递推关系：l累加消元：由（1-2）、（1-3）联立求解，得到：同理：当n+1时，可得：（证略）2、例：斐波那契数是偶数当且仅当n内被3整除；0，1，1，2，3，5，8，13，21，34，55，89，144，233……20偶、奇、奇、偶、奇、奇、偶、奇、奇、偶……定理7.1.1：斐波那契数列满足公式：证明：l设初值：；l由斐波那契数列的递推关

4、系：设。——————问题：为什么不设？注：符合常微分方程的格式：例如：则，原式变为：得：得通解：代入初值：20得现有斐波那契的初值：代入，满足公式：得到：例，证明同上。斐波那契数列的实际应用：例1：确定2*n的棋盘用多米诺骨牌完美覆盖的方法数解：需要n块牌，如果最后1块牌竖排（即固定住第n块牌摆放，排放其余n-1块牌），与前面n-1块牌的排法有关系，这种排法有：如果最后1块牌横排，与前面n-2块牌的排法有关系，这种排法有：所以符合斐波那契数列，在根据实际情况，求出例2：无101、也没有010的长度为n的0、1序列有多少？解：末位为0，…………11020…………00末位为1，…………

5、11…………000所以满足斐波那契数列，初值求解例3、爬楼梯问题：每次可以爬1个台阶或者两个台阶，求。经过推导，会发现，符合斐波那契数列。略，202、Pascal三角形：由图，可以很容易看出，斜对角线上的元素累加和符合斐波那契数列。K的取值，其实就是对角线上k的取值。定理7.1.2：20沿Pascal三角形左边向上对角线的二项式系数的和是斐波那契数。第n个数满足：其中是n/2的若取整。（或者写成，更容易看出就是对角线上k的取值。）更具二项式系数的性质，很容易证出：20证略。7.2线性齐次递推关系已知数列和系数满足：关于齐次与非齐次：若，叫k阶常系数线性齐次递推关系；若，叫k阶常系数

6、线性非齐次递推关系；齐次：例题：略定理7.2.1令q为一个非零数。则是常系数线性齐次递推关系的解，当且仅当q是多项式方程的一个根。如果多项式方程有k个不同的根则是下述定义下（7-20）的一般解：无论给定什么初始值，都存在常数，使得公式（7-22）满足递推关系（7-20）和初始条件的唯一的序列。证明：l证明，存在k个不同根的解：为公式（7-20）的解，当且仅当：由于：，所以存在不为0.则存在通解：推之，l证明，无论初值取何值，如果互异，不为0，则总存在常数20，使得公式（7-22）满足递推关系（7-20）设初始值：则：方程组系数行列式：范德蒙矩阵。由于，所以方程组有唯一解。定理得证。

7、定理7.2.2联系：常微分方程证明方法类似7.2.1，这里采用的是特征方程法。符合常微分方程的格式：207.3非齐次递推关系汉诺塔问题：（插入视频）借助于B，将盘从A全部移到B，保持每一步操作中，每块盘的下面一块盘都比它大。下面是移动3块盘的示意图：解法详细描述搬第n块，需要：；把剩下的n-1块搬过去，需要：；所以：迭代得出：207.4生成函数（解决组合问题）生成函数是无限可微分函数的泰勒级数（幂级数展开式）。有无穷数列：它的生成函数定义为无穷级数：若，从第m项开始，