错位排列组合原理(错位排列问题公式)

在生活中，很多人可能想了解和弄清楚错位排列问题：有趣的排列组合与概率问题（二）的相关问题？那么关于错位排列组合原理的答案我来给大家详细解答下。

错位排列问题也是很经典的问题：五封标号为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，它是个线性递推式，也是可以求出通项公式的，读者感兴趣可以自行推导。

温馨提示：通过以上关于错位排列问题：有趣的排列组合与概率问题（二）内容介绍后，相信大家有新的了解，更希望可以对你有所帮助。