错排问题

时间：2019-02-10 14:23:19 阅读：153 评论：0 收藏：0 [点我收藏+]

属于组合数,排列数这类的

定义：

　　n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。

　　如，1 2的错排是唯一的，即2 1。1 2 3的错排有31 2，2 3 1。这二者可以看作是1 2错排，3分别与1、2换位而得的。

错排公式：

递推关系：

-------------为求其递推关系，分两步走：

第一步，考虑第n个元素，把它放在某一个位置，比如位置k，一共有n-1种放法；

第二步，考虑第k个元素，这时有两种情况：（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有

种放法；

　　　　　　　　　　　　　　　　　　　　（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有

种放法。

根据乘法和加法法则，综上得到

时间复杂度为

原文：https://www.cnblogs.com/darlingroot/p/10359139.html

踩

(0)

评论一句话评论（0）

分享档案

更多>