首页 > 代码库 > 错排数

错排数

考虑如下问题:

   若1...n的一些全排列满足第1个不是1,第2个不是2,...,第n个不是n,这样的序列有多少个?

 

记答案为f

考虑第1个位置的数,若它是x:

1. 若第x位是1,则剩下的就是n-2个数的错排数fn-2

2.否则,就相当于n-1个数的错排数(因为第2个不是2,...第x个不是1,...,第n个不是n,那就可以把1看作x)fn-1

又因为x有n-1种选法,所以fn=(n-1)(fn-1+fn-2)

有f0=1,f1=0

这个序列称作错排数。

它的前几项为1, 0, 1, 2, 6...

 

错排数