错排问题详解

约定不等于承诺〃 2024-03-16 22:54 29阅读 0赞

## 错排问题（Derangement） ##

### 概念释义[\#][Link 1] ###

又叫错位排列、重排，即使一个排列所有的元素都不在原来的位置上。

> 错排问题是组合数学发展史上的一个重要问题，错排数也是一项重要的数。令 ak(1≤k≤n) 是 n,nϵN 的一个错排，如果每个元素都不在其对应下标的位置上，即 ak≠k ，那么这种排列称为错位排列，或错排、重排（Derangement）。

Copy

`————————摘自《百度百科》`

### 简要分析[\#][Link 2] ###

我们来看一个最为经典的错排问题，信封问题：**共有 n 张信和 n 个信封，假设所有信都装错了信封，共有多少种情况？**

我们先定义 f(n) 为当有 n 个信封和 n 张信时，有 f(n) 种错排方案。

当 n=1 时，信只能放在它对应的信封中，不可能出现错排情况。

故 f(1)=0。

当 n=2 时，只存在一种情况，即两张信交换位置。

故 f(2)=1。

当 n=3 时，存在着 、、、、3、1、2 和 、、、、2、3、1 两种情况，我们可以将其看为 1 与 2 错排，3 与 1、2 交换位置得来的。

故 f(3)=2。

当 n=4 时，错排有：

`4 3 2 1` `4 1 2 3` `4 3 1 2`

第一列是 4 分别与 123 互换位置，其余两个元素错排。

`3 4 1 2` `3 4 2 1` `2 4 1 3`

第二列是 4 分别与 312（ 123 的一个错排）的每一个数互换。

`2 1 4 3` `3 1 4 2` `2 3 4 1`

第三列则是由另一个错排 231 和 4 换位而得到。

共 9 种情况。

根据上面的注释得知， f(n) 的值与 f(n−1) 、f(n−2) 的值有一定的关联。

那我们能否得出递推式呢？答案是肯定的。

### 公式推导[\#][Link 3] ###

#### 首先，[\#][Link 4] ####

1 号元素必定要排在第 2∼n 个位置的其中之一，所以有 n−1 种放法。

#### 然后，[\#][Link 5] ####

假设 1 号元素放在了第 k 个位置，那么下一步就要排 k 号元素。

#### 再然后，[\#][Link 6] ####

k 号元素的排列有两种方式：

**一是放在第 1 个位置**，剩下的 n−2 个元素进行错排，共有 f(n−2) 种可能；

**二是不放在第 1 个位置**，这时我们将第 1 个位置看作第 k 个位置，于是就形成了包括 k 号元素在内的 n−1 个元素的错排，共有 f(n−1) 种可能。

**所以，k 号元素共有 f(n−1)+f(n−2) 种可能。**

又因为第一号元素有 n−1 种放法，根据乘法原理。

#### 我们得知，[\#][Link 7] ####

**递推式为：**

f(n)=(n−1)×(f(n−1)+f(n−2))。

以上就是错排问题的全部内容了（当然只是基础部分的全部内容）

### 练习题[\#][Link 8] ###

#### [P1595 信封问题][P1595][\#][Link 9] ####

这是一道模板题，只要你知道递推式便可以做对。此题也可以使用深度优先搜索来 AC 掉这道题。

不过需要注意的是，错排方案的增长非常快。  
n=13 时 int 会爆掉，n=22 时 f(n) 的值就已经达到了约 7×1018 , 在 n=23 时 long long 会爆掉。

也就是说，在处理错排问题时一定要开 long long。

当题目给出 n>20 的范围时，我们就应该使用高精度算法了（Python、Java等略过）。

### Code[\#][Link 10] ###

Copy

`#include<iostream> #include<cstdio> using namespace std; long long f(long long x)//一定要开long long { if( x == 1 ) return 0; else if( x == 2 ) return 1; else return (x-1)*(f(x-1)+f(x-2)); } int main() { int n; cin>>n; cout<<f(n); return 0; }`

#### [P3182 \[HAOI2016\]放棋子][P3182 _HAOI2016][\#][Link 11] ####

这道题也是一道裸错排题，不过数据到了 200 ，必定需要高精度。

[Link 1]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#910688884
[Link 2]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#2178495766
[Link 3]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#154978133
[Link 4]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#1911566636
[Link 5]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#152469913
[Link 6]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#4210393902
[Link 7]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#1752237117
[Link 8]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#3184204002
[P1595]: https://www.luogu.com.cn/problem/P1595
[Link 9]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#510233357
[Link 10]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#17880330
[P3182 _HAOI2016]: https://www.luogu.com.cn/problem/P3182
[Link 11]: https://www.cnblogs.com/baijian0212/p/cuopaiwenti.html#3504066855