一、递推式推导

考虑问题:有 $n$ 个箱子,颜色分别为 $1…n$;还有 $n$ 个球,颜色也分别为 $1…n$。现在要将每一个球分别放入一个箱子里,并且每个箱子和它里面球的颜色都不一样 ,求方案数。

设 $D_n$ 表示方案数。对第$n$个球有 $n-1$ 种情况:$n$号球分别放进$1$号,$2$号,……,$n-1$号箱子。

考虑将第$n$个球放进第$k$个箱子,那么对于第$k$个球,又有两种情况:在或不在第$n$个箱子。

若在,即是将剩下$n-2$个球按上述原则继续排列,方案显然有$D_{n-2}$种。

若不在,则问题变成:第$1$个球不在$1$号箱,……,第$k-1$个球不在$k-1$号箱,第$k+1$个球不在$k+1$号箱,……,第$n-1$个球不在$n-1$号箱,第$k$个球不在$n$号箱。可以发现,这就是把第$n$个球扔掉再排列,显然方案有$D_{n-1}$种。

而$k$又有$n-1$种取值,所以有$D_n=(n-1)(D_{n-1}+D_{n-2})$。

二、由递推式推导通项式

设$D_n=n!\times M_n$,易得$M_1=0$,$M_2=\frac {1}{2}$。
当$n\geqslant 3$时,由$D_n=(n-1)(D_{n-1}+D_{n-2})$,
得$n!M_n=(n-1)\times (n-1)!M_{n-1}+(n-1)\times (n-2)!M_{n-2}=n!M_{n-1}-(n-1)!M_{n-1}+(n-1)!M_{n-2}$
约掉$(n-1)!$并移项,
得$nM_n-nM_{n-1}=-M_{n-1}+M_{n-2}$
再约掉$n$并变形,
得$M_n-M_{n-1}=-\frac {1}{n}(M_{n-1}-M_{n-2})$
不断迭代可得$M_n-M_{n-1}=(-\frac {1}{n})(-\frac {1}{n-1})…(-\frac {1}{3})(M_2-M_1)=(-1)^n \frac {1}{n!}$
列出$M_i-M_{i-1}(1<i\leqslant n)$并累加,
得$M_n=(-1)^2\frac {1}{2!}+(-1)^3\frac {1}{3!}+…+(-1)^n\frac {1}{n!}$
所以$D_n=n!M_n=n!(\frac {1}{2!}-\frac {1}{3!}+…+(-1)^n\frac {1}{n!})$

三、由容斥原理推导通项式

显然数列$\left \{ 1,2,3,…,n \right \}$的全排列有$n!$种,其中确定第$k$位是$k$的有$(n-1)!$种,所以需要减去这些;但是这样又把同时有两个数不错排的排列多排除了一次,所以需要加上;但是这样又把同时有三个数不错排的排列多加上了一次,所以需要减去……
于是得$D_n=n!-\frac {n!}{1!}+\frac {n!}{2!}-\frac {n!}{3!}+…+(-1)^n\frac {n!}{n!}=n!(\frac {1}{2!}-\frac {1}{3!}+…+(-1)^n\frac {1}{n!})$

四、常用推论

  • 简化通项式:$D_n=\left \lfloor \frac {n!}{e}+\frac {1}{2} \right \rfloor$
  • 另一种递推式:$D_n=nD_{n-1}+(-1)^n$

最后更新: 2018年11月24日 07:35

原始链接: https://ruixiangjiang.github.io/2018/11/16/Disorderly-arrangement/

× 请我吃糖~
打赏二维码