首页 > 代码库 > 错排数
错排数
考虑如下问题:
若1...n的一些全排列满足第1个不是1,第2个不是2,...,第n个不是n,这样的序列有多少个?
记答案为fn 。
考虑第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...
错排数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。