错排问题
错排问题
定义
考虑一个有 \(n\) 个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。
\(n\) 个元素的错排数记为 \(D(n)\)
公式
\(D(n)=(n-1)(D(n-1)+D(n-2))\)
考虑当前放到了第 \(n\) 个元素，那么这个元素肯定不能放到第 \(n\) 个位置上
也就是说，这个元素可以放到除了第 \(n\) 个位置以外的 \(n-1\) 个位置上
假设第 \(n\) 个元素放到了第 \(i\) 个位置上
那么原来第 \(i\) 个位置上的元素就必须放到其它的位置上
如果这个元素放到了第 \(n\) 个位置上
就相当于位置 \(n\) 和位置 \(i\) 的元素交换，其它的元素不动，也就是一个 \(n-2\) 规模的错排问题
如果这个元素放到了除了第 \(n\) 个位置和第 \(i\) 个位置以外的 \(n-2\) 个位置中的一个
那么不去考虑放在第 \(i\) 个位置的第 \(n\) 个元素
就相当于一个 \(n-1\) 规模的错排问题
只不过把第 \(i\) 个元素不能放到第 \(i\) 个位置上改为了第 \(i\) 个元素不能放到第 \(n\) 个位置上
版权声明：本文为liuchanglc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。