错位排列问题:有趣的排列组合与概率问题(二)

错位排列问题:有趣的排列组合与概率问题(二)错位排列问题也是很经典的问题 五封标号为 1 5 的信放进 5 个编号为 1 5 的信笺里面 若信的编号与信笺的编号都不相同 一共有多少种不同放法 更一般的是 n 封标号为 1 n 的信放进 n 个编号为 1 n 的信笺里面 若信的编号与信笺的编号都不相同 一共有多

欢迎大家来到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

(0)
上一篇 12小时前
下一篇 12小时前

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信