递推关系的求解及其应用-组合数学

《组合数学》课程结课作业题目递推关系的求解及其应用院系控制与计算机工程学院专业班级学生姓名学号2018年5月摘要递推关系作为数学的一种思维，充分的展现了生活中许多事物现象变化所遵循的规律。所有的事物都不是单一存在的，而是和某些东西相互依存的。比如在求解排列组合、数列中都会用到递推关系的思想与方法。本论文将围绕着递推思维及求解在数列、排列组合上的应用展开讨论。本论文阐述递推关系不是单一的个体，它与生成函数、线性关系、数列组合综合使用，并到达解决问题的思想。也说明学科之间是一个统一的整体。关键词：递推关系;求解方法;递推思维;应用1绪论递推关系几乎在所有的数学领域中都占据着重要的比例和广泛应用,在物理学上也有着深刻的影响，是数学运算中的一个强有力的工具。因此不管是在教学中还是生活中，都可能要用递推关系来解决所碰到的问题，或与其他学科相结合形成性学科的过程中用递推关系，比如递推关系可和数列、线性规划与矩阵相结合形成要实现这一目的新学科，把所学的知识串连在一起，形成一种新的思维。首要的关键是用递推方法来探究这一过程，搭建一桥梁。在此基础上才能用所学的递推理论和方法进行分析和应用，从而才能解决实际理论的问题，是我们所学的知识更上一个台阶。通常情况下递推关系的求解比较困难，仅局限于使用递推关系的一些定义很多问题是不能解决的，并且所涉及的领域也很广。递推关系的研究还可以追溯到斐波纳契关系：它是比萨的数学家Leonardo在1202年给出的。在他所著的《Liberbaci》一书中，讨论一个一年之内能有多少对兔子的问题，都用到了递推关系的思想。比如常见的线性递推数列，生成函数都是数学中的重要概念,也是解决数学问题的重要工具之一。本文主要介绍线性递推数列通项公式的求解方法及利用生成函数来求解递推关系，以及递推关系的推广。2线性递推关系数列na必须有连续个k项满足),,,(21nknknknxxxfx，满足此式的数列则叫它为数列nx的一个递推关系式。由递推关系式及满足k个初始值可以确定的一个数列nx叫做递推数列。因此，无论是牵涉到递推数列的证明题，解析题，还是需要建立递推关系式的综合题，那么解决递推数列的核心是求通项公式，也是最基本的步骤。2.1线性递推数列的相关认识定义1如果已知数列na的第1项（或前几项），且数列na的任意一项与它的前一项1na（或前几项）间的关系可以用一个式子来表示，对于任意的自然数n，由递推关系),,,(21nknknknaaafa所确定的数列na则叫做递推数列1。例2.1求解递推关系17nnaa其中9812an且。解：这是nnaa71其中0n且982a的另一种描述形式。于是解具有形式).7(0nnaa因为),7(98202aa于是,20a而且),7(2nna是唯一解。定义2若数列na从第k项以后的任意一项都是其前k项的线性组合，即nkknknknararara2211（1）其中,n是任意的自然数，krrr,,,21是常数，且0kr那么称na为k阶的线性递归数列，（1）则叫na的递归方程2。例2.2公比为q的等比数列是一阶线性递归数列它的递归方程是nnqaa1,3,2,1n，0q并且1,121aa.例2.3斐波那契数列（Fibonaccisequence）是二阶线性递归数列，它的递归方程为nnaaan12，(，4,3,2,1n)且121aa。2.2线性递推数列通项公式的求解分类我们探究线性递推数列目的就是要求出线性递推数列通项公式，然后用它来解决数学与生活中的一些问题，下面列出一些我们常见的求通项公式的方法:公式法、叠加法、叠乘法、待定系数法、迭代法、换元法、不动点法、转换法、数学归纳法等。2.3利用线性递推数列通项公式解决问题递推关系在数学这个庞大的领域，有很多问题我们是无法解决的，那么需要我们运用所学的知识，把各个知识点串联起来形成一种新的思想，达到解决问题的目的。比如在解决递推关系时我们通常利用线性递推数列的通项公式来解决一些比较复杂的问题。接下来介绍几种常见的方法。1）数学归纳法所谓数学归纳法，令)(nS代表含有一次或多次出现变元n的一个开放数学语句，其中n表示一个整正数。如果)1(S为真；并且等式成立。若一旦)(kS为真，则有)1(kS为真；那么对于所有Nn都有)(nS为真。它常用在数学上证明与自然数N有关的命题的一种特殊方法，它主要用来探究与整正数有关的数学问题，在高中数学中常用来证明等式的成立和数列通向公式的成立，接下来就用它来证明此数列是成立的。例2.4已知数列na中，)(,1,01221Nnaaaaannn,求证：数列na的第Ntt14项能被整除。证(1)当1t时，因为211,10123123aaaaaa，得312345aaa，能被3整除。（2）假设)1(kkt时。14ka能被3整除，当1kt时，4434541)1(4kkkkaaaa)()(24341424kkkkaaaa)(214241424kkkkaaaa=142423kkaa由于14ka能被3整除，故1)1(4ka也能被3整除，由（1）和（2）可知道对于一切的14,kaNt能被3整除。2）叠乘法所谓叠乘法：如12,112312naaaaaann将所有等式叠乘后就是)1(3211naan就是将中间的，432,,aaa等项消去，找到与naa与1的关系。它的目的就是找到1a与后面的关系，从而推出通项公式。叠乘法在生活中不是很常见，但是在数列中我们会经常用到它，能把复杂的问题通过相互叠乘使之化简，从而解决问题。例2.5在数列na中，)2(11,2111nannaann，求na.解：14534231211,,64,53,42,31nnannaaaaaaaaa因此用叠乘法可得出)1(1nnan3）待定系数法待定系数法，一种求未知的方法。将一个多项式表示成另一种含有待定系数的新的形式，这样就得到一个恒等式。然后根据恒等式的性质得出系数满足的方程或方程组，其通过方程或方程组可求出待定系数，或找出某些系数所满足的关系式，这种解决问题的方法叫做待定系数法。然而求数列的通项公式，最为广泛的的办法是：把所给的递推关系变形，使之成为某个等差数列或等比数列的形式，于是就可以由此推得所给数列的通项公式。求解的关健在于变形的技巧，而变形的技巧主要在于引进待定系数，接下来就看看与之相关的内容。例2.6设75,211nnxxx且，求数列的通项公。解：所给递推公式变形为，左右两边同时加m，47557),557(57511mmmmxmxmxnnn，则令于是),47(5471-nnxx由此47nx是等比数列，其首项是41547x，公比是1541547,5nnxq于是所以4754151nnx3递推关系在生活中的应用递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，递推关系如何求解。本节围绕如何求解递推关系，归类说明其广泛的应用价值．3.1染色问题问题1：将一个圆分成t个扇形(t≥2),每个扇形只能用五种不同颜色中的任意一种涂色，且相邻扇形颜色互不相同，共有多少中不同的涂法？分析：记涂法种数为Xt(t≥2)，分析Xt与t的关系，1有5种涂法，2有4种涂法，⋯，t有4种涂法（无论是否与1同色），这样共有5×4n-1种涂法。5×4n-1种涂法分两类：一类是t与1同色，另一类是t和1不同色，前者不合题意，但可看成t和1合为一个扇形，此时有涂法种数Xt-1，故递推关系为Xt+Xt-1=5×4n-1.例3.1：在六边形区域内饲养动物，要求同一区域饲养同一种动物，相邻区域饲养不同动物，现要饲养4种不同动物，则有多少种饲养方案。解：从问题1，我们知a2=12，a3=4×32-12=24，a4=4×33-24=84，a5=4×34-84=240，a6=4×35-240=732.故不同的栽种方案有732种。3.2平面分割问题问题2：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰相交于两点，任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。分析：设an为n条封闭曲线把平面分割成的区域个数，当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条封闭曲线恰好相交于两点，且不会与任何两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域，故递推关系是an=an-1+2(n-1)，初始条件是a1=1.例3.2：球面上有n(n≥3)个大圆，且任何三个都不相交于同一点，设球面被这n个大圆分成bn个部分，求bn.解：通过问题2知，在n个大圆基础上增加一个圆，产生2n个交点，在第n+1个圆上这2n个点将圆分成2n段弧，且每一段弧将原来的一块分成2块，从而有bn+1=bn+2n，且b3=8.于是有bn=b3+(b4-b3)+⋯+(bn-bn-1)=n2-n+2.3.3匹配问题问题3：在由整数1，2，i，⋯，n构成的排列中，如果i不出现在第i个位置，则这些整数的一个排列说成是它们的一个匹配。分析：记1，2，i，⋯，n这n个数匹配的个数为Xn，考虑将此n个数的匹配问题行恰当分类：若第一个位置由整数r，则第一个位置的填法有n-1种，余下的n-2个数2，3，⋯,r-1，r+1，⋯，n的排法数等价于整数1，2，⋯，n-2的匹配数，即有Xn-2种排法；第二类，如果第r个位置不是1，则填入2，3，⋯，r-1，r+1，⋯，n的排法数等价于在第2到第n位置上先错位排列2，3，⋯，r-1，r，r+1，⋯，n，而后将r改为1即可，即有Xn-1种排法，可得到递推关系式:Xn=(n-1)(Xn-1+Xn-2).例3.3：一个班有40名同学，每个同学写一封信并集中起来，然后每人从中拿一张别人写的信，则40封信存在多少种不同的分配方式？解：根据问题3，显然a1=0,a2=1,a3=2×(1+0)=2，⋯，a40=39×(38+37)=2925.故四张贺年卡的分配方式有2925种。3.4上楼问题问题4：某人上楼梯，要么每次向上走一阶，要么每次向上走二阶，如果用Xn表示该人走到第n个阶梯时所有可能的不同走法的种数，求Xn．分析：显然X1=1，X2=2.如果从最后一步走的方法来分类讨论：①若最后一步走一阶，那么该人走到第n个阶梯可能分成两步骤，先走到第n-1个阶梯，此时所有可能的不同走法有Xn-1种，再从第n-1个阶梯走一阶到第n阶梯有一种走法，从而这一类有Xn-1种；②若最后一步跨两阶，同理可得这一类有Xn-2种走法。综上所述，该人走到第n个阶梯时，所有可能的不同走法的种数：.Xn=Xn-1+Xn-2(n≥3)例3.4：假定一对兔子(雄和雌的)，从出生第二个月开始，每个月繁殖一对新的兔子，那么，从饲养第一对兔子开始起一年后有多少对兔子呢？解：根据问题4知a1=1，a2=2，a3=3，a4=5，a5=8，a6=13，a7=21，a8=34，a9=55，a10=89，a11=144，a12=233.故一年后有233对兔子。3.5传球问题问题5：X(X≥2)个人在一起相互传球，规定甲首先发球，则经过Y(Y≥2)次传球后，球再次回到甲手中的不同传球方式有多少种？分析：设经过Y(Y≥2)次传球又回到甲的手中的不同传球方式有an种，每次传球都有m-1种可能，故前n-1次传球一共有(m-1)n-1种方法，但第n-1次传球不能传给甲，而第n-1次传球给甲的方法总数即为an-1，故递推关系an=(m-1)n-1-an-1.4总结不管是数学中还是