导入
我叫追风卡洛特，复姓追风，是河中的超气人娼年小南梁.
为了让自己的腿子更健美，我今天约了同学，一共3个人去跑步.我们脱下校服放成一堆就上道了.跑完后， 每人随手抓了一件校服就穿上了，匆忙之下，所有人都没穿到自己的衣服.
请问，在此情况下一共有多少种穿衣服的方法？
如果跑步的人一共是4人呢？5人呢？10000人呢？
正片开始
导入中描述的就是典型的全错排问题.首先，有$n$个元素进行排列，每个元素均有自己对应的位置，全错排问题 就是去研究所有元素都不排在原来所对应的位置的情况总数.例如，对于(1,2,3)的全错排情形，有(2,3,1),(3,1,2)共两种.
下面，我们令$n$个元素的全错排排列总数为$a_n$，研究数列${a_n}$的通项公式.
基于容斥原理的归纳推导方法
全错排公式的推导一般有递推数列法和容斥原理法两种.但由于标题说了，选必部分我们只看了第三册，因此此处 采用容斥原理的方法.以$n=4$时的全错排为例.
首先，我们需要采用一种正难则反的思想，即先将所有可能都算出来，再减去不合题意的情况.
四种元素的排列共
$$ A_4^4=24 $$种.
接下来，容斥原理登场.这个原理，我愿称之为“加多了就减，减多了就加，加减交替，一步步地接近真实”.容易发现， 在4个元素的全部排列中，包含“有1个元素正确排列”的情况（按照容斥原理的逻辑，应从包含情况较多的集合开 始考虑），下面减去
$$ A_4^4-C_4^1A_3^3 $$其中 $C_4^1$ 代表从4个元素中选出一个正确排列，$A_3^3$ 表示剩余3个元素任意排列.下文类似逻辑不再赘述.
接着，容易发现，在“有1个元素正确排列”的情况中包含“有2个元素正确排列”的情况.也就是说，上面的操作“减多了”， 于是下面我们加回去
$$ A_4^4-C_4^1A_3^3+C_4^2A_2^2 $$同理，在“有2个元素正确排列”的情况中包含“有3个元素正确排列”的情况……以此类推，最终我们得出式子：
$$ A_4^4-C_4^1A_3^3+C_4^2A_2^2-C_4^3A_1^1+1 $$最后的“1”，表示“4个元素全部排列正确”的情况。
计算该式子，得出答案为9.
列举4种元素的全错排方式如下
(4,3,2,1),(4,1,2,3),(4,3,1,2),(3,4,1,2), (3,4,1,2),(2,4,1,3),(2,1,4,3),(3,1,4,2), (2,3,4,1)
凡9种，与计算结果相符.
此时，展开我们最后得到的式子，得到
$$ 4\times3\times2\times1-4\times3\times2+4\times3-4+1 $$观察可以发现，多项式中的第一项是$4!$，此后每一项都比前一项少个“尾巴”.
写成阶乘的形式，得到
$$ \frac{4!}{0!}-\frac{4!}{1!}+\frac{4!}{2!}-\frac{4!}{3!}+\frac{4!}{4!} $$不难发现，每一项的正负与该项分母的奇偶有关.所以又能写成
$$ \sum_{i=1}^4 \frac{{(-1)^i}4!}{i!} $$事实上，对于$n$为其他正整数的情况，也能得到这种结构，读者可自行验证.
于是我们得到全错排公式
$$ \boxed{ a_n=\sum_{i=1}^n \frac{{(-1)^i}n!}{i!} } $$推导完毕！！！(ᕑᗢᓫ∗)
可能存在的疑问
- 对于4个元素的全错排，3个元素排列正确就意味着4个元素排列正确，为什么重复计算？
这个我认为是容斥原理的计算规则.我们在集合中使用容斥原理时，是按交集的个数递增的顺序计算的，像 $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$（$|X|$表示集合$X$中元素个数）.你可以画Venn图，每一个 圆圈代表一个元素的正确排列，就会发现其实我们要求的是“有元素正确排列”的情况，即所有集合的并集的元素个数. 由于针对集合的计算是正确的，所以即便有些集合是空集，算出来的结果也同样是符合真实状况的.
- 我算出的情况重复了.
应该的，你多次计算了交集的部分，后面减去就好了.
更多疑问可致信河中数协官方邮箱hyzxmath@outlook.com或者在下方评论区留言，小南梁会耐心为您解答♡