概述
错排数的定义
- 假设有n个元素，n个位置，每个元素都有自己唯一的正确位置，问，所有元素都处在错误位置有多少可能
递推公式
- 设 f(n) f ( n ) 表示n个元素的错排种数，则 f(n+1)=n∗(f(n)+f(n−1)) f ( n + 1 ) = n ∗ ( f ( n ) + f ( n − 1 ) )
- 解释如下
- 假设已经有n个元素错排，新来一个元素，那么该元素处于已有的n个元素的位置都可以实现错排，所以有 n∗f(n) n ∗ f ( n ) 种可能
- 假设已有n个元素，其中n-1个是错排的，另外一个是正确的，这种情况有n种。新来一个元素，这个元素唯有跟那个正确元素交换位置才可以实现n+1个元素的错排。所以有 n∗f(n−2) n ∗ f ( n − 2 ) 种可能
- 为什么没有其他可能？
- 因为对于n+1个元素的某个错排来说，假设第 n+1 n + 1 个元素处于第i位( i≠n+1 i ≠ n + 1 )，然后第 n+1 n + 1 个位置有第k个元素，那么要么 k=i k = i 或者 k≠i k ≠ i ，没有其他可能情况
ACM题
- hdu2049
最后
以上就是可爱黄蜂为你收集整理的组合数之错排数的全部内容，希望文章能够帮你解决组合数之错排数所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[SDOI2016]排列计数(详解)](/uploads/reation/bcimg4.png)
![洛谷-4071 [SDOI2016]排列计数](/uploads/reation/bcimg8.png)
发表评论 取消回复