错排公式
错排问题最早被 尼古拉·伯努利和欧拉 研究，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将\(n\)封信装到\(n\)个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。
举例：
十本不同的书放在书架，现重新摆放，使得每本书都不在原来的位置上，有几种摆法？
一个人给十个同学写信，但他把所有的信都装错了信封，问共有多少种错误的方式？
解题思路
做这道题刚开始没有什么头绪，后来上网查了一下才发现原来有一个错排公式，也就是元素都不在对应原来位置的方法数。公式为：
\[\large f(n) = (n-1) \times (f(n-2) + f(n-1)) \]
推导过程：
第一步：假如一共有\(n\)个元素，那么如果把 第\(n\)个元素 放在某一个位置\(k\)处，一共有\(n-1\)种方法(除去位置\(n\)可不就是有\(n-1\)个吗~)；
第二步：放编号为\(k\)的元素有两种情况：
- 如果把它放到位置\(n\)，那么除了\(n\)和\(k\)元素外的\(n-2\)个元素一共有\(f(n-2)\)种方法
- 如果不把它放到位置\(n\)，那么对于剩下的\(n-1\)个元素有\(f(n-1)\)种方法
综上所述，错排公式为:
\[\large f(n) = (n-1) \times (f(n-2) + f(n-1)) \]
有了错排公式，这道题就很容易解决了，总的排列方法数有\(n\)的阶乘个，而全部错排的方法数有 \((n-1)\times (f(n-1) + f(n-2))\)个，最后直接把错排方法数除以总的排列数，然后注意输出格式就可以了。
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef long long LL;
LL f[N], sum;
// f(n)=(n-1)*(f(n-1)+f(n-2))
int main() {
int m;
scanf("%d", &m);
while (m--) {
int n;
scanf("%d", &n);
// base case
sum = 1;
f[1] = 0, f[2] = 1;
//递推出错排次数
for (int i = 3; i <= n; i++)
f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
//总次数
for (int i = 1; i <= n; i++) sum = sum * i;
//比率
printf("%.2lf%%\n", (double)f[n] / sum * 100);
}
return 0;
}
将总数为\(n\)个人的一队人，将选错新娘的放在一起则构成一个 全错排列，将选对的\(n-m\)个新郎放在一起成为一个排列，则可能出现的总数为正确的排列情况*全错排的情况
复习一下组合数公式：
\[\large C_a^b=\frac{a!}{b!\times (a-b)!} \]
#include <iostream>
using namespace std;
typedef long long LL;
LL C(int a, int b) {
LL sum1 = 1, sum2 = 1;
for (int i = b + 1; i <= a; i++) sum1 *= i;
for (int i = 1; i <= a - b; i++) sum2 *= i;
return sum1 / sum2;
}
int main() {
LL f[21] = {0, 0, 1}; //这个初始化很牛B的样子,放过头雁打二雁，而且f[1]=0,f[2]=1
//错排公式,预处理
for (int i = 3; i < 21; i++) f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
cout << C(n, m) * f[m] << endl;
}
return 0;
}