本文将从题目出发，以问题为导向，先介绍错位排列的情景及研究方法，再给出其递推公式及通项公式的证法，最后给出子阶乘的定义及性质若干。（可以大幅度简化计算）

题目 有共个人，他们的座位分别为。现要求一个人只能坐一个座位，且都不坐自己座位，设数列为其不同的方法种数，试求其递推公式及通项公式。

【解析】. 先来计算递推公式，考虑应用分步乘法原理，将选座位分为两步：
(i)

选座位：根据题意，除了自己的不能选，其他位置均可选择。故有种选择。假设选择了座位；
(ii)选座位：应用分类加法原理，分为两类：
a. 若选择座位，则接下来的问题转化为“个人不选自己座位，有多少种选法？”，即种数为；
b. 若不选座位，则可将看作原来的那个不能选的座位，此时的问题就化归为“个人不选自己座位，有多少种选法？”，即种数为。
综合上述分析，则

再来计算通项公式，这就没有上面计算递推公式那么简单且愉快了。我们不从递推公式推通项，而是从头考虑问题。

记满足坐自己的座位条件的集合为，记表示集合A元素的个数。则原题转化为求

在这里就需要运用容斥原理进行进一步的转化。

定理1（容斥原理）. 容斥原理是集合元素计算的一个重要方法。针对不同的形式，可以采取不同的容斥原理形式，这里介绍常用的两种（为了内容的连续性，证明将在附录中给出）：

容斥原理Ⅰ：设为个不同的集合，则有

此公式称为容斥分式，可以看作是加法原理的推广；

容斥原理II：设为有限集（全集）的子集，在全集下的补集，则有

此公式称为筛法公式，是容斥分式的直接推论。

则由筛法公式可将原式化为

在本题的情景下，全集的元素数$|\bm{I}|$即为$n$的全排列$n!$。

考察展开式中由个取交集的项。令为的含个元素的子集（），则任意个取交集而形成的集合可表示为，简记为，一共能取出个这样的集合。由于轮换对称性，只要一定，所有这样取出的集合的元素个数都应相等\vspace{0.5em}，且等于“个人排位，其中有个人的位置一定（坐在自己的位置），其余个人全排列”的种数，即

而由上文提到，一共能取出$C_{n}^{k}$个这样的集合。故式中由$k$个$F_i$取交集的项

例如，当时，有，而这样由3个取交集而形成的集合一共有个，故

通过一个例子，你现在理解了展开式中的其中一项。让我们对其继续化简

故原式

即

【答案】.

【注】.

1. 题目中的错位排列问题，定义为没有物体出现在其自然位置上的个物体的排列的数量。记其通项为，读作“子阶乘”。满足递推公式和通项公式；
2. 子阶乘的快速计算方法：M. Hassani在2004 年 10 月 28 日的私人通信中给出了以下形式：
   

   其中为是最接近整数函数（四舍五入），为向下取整函数。

3. 唯一的素数子阶乘是 ，唯一等于其数字的子阶乘之和的数字是；
4. 子阶乘可以解析延拓到复平面，如下图所示：
   
5. 容斥原理的有关证明：

证明. 用数学归纳法证明容斥分式：
(i)当

时，显然成立；
(ii)若其对于成立，即

则对于时

也成立。

综上所述，由(i)(ii)可知，成立。

再由容斥分式推出筛法公式：