欢迎大家来到IT世界,在知识的湖畔探索吧!
错位排列问题也是很经典的问题:五封标号为1~5的信放进5个编号为1~5的信笺里面,若信的编号与信笺的编号都不相同,一共有多少种不同放法?
更一般的是:n封标号为1~n的信放进n个编号为1~n的信笺里面,若信的编号与信笺的编号都不相同,一共有多少种不同放法。数学家欧拉研究过这个问题,就是用的构造递推式的方法。
设A、B、C、……代表n个信封,a、b、c、……代表n份写的信,假如a错装到B中,考虑在这个情境下多少种错装法。可以分为两类:第一类是b装入A中。有多少种错装方式?这时剩下的n-2封信的错装与A和B无关。设n封信错装法有f(n)种,则在第一类的情况下,错装方式有f(n-2)种;第二类是b不装入A中,这相当于n-1封信的错装,于是错装方式有f(n-1)种。这样,在a装入b中的情况下,总共有f(n-2)+f(n-1)。a可以装到B也可以装到C、D……,所以n封信错装方式:
接下来就是由这个递推式求通项公式。
易知f(2)=1,f(1)=0,则
可以看到这个通项公式是用级数表示的,对幂级数了解的人会知道n趋近于无穷时,括号里面这个级数代表的正是1/e 。
接下来是个看起来很简单的问题: 一个楼梯共10个台阶,如果规定一步登一个台阶或登两个台阶,一共有多少种不同的走法?
很多同学看到这个问题,通常的思路是,按照登两个台阶的次数来分类:可以是0、1、2、3、4、5,0对应的是全部用登一个台阶的方式,5对应的是,全部用登两个台阶的方式,5次可以登上10个台阶。按照这个分类:
情况0:种数是1
情况1:种数是
情况2:种数是
……
全部加起来就是:
推广到n个台阶就是
这里是无穷级数,我用的组合数是广义的组合数,不了解广义组合数和牛顿二项式的戳这篇牛顿二项式:牛顿刻在墓碑上的公式,例如:
和上面的问题一样,也是用级数来表示。而如果我换种方法来做,会得到答案的另一种表达方式。看看里面是否存在递推关系。登10级台阶可以这样来思考,第一类是先登九级,最后用登一个台阶的方式完成;第二类是先登8级,最后用登2个台阶的方式完成。
设f(n)为登n级台阶的种数,那么就有:
而且f(1)=1,f(2)=2。到这儿来就会发现,这不就是斐波拉契数列吗?只不过与斐波拉契数列相比,这个数列的第1项是斐波拉契数列的第二项,根据斐波拉契数列的通项公式,可以写出
这样答案的另外一种表达形式,可以看到相对于上面用级数的形式来表达,这个表达形式才是才我们通常意义上说的通项公式,就是表达成n的初等函数的形式,于是
回忆前面的错位排列问题,我们用递推式好像并没有求出一个可以用n的初等函数表示的式子而是
所以有些级数可能并没有和函数。把这个问题还可以推广,例如 一个楼梯共10个台阶,如果规定一步登一个台阶或登三个台阶,一共有多少种不同的走法?
这时候递推式就变为f(n)=f(n-1)+f(n-3), n>3,它是个线性递推式,也是可以求出通项公式的,读者感兴趣可以自行推导。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/99969.html