【排列组合】错位全排列的简化计算公式

一、错位全排列问题

什么是错位全排列问题？其实很简单，在生活中可能都会遇到：

“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(Danid Bernoulli，1700－1782)提出来的，大意如下：
一个人写了  封不同的信及相应的  个不同的信封，他把这  封信都装错了信封，问都装错信封的装法有多少种？

为了解决这个看似简单的问题，我们从数学的角度出发，尝试几个常用的方法。

记装错  封信的种类为  ，并且有  封信 

（1）枚举法（Enumeration method）计算种数

当  的值较小时，可以利用枚举法：

 时，不可能装错信，则  ；

 时，显然装错信时，只可能为两者调换位置，则  ；

 时，有  ，  两种装法，则  ；

 时，装法如下：

 ，  ，  ， ，  ，  ， ，  ，  ，则  。

当  的值越来越大时，枚举会变得异常复杂。可以考虑用排列数（Permutation）和组合数（Combination），来得到错位全排列的计算公式。

（2）排列组合计算种数

显然，  封信的组合方式共有  种装法，接下来我们要做的就是扣掉其中重复的种类，保证计数“不重不漏”。

假设第一封信装对，即为剩下的  个元素的一个全排列（All permutation），则有  种装法；并且当第二封信装对时，也有  ，以此类推，每一封信装对时，都有  种装法。

但是并不是只需扣掉装对一封信的情况。当第一封信和第二封信同时装对的时候，就出现重复了。要扣掉重复的元素，就需要应用到高中课本中没有提到的“容斥原理”。

注：在部分材料上，排列数  也被写作  。

二、容斥原理（Principle of inclusion-exclusion）

在计数时，必须注意没有重复，没有遗漏。
为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：
先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

容斥原理一般用在计算集合（Aggregate）的元素个数中。

（1）两个集合的容斥原理

设有两个非空集合  ，记  为集合  中元素的个数，则有如下关系：

这在文氏图（Venn diagram）中其实是显然的：要计算集合  的元素的个数，首先把两集合  和  的元素个数相加。但是中间出现了重复的部分，也就是集合 的元素个数，要从中扣除。

因此便有公式  。

（2）三个集合的容斥原理

推广到三个集合的情况下，公式要稍加变形：设有三个非空集合  ，则有如下关系：

参照上面的分析，这个关系也是显然的，但是多考虑到了集合  的元素个数。

（3）多个集合的容斥原理

推广到  个集合  中，有如下关系：

在这里记  ， 

简化后得到  ，此即为容斥原理。

三、一般计算公式

容斥原理是在集合中应用的，因此我们需要将“错位全排列”问题“翻译”一下。

设元素  的一个排列为  ，使  的全排列的集合记为  ，则  ，接下来只要算出  即可。

注意到当有一个元素“排对”时，剩下的  个元素进行全排列得到 

 ，并且这样满足要求的集合组共有  个；

当有两个元素“排对”时，剩下  个元素进行全排列得到  ，并且这样满足要求的集合组共有  个；

以此类推，到最后全部“排对”时， ，这样满足条件的集合组只有  个。

因此 

注意到对于  ， 

因此 

所以 

从上面我们得到的  的公式就会发现，为了计算错位全排序，还需要计算多次阶乘。

当  越来越大的时候，计算器通常都会受不了，是否有方法可以简化计算？

四、级数（Series）与麦克劳林公式

注意到在上面的公式当中，出现了这样的式子：  。

记  ，我们用计算器来估计一下  的值。

当  时，  ；当  时，  ；

当  时，  。

当  时，  ，取对数得  ，因此  。

当 的值越来越大的时候，  的值也会越来越接近  。

事实上，在高等数学当中，函数  的麦克劳林公式（Maclaurin's series）如下：

麦克劳林公式是泰勒公式（Taylor's formula）的一种特殊形式。
数学中，泰勒公式是一个用函数在某点的信息描述其附近取值的公式。如果函数足够平滑的话，在已知函数在某一点的各阶导数值的情况之下，泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的邻域中的值。泰勒公式还给出了这个多项式和实际的函数值之间的偏差。
泰勒公式得名于英国数学家布鲁克·泰勒。他在1712年的一封信里首次叙述了这个公式，尽管1671年詹姆斯·格雷高里已经发现了它的特例。拉格朗日在1797年之前，最先提出了带有余项的现在形式的泰勒定理。

在原本的公式中，本应该有余项，表示估计的误差大小：

 ，当  增大时，余项  趋近于  。

代入  得： 

即  ，因此  ，从这里出发，可以得到以下的估计公式。

五、估计公式

由以上的级数，可以得到  ，但是由于麦克劳伦公式是有一个“余项”存在的，总会有一定的误差。那么误差有多大呢？

记  ，接下来同样借助计算器来估计误差。

当  时，  ，而 

当  时，  ，而 

当  时，  ，而 

当  时，  ，而 

当  时，  ，而 

当  时，  ，而 

当  时，  ，而 

从上面的数据可以看出， 的值实际上是  四舍五入的结果。因此可以将  改写成： ，其中  表示不超过  的最大整数。

所以得到估计公式： 。

在平常计算当中，使用此公式可以大大缩短计算时间，非常便利。

六、一点小补充

评论区有人提到，在求  的时候可以用到递推的方法。

当  时，考虑  个元素  ，  ，  ，  ，根据题目要求，我们知道  不能放在第  个位置，故一共有  种选择。假设  放在第  个位置，考虑元素  ，有两种情况。

若  与  调换位置，则只需考虑剩下  个元素错位全排列的情况。

若  不放在第  个位置，则  也无法放在第  个位置，因此只需考虑剩下  个元素错位全排列的情况。根据加法原理和乘法原理，可以得到：  。

又  ，  ，于是可以用数学归纳法证明  。

或是可以采用以下方法： 

 ，令  ，则  ，且  ，迭代得  。

因此  ，累加得  ，因此可以得到通项公式为 。

另外，

@酱紫君

 指出，近似计算的话直接对  渐近展开,  阶是  , 一阶是  ，注意到 和  的斯特林展开是等价的，也可以得到上面类似的结果。