问题:有8个信封,8封信,若是每一封信都装错,则有多少种情况?
形如以上问题的推导,便是错排问题。
错排问题是组合数学发展史上的一个重要问题,错排数也是一项重要的数。
令 a k ( 1 < k < 1 ) {a_k}(1 < k < 1) ak(1<k<1)是 n ( n ∈ N ) {n}(n \in N) n(n∈N)的一个错排,如果每个元素都不在其对应下标的位置上,即 a k ≠ k a_k \neq k ak=k,那么这种排列称为错位排列,或错排、重排(Derangement)。
而用以解决错排问题的公式便是错排公式。
推导方式有两种:
- 容斥原理
- 递推
递推求错排公式
设 D n D_n Dn 为 n n n 个元素的错排数,则我们可以考虑两种情况:
- 前 n − 1 n-1 n−1 个元素皆放错,则第 n n n 个元素只需要和前面任意一个元素交换即可,即 D n − 1 D_{n-1} Dn−1 种可能
- 有一个元素放对,剩下的全部放错,则第 n n n 个元素只需要和放对的元素交换即可,即 D n − 2 D_{n-2} Dn−2 种可能
所以对于 D n D_n Dn 都有 D n = ( n − 1 ) ( D n − 1 + D n − 2 ) D_n = (n - 1)(D_{n-1}+D_{n-2}) Dn=(n−1)(Dn−1+Dn−2)
特殊的, D 1 = 0 , D 2 = 1 D_1 = 0,D_2 = 1 D1=0,D2=1
得到这个递推式之后,我们进一步进行推导:
为了运算的方便,我们设 D n = n ! × N n D_n=n! \times N_n Dn=n!×Nn
则有: n ! ∗ N n = ( n − 1 ) ∗ ( n − 2 ) ! ∗ N n − 2 + ( n − 1 ) ∗ ( n − 1 ) ! ∗ N n − 1 n!*N_n=(n-1)*(n-2)!*N_{n-2}+(n-1)*(n-1)!*N_{n-1} n!∗Nn=(n−1)∗(n−2)!∗Nn−2+(n−1)∗(n−1)!∗Nn−1
两边同时除 ( n − 1 ) ! (n-1)! (n−1)! ,可得: n ∗ N n = N n − 2 + ( n − 1 ) ∗ N n − 1 n*N_n=N_{n-2}+(n-1)*N_{n-1} n∗Nn=Nn−2+(n−1)∗Nn−1
移项: N n − N n − 1 = ( N n − 2 − N n − 1 ) / n = − ( 1 / n ) ( N n − 1 − N n − 2 ) N_n-N_{n-1}=(N_{n-2}-N_{n-1})/n = -(1/n)(N_{n-1}-N_{n-2}) Nn−Nn−1=(Nn−2−Nn−1)/n=−(1/n)(Nn−1−Nn−2)
错项相消得: N n − N 1 = 1 / 2 ! − 1 / 3 ! + 1 / 4 ! − ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ( − 1 ) n − 1 1 ( n − 1 ) ! + ( − 1 ) n 1 ( n ) ! N_n-N_1=1/2!-1/3!+1/4!- ··· ··· +(-1)^{n-1}\frac{1}{(n-1)!}+(-1)^{n}\frac{1}{(n)!} Nn−N1=1/2!−1/3!+1/4!−⋅⋅⋅⋅⋅⋅+(−1)n−1(n−1)!1+(−1)n(n)!1
由于 N ( 1 ) = 0 , N ( 2 ) = 1 N(1)=0,N(2)=1 N(1)=0,N(2)=1, 所以 N n = N n − N 1 = 1 / 2 ! − 1 / 3 ! + 1 / 4 ! − ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ( − 1 ) n − 1 1 ( n − 1 ) ! + ( − 1 ) n 1 n ! N_n=N_n-N_1=1/2!-1/3!+1/4!- ··· ··· +(-1)^{n-1}\frac{1}{(n-1)!}+(-1)^{n}\frac{1}{n!} Nn=Nn−N1=1/2!−1/3!+1/4!−⋅⋅⋅⋅⋅⋅+(−1)n−1(n−1)!1+(−1)nn!1
于是可以得到错排公式为:
D n = n ! ∗ ( 1 / 2 ! − 1 / 3 ! + 1 / 4 ! − ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ + ( − 1 ) n − 1 1 ( n − 1 ) ! + ( − 1 ) n 1 ( n ) ! ) = n ! ( ∑ i = 1 n ( − 1 ) i 1 i ! ) D_n=n!*(1/2!-1/3!+1/4!- ··· ··· +(-1)^{n-1}\frac{1}{(n-1)!}+(-1)^{n}\frac{1}{(n)!}) = n!(\sum_{i = 1}^n(-1)^i\frac{1}{i!}) Dn=n!∗(1/2!−1/3!+1/4!−⋅⋅⋅⋅⋅⋅+(−1)n−1(n−1)!1+(−1)n(n)!1)=n!(∑i=1n(−1)ii!1)
这样,我们就通过递推得到了两个关于错排问题的公式。
容斥原理求错排公式
在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理
定义 ∣ A ∣ |A| ∣A∣ 为集合 A A A 中的元素个数,则:
∣ ⋃ i = 1 n A i ∣ = ∑ k = 1 n ( − 1 ) k − 1 ∑ i = 1 ( 1 ≤ i 1 ≤ i 2 . . . . . . ≤ i k ≤ n n ∣ A i 1 ∩ A i 2 ∩ A i 3 . . . . . . ∩ A i k ∣ |\bigcup_{i = 1}^n A_i| = \sum_{k=1}^n(-1)^{k-1}\sum_{i=1(1\leq i_1\leq i_2......\leq i_k \leq n}^n |A_{i1} \cap A_{i2} \cap A_{i3} ...... \cap A_{ik}| ∣⋃i=1nAi∣=∑k=1n(−1)k−1∑i=1(1≤i1≤i2......≤ik≤nn∣Ai1∩Ai2∩Ai3......∩Aik∣
所以我们可以很容易的得到:
错排个数=全排个数-不是错排的个数
全排个数很显然为为 n ! n! n! , 而不是错排的个数我们可以以以下方法进行计算:
回到不是错排的定义,只要有一个数按照顺序排列,那么这个排列就不是错排。
那么我们可以先定义集合 P 1 P_1 P1 的元素是所有以 1 为开头的排列,定义集合 P 2 P_2 P2 的元素是所有第二个位置是 2 的排列,以此类推,定义集合 P n P_n Pn 的元素是所有第n位置为 n n n 的排列。举例来说, P 1 P_1 P1 中的元素可以是 1 2 3 4... n 1\ 2\ 3\ 4...\ n 1 2 3 4... n ,只要保证第一位为1就行。
很显然 P 1 ∪ P 2 ∪ . . . ∪ P n P_1\cup P_2 \cup ...\cup P_n P1∪P2∪...∪Pn 这个集合包括了所有的不是错排的排列。设错排的通项公式为 D n D_n Dn ,那么 D n = n ! − ∣ P 1 ∪ P 2 ∪ . . . ∪ P n ∣ D_n=n!-|P_1\cup P_2 \cup ...\cup P_n| Dn=n!−∣P1∪P2∪...∪Pn∣。将其展开 D n = n ! − ∣ P 1 ∪ P 2 ∪ . . . ∪ P n ∣ = n ! − ∑ i = 1 n ∣ P i ∣ + ∑ 1 ≤ i < j ≤ n ∣ P i ∩ P j ∣ − ∑ 1 ≤ i < j < k ≤ n ∣ P i ∩ P j ∩ P k ∣ . . . D_n=n!-|P_1\cup P_2 \cup ...\cup P_n| \\ =n!-\sum_{i=1}^n|P_i|+\sum_{1\leq i< j\leq n}{|P_{i}\cap P_{j}|}-\sum_{1\leq i<j<k\leq n}|P_i\cap P_{j}\cap P_{k}|... Dn=n!−∣P1∪P2∪...∪Pn∣=n!−∑i=1n∣Pi∣+∑1≤i<j≤n∣Pi∩Pj∣−∑1≤i<j<k≤n∣Pi∩Pj∩Pk∣...
我们来逐项分析,先看第二项 ∑ i = 1 n ∣ P i ∣ \sum_{i=1}^n|P_i| ∑i=1n∣Pi∣。首先 ∣ P 1 ∣ |P_1| ∣P1∣ 应该是多少?按照前面的定义,只要第一项是1的排列都是 P 1 P_1 P1 的元素。也就是说剩下的 n − 1 n-1 n−1 位随便排列。那么很显然, ∣ P 1 ∣ = ( n − 1 ) ! |P_1|=(n-1)! ∣P1∣=(n−1)! 。以此类推,对于任意的 i i i , ∣ P i ∣ = ( n − 1 ) ! |P_i|=(n-1)! ∣Pi∣=(n−1)! 。那么第二项 ∑ i = 1 n ∣ P i ∣ = n × ( n − 1 ) ! = n ! 1 ! \sum_{i=1}^n|P_i|=n\times(n-1)!=\frac{n!}{1!} ∑i=1n∣Pi∣=n×(n−1)!=1!n! 。
往后类推:
∑ 1 ≤ i < j < k ≤ n ∣ P i ∩ P j ∩ P k ∣ = n ! 3 ! ∑ 1 ≤ i < j < k < l ≤ n ∣ P i ∩ P j ∩ P k ∩ P l ∣ = n ! 4 ! ∑ 1 ≤ i < j < k < l < m ≤ n ∣ P i ∩ P j ∩ P k ∩ P l ∩ P m ∣ = n ! 5 ! ⋯ \sum_{1\leq i<j<k\leq n}|P_i\cap P_{j}\cap P_{k}|=\frac{n!}{3!}\\ \sum_{1\leq i<j<k<l\leq n}|P_i\cap P_{j}\cap P_{k}\cap P_{l}|=\frac{n!}{4!}\\ \sum_{1\leq i<j<k<l<m\leq n}|P_i\cap P_{j}\cap P_{k}\cap P_{l}\cap P_{m}|=\frac{n!}{5!} \\ \cdots ∑1≤i<j<k≤n∣Pi∩Pj∩Pk∣=3!n!∑1≤i<j<k<l≤n∣Pi∩Pj∩Pk∩Pl∣=4!n!∑1≤i<j<k<l<m≤n∣Pi∩Pj∩Pk∩Pl∩Pm∣=5!n!⋯
化简得:
D n = n ! ( ∑ i = 1 n ( − 1 ) i 1 i ! ) D_n = n!(\sum_{i=1}^n(-1)^i\frac{1}{i!}) Dn=n!(∑i=1n(−1)ii!1)