错排问题

（浙江理科.2010.17）有4位同学在同一天的上午和下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”等五个项目的测试，每位同学上午和下午各测试一个项目，且不重复。若上午不测“握力”项目，下午不测“台阶”项目，其余项目上午和下午都各测试一人，则不同的安排方式共有________种。（用数字作答）

        先吐槽一句，引号之间不该用顿号连接。

        枚举自然不在话下，关键在于有无一通用的思路。

        个有序的元素应有个不同的排列，若存在一个排列使得所有的元素均不在原来的位置上，则称这个排列为错排。

        错排问题

        涉及的问题，我们考虑数列递推解题。

        显然有，。

        对于中的第个元素，不妨设其对应第个元素（），这共有种情况。然后考虑以下两种情况：

        ①第个元素同时对应第个元素，即为剩下（）个元素错排，有种情况。

        ②第个元素并不同时对应第个元素，仔细一想，会发现这等价于个元素错排（一定要仔细想，精髓在此），有种情况。

        所以，根据加法原理与乘法原理，我们得到：

        这是这一问题的核心等式。

        下面进行数列推导。

        该数列前几项为：

        有意思的是，该数列还有一个简化公式：

        也就是说，四舍五入的结果。

        不妨进行程序验证。

        结果如下：

        其实这个公式只是个障眼法。由的麦克劳林展开式，我们有：

        令，得

        代入即得到

        其中，根据拉格朗日余项知：

        有：

另一种采用容斥原理的证明

        简单证明如下：

        设为的排列，则

        回到原题，考虑两方面：

        ①上午测台阶，下午测握力发生在同一位同学身上，等价于3人错排，采用先分堆再分配的方法，计算得

        ②上午测台阶，下午测握力没有发生在同一位同学身上，等价于4人错排，仍采用先分堆再分配的方法，计算得

        共种。

        关于泰勒展开的基础说明，详见以下文档。