[数学] 错排问题
错排问题
直接上题解释吧
题目描述
某人写了 \(n\) 封信和 \(n\) 个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
输入格式
一个信封数 \(n\)（\(n \le 20\)）
输出格式
一个整数，代表有多少种情况。
首先, 我们明确一下 \(D \left( n \right)\) 的定义: \(n\) 个数都不能放在原先的位置的方案数.
对于这个题, 我们假定已经知道了 \(D \left( 0 \right)\) ~\(D \left( n-1 \right)\)的值.
当我们放入第 \(n\) 个数时, \(n\) 一定有 \(n-1\) 种放法.
考虑其中一种: 当 \(n\) 被放置在第 \(k\) 个位置时:
1. \(k\) 被放在了第 \(n\) 个位置, 这两个数对剩下位置的错排无任何影响, 有 \(D \left( n-2 \right)\) 种方案;
2. \(k\) 被放在了其他位置, 这时我们需要排除 \(k\) 被放在 \(n\) 位置上的情况( 即第一种情况 ), 所以我们可以直接把 \(n\) 位置看作是 \(k\) 的原位置, 则有 \(D \left( n-1 \right)\) 种方案.
于是我们得到了如下的递推公式:
\[D \left( n \right) = \left( n-1 \right) \times \left[D \left( n-1 \right)+D \left( n-2 \right)\right]\]
特别的, \(D\left(0\right) = 0\), \(D\left(1\right)=0\), \(D\left(2\right)=1\).
根据这个递推公式, 我们可以求出数列通项公式:
\[D\left(n\right) = n!\left(1-\frac{1}{1!}+\frac{1}{2!}- ... \pm \frac{1}{n!} \right)\]
这就是错排问题的基本公式.
注: 运用容斥原理同样可以导出相同的结果.