错排问题

问题

错排问题是组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为 D_n!n

递归解法

显然D_1=0,D_2=1

n \ge 3 时,不妨设n排在了第k位,其中k \ne n,也就是 1 \le k \le n-1。那么我们现在考虑k的情况。

  1. 当k排在第n位时,除了n和k以外还有n-2个数,其错排数为D_{n-2}
  2. 当k不排在第n位时,那么将第n位重新考虑成一个新的“第k位”(这步很重要!!!),这时的包括k在内的剩下n-1个数的每一种错排,都等价于只有n-1个数时的错排(只是其中的第k位会换成第n位)。其错排数为D_{n-1}

所以当n排在第k位时共有D_{n-2}+D_{n-1}种错排方法,又k有从1到n-1共n-1种取法,我们可以得到以下递推公式:

D_{n}=(n-1)(D_{n-1}+D_{n-2})

这里给出D_n的前几项:0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, …

发表评论

电子邮件地址不会被公开。 必填项已用*标注