关于错排问题
给定 n n n 个数字，求数字 1 , 2 , ? ? , n 1,2,\cdots,n 1,2,?,n 不排列在第 1 , 2 , ? ? , n 1,2,\cdots,n 1,2,?,n 上的排列数量称为错排问题。
容斥定理
X
1
,
?
?
,
X
n
X_1,\cdots,X_n
X1?,?,Xn? 为可数集合，那么
∣
X
1
∪
?
∪
X
n
∣
|X_1\cup\cdots\cup X_n|
∣X1?∪?∪Xn?∣ 为
∣
X
1
∪
?
∪
X
n
∣
=
∑
k
=
1
,
1
?
i
1
<
?
<
i
k
?
n
n
(
?
1
)
k
+
1
∣
X
i
1
∩
?
∩
X
i
k
∣
|X_1\cup\cdots\cup X_n|=\sum_{k=1,1\leqslant i_1<\cdots<i_k\leqslant n}^n(-1)^{k+1}|X_{i_1}\cap\cdots\cap X_{i_k}|
∣X1?∪?∪Xn?∣=k=1,1?i1?<?<ik??n∑n?(?1)k+1∣Xi1??∩?∩Xik??∣
求解错排问题
给定
n
n
n 个数字，我们令
Y
i
:
=
{
Permutations?that?number?
i
?is?not?at?the?position?
i
}
Y_i:=\{\text{Permutations that number }i\text{ is not at the position }i\}
Yi?:={Permutations?that?number?i?is?not?at?the?position?i}
例如给定
n
=
3
n=3
n=3，我们有
Y
1
=
{
213
,
312
,
231
,
321
}
Y_1=\{213,312,231,321\}
Y1?={213,312,231,321}
根据错排问题的描述，从
n
n
n 个数字的全排列中去除一个数字排对的情况、两个数字排对的情况、……、
n
n
n 个数字排对的情况就得到了错排问题的全部可能排列。那么
n
n
n 数情况下错排问题的解
a
n
a_n
an? 即为
a
n
=
n
!
?
∣
Y
1
∪
?
∪
Y
n
∣
\begin{aligned} a_n&=n!-|Y_1\cup\cdots\cup Y_n|\\ \end{aligned}
an??=n!?∣Y1?∪?∪Yn?∣?
显然对于互不相等的
1
?
i
1
<
?
<
i
k
?
n
1\leqslant i_1<\cdots<i_k\leqslant n
1?i1?<?<ik??n，有
∣
Y
i
1
∩
?
∩
Y
i
k
∣
=
C
n
k
(
n
?
k
)
!
|Y_{i_1}\cap\cdots\cap Y_{i_k}|=C_n^k(n-k)!
∣Yi1??∩?∩Yik??∣=Cnk?(n?k)!
即
k
k
k 个数字排对，其余数字随意排列得到的排列数量。那么有
a
n
=
n
!
?
∣
Y
1
∪
?
∪
Y
n
∣
=
n
!
?
∑
k
=
1
n
(
?
1
)
k
+
1
C
n
k
(
n
?
k
)
!
=
n
!
?
∑
k
=
1
n
(
?
1
)
k
+
1
n
(
n
?
1
)
?
(
n
?
k
+
1
)
k
!
(
n
?
k
)
!
=
n
!
?
n
!
∑
k
=
1
n
(
?
1
)
k
+
1
k
!
=
n
!
(
1
+
∑
k
=
1
n
(
?
1
)
k
k
!
)
=
n
!
∑
k
=
0
n
(
?
1
)
k
k
!
\begin{aligned} a_n&=n!-|Y_1\cup\cdots\cup Y_n|\\ &=n!-\sum_{k=1}^n(-1)^{k+1}C_n^k(n-k)!\\ &=n!-\sum_{k=1}^n(-1)^{k+1}\frac{n(n-1)\cdots(n-k+1)}{k!}(n-k)!\\ &=n!-n!\sum_{k=1}^n\frac{(-1)^{k+1}}{k!}\\ &=n!\left(1+\sum_{k=1}^n\frac{(-1)^{k}}{k!}\right)\\ &=n!\sum_{k=0}^n\frac{(-1)^k}{k!} \end{aligned}
an??=n!?∣Y1?∪?∪Yn?∣=n!?k=1∑n?(?1)k+1Cnk?(n?k)!=n!?k=1∑n?(?1)k+1k!n(n?1)?(n?k+1)?(n?k)!=n!?n!k=1∑n?k!(?1)k+1?=n!(1+k=1∑n?k!(?1)k?)=n!k=0∑n?k!(?1)k??
为了便于求解，给出
a
n
a_n
an? 的递推。对于
n
?
1
n\geqslant 1
n?1，我们有
a
n
?
n
a
n
?
1
=
n
!
(
?
1
)
n
n
!
=
(
?
1
)
n
?
a
n
=
n
a
n
?
1
+
(
?
1
)
n
a_n-na_{n-1}=n!\frac{(-1)^n}{n!}=(-1)^n\Rightarrow a_n=na_{n-1}+(-1)^n
an??nan?1?=n!n!(?1)n?=(?1)n?an?=nan?1?+(?1)n
