看到一道有意思的题，因而分享。

19. 错排问题源于伯努利和欧拉研究的“装错信封问题”。

设将编号为 $1,2,3,\cdots,n$ 的 $n$ 个小球放入编号为 $1,2,3,\cdots,n$ 的 $n$ 个盒子中（每盒恰放一球），若恰有 $m$ 个小球不在其对应编号的盒子中（即“错放”），则称这种情况数为错排数 $F(n,m)$，其中编号为 $i$ 的小球对应编号为 $i$ 的盒子。

已知 $F(1,1)=0$，$F(2,2)=1$，规定 $F(0,0)=1$。

(1) 直接写出 $F(3,3)$，$F(4,4)$ 的值；

(2) 设 $F(n,n)=a_n$，$n \in \boldsymbol{N}^*$，证明数列 ${a_{n+1}-(n+1)a_n}$ 是等比数列；

(3) 在高考英语中，“七选五”是一种常见题型。题目给出一篇缺少5个句子的短文，要求考生从文后的7个选项 $A、B、C、D、E、F、G$ 中选出5个最佳选项，填入文中空缺处，使文章完整、语义连贯。某考生由于平时不重视英语学习，于是在做此类题时采用“蒙题”的策略：5个空完全随机作答（选项不重复）。记蒙题答对的题数为随机变量 $X$，求 $X$ 的分布列和数学期望。

Sol:

(1) + (2)：错排数的求解有两种经典做法，一种是利用容斥原理，一种是像题(2)一样构造递推关系求解，我们这里不妨遵循出题人的思路采用第二种方法。

Step1: 建立$a_{n+1},a_n,a_{n-1}$之间的关系 假设我们要计算$a_{n+1}$，手里有n+1个球，为了建立递推关系，我们必须先固定一个球的位置，如果我们先把1号球放在1号盒子，考虑剩下n个球的排列；

Case1: 如果剩下n个球完全错排，有$a_n$种组合，这时将1号球与其中任意一个进行交换，仍得到n+1个球的错排，共有$n\times a_n$种情况

Case2: 如果剩下n个球种恰有一个球i在对应的盒子i种，剩下n-1个球是错排，此时将球1和球i交换位置，得到n+1个球的错排，共有$n\times a_{n-1}$种情况。 剩下n个球种恰有一个球

Case3: 如果剩下n个球中有大于等于2个球在对应的盒子里，这里就无法在1步交换操作内实现n+1个球的错排，不考虑。

因此，得到递推关系： \(a_{n+1}=na_n+na_{n-1}\) 移项整理即得： \(a_{n+1}-(n+1)a_n=-(a_n-na_{n-1})\)

即得到${a_{n+1}-(n+1)a_n}$是以-1为公比的等比数列。

Step2: 求解$a_n$

易得:$a_1=0,a_2=1$

所以， \(a_{n+1}-(n+1)a_n=(-1)^{n-1}\)

两边同除以$(n+1)!$，得到

\[\frac{a_{n+1}}{(n+1)!}-\frac{a_{n}}{(n)!}=\frac{(-1)^{n+1}}{(n+1)!}\]

求和易得：

\[\frac{a_{n+1}}{(n+1)!}=\sum_{k=2}^{n+1}\frac{(-1)^{k}}{k!}\]

所以，

\[a_{n}=n!\sum_{k=2}^{n}\frac{(-1)^{k}}{k!}\]

并验证$a_1=0$符合上式。

自然有$a_3=2,a_4=9$

(3): 七选五问题建模

Idea:利用(1)(2)分别计算$P(X=k), k=0,1,2,3,4,5$

为了用上错排数的已知内容，我们不妨把五个填空编号1,2,3,4,5；正确的5个选项依次为A,B,C,D,E,加上两个干扰项F,G;我们把问题建模为7个选项选5个随机排列，总共$A_7^5=2520$种组合。

(i) $P(X=5)$

最简单，只有1种组合。

(ii) $P(X=4)$

先选4个对的$C_5^4$,再选1个干扰项$C_2^1$，共10种可能。

(iii) $P(X=3)$

逻辑链是一样的，先选3个对的$C_5^3$,然后分3种情况，F,G选了0,1,2个，依次计算相加得到有$C_5^3\times(C_2^0a_2+C_2^1C_2^1+A_2^2)=70$种组合

(iv) $P(X=2)$

先选2个对的$C_5^2$,然后分3种情况，F,G选了0,1,2个，依次计算相加得到有$C_5^2\times(C_2^0a_3+C_2^1C_3^2(a_2+C_2^1)+C_2^2C_3^1C_2^1A_2^2)=320$种组合。

(iv) $P(X=1)$ 先选1个对的$C_5^1$,然后分3种情况，F,G选了0,1,2个，依次计算相加得到有$C_5^1\times(C_2^0a_4+C_2^1C_4^3(a_3+C_3^1(a_2+C_2^1))+C_2^2C_4^2(a_2A_2^2+C_2^1C_2^1A_2^2+A_2^2A_2^2))=905$种组合。

(v) $P(X=0)$ 分3种情况，F,G选了0,1,2个

若F,G中选了0个，组合数就是5个选项错排$a_5$;

若F,G中选了1个，假设是F，假设正确选项5选4选了A,B,C,D；分两种情况讨论，若F在位置5，则剩下是$a_4$种组合，若F不在位置5，相当于是5个选项的错排，即$a_5$种组合，因此该情况共有$C_2^1C_5^4(a_4+a_5)=530$种组合。

若F,G中选了2个，类似讨论有$C_2^2C_5^3(a_3+a_4+a_4+a_5)=640$种组合。

因此该情况的组合数一共1214种（验算各情况组合数相加是否为2520，当然如果你对前面的计算足够自信这里也可以直接用减法得到k=0的组合数）

进而得到随机变量$X$的分布列，计算其数学期望应为 \(EX=\frac{5}{7}\)