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