错位排列 [数学]

写在前面

那就先从一个例题引入吧 (来自《组合数学》P110)

题目

在一次聚会上,有 $n$ 位男士和 $n$ 位女士。这 $n$ 位女士能够有多少种方法选择男舞伴开始第一支舞?如果在一首曲后每个人必须换舞伴,那么第二支舞又有多少种选择方法?

分析

首先,第一支舞有 $n!$ 中选择,而第二支舞的选择方法数为后面要讲的错位排序数 $D_n$

(说起来这个例子好像我校神犇兔崽子Tzz换女朋友)

错位排列

首先安利 $Planet6174$ 的博客讲解 小学生都能看懂的错排问题解析 (高中生表示看懂了)

问题

给定 $n$ 元集合 $X$,它的每一个元素都有一个特定的位置,而现在要求求出没有一个元素在它指定的位置上的排列的数目。(发现就是上面的第二支舞)

特别的,请注意,每一个元素都只有一个限定不能放的位置。

方法

我们这里假定第 $i$ 个元素不能放在第 $i$ 个位置上(因为不一样的我们可以通过交换达成,对应顺序没有影响)

用 $D_n$ 表示 $\{1,2,3,…n\}$ 的错位排列的数目。那么,对于 $n=1$ ,不存在可行解; $n=2$ 时,唯一的错位排列是 2 1; $n=3$ 时有两个排列 2 3 1 和 3 1 2。因此,我们有 $D_1=0$, $D_2=1$, $D_3=2$。

递推式

考虑将第 $n$ 个元素放到第 $k$ 个位置 $(k \neq n)$,有 $n-1$ 种放法,然后分类讨论

1、第 $k$ 个元素放到了第 $n$ 个位置上
发现这样的话第 $n$ 个和第 $k$ 个就相当于不存在了,不影响其他元素的放置,此时,我们将其余的元素错位排列的方案数量有 $D_{n-2}$ 种

1、第 $k$ 个元素没有放到第 $n$ 个位置上
这样相当于是加了一个限定:第 $k$ 个元素不能放在第 $n$ 个位置上。因为 $k$ 个位置已经被用过了,相当于不存在,那么可以说去掉了 $k$ 不放 $k$ 位的限制。这样我们可以交换第 $k$ 个和第 $n$ 个位置,就变成去掉了一个元素 $n$ 和位置 $k$ 的情况,即变成 $n-1$ 个元素的错位排列 $D_{n-1}$

我们有了一个很简单的递推式

通项公式

证明这个……详见《组合数学》P108

简单推一下,主要思想 容斥原理

首先,不考虑限制,总排列数为 $n!$ 。
减掉不合法的:至少有一个元素放到它的指定位置的有 $C_n^1$ 种,限定了这个个的放法后,其余的 $n-1$ 个元素可以随意排列,共有 $C_n^1 \times (n-1)!$ 种。
但这样有算重的,还要加上两个元素都放在它的指定位置上的方案数 $C_n^2 \times (n-2)!$ 种,再减去三个元素的……就得到了

当然也可以

参考资料

1、$Planet6174$ 小学生都能看懂的错排问题解析
2、《组合数学》第六章 容斥原理及应用-错位排序

完结撒花

你以为这就完了?不不不,上面那些并不是导致我写这篇博客的根本原因,源自一道题

限制了一些元素放置位置的错位排列

题目

Codeforces 340E

问题描述

给你 $n$ 个球 $n$ 个盒子,一个盒子只能放一个球,限定第 $i$ 个球不能放在第 $i$ 个位置上,但已知一些盒子里面已经放了球,求一共有多少种合法的放置方案。

输入格式

第一行一个整数表示 $n$ 。第二行 $n$ 个数 $a_i$ 。如果 $a_i = -1$ 表示第 $i$ 个盒子没有放球,否则表示第 $i$ 个盒子已经放了球 $a_i$ 。

输出格式

一个非负整数表示合法的方案数,模 $1e9+7$ 。

样例输入

1
2
5  
-1 -1 2 1 -1

样例输出

1
4

数据范围

分析

真是,第一眼看到这个题目就想到了错排,但当时这是一个甚至没有列入学习计划的东西却认出来了,然后当场去学,发现错排好简单……再然后,被告知这个题还有放球的限制……

突破口就是将球分成两部分:一个是没有限制可以随便放的,一个是有限制球 $i$ 不能放在盒子 $i$ 的 。其中已经放好了的球就不管了。

然后就有了一个 $O(n^2)$ 的 $dp$ ,记 $f[i][j]$ 为剩余 $i$ 个没限制的球和 $j$ 个有限制的球的方案数,然后你大力转移一下,就有了一个 $50$ 分的好成绩,再次完结撒花

没有转移方程 -> 因为在推 $dp$ 式敲代码的时候看了一眼原本的错位排列后突然想到了 $O(n)$ 的……

容斥! 不要管没有限制的球,我们记 $tot$ 为没有放好的球的个数,记 $a$ 为有限制的球的个数 。不理限制时,总共有 $tot \ !$ 种,然后再像上面一样,枚举至少有一个球 $i$ 放到盒子 $i$ ,其余随便排的 $C_a^i \times (tot-i)!$ 种减掉,再加上至少两个的……
最后

其实很简单(推式子用了一分钟,前面的一堆算上和机房的那群人聊天用了2h+—),好菜好菜……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

#define _ 0

namespace TYC
{
typedef long long ll;
const int N=2e6+10;
const int p=1000000007;
const int inf=0x3f3f3f3f;

int arr[N],vis[N];
ll fac[N],inv[N];

inline int read()
{
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}

inline ll qpow(ll x,ll tim)
{
ll ans=1;
for(;tim;tim>>=1,x=x*x%p)
if(tim&1) ans=ans*x%p;
return ans;
}

void init(const int n)
{
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p;
inv[n]=qpow(fac[n],p-2);
for(int i=n;i;i--) inv[i-1]=inv[i]*i%p;
}

inline ll C(const int n,const int m)
{
if(n<m) return 0;
return fac[n]*inv[m]%p*inv[n-m]%p;
}

inline void work()
{
int n=read();
int tot=0,x=0;
for(int i=1;i<=n;i++)
{
arr[i]=read();
if(~arr[i]) vis[arr[i]]=1;
else tot++;
}
for(int i=1;i<=n;i++)
if(!vis[i]) x+=(arr[i]==-1);
init(tot);
ll ans=0;
for(int i=0;i<=x;i++)
ans=(ans+(((i&1)?-1:1)*C(x,i)+p)%p*fac[tot-i]%p)%p;
printf("%lld\n",ans);
}
}

int main()
{
TYC::work();
return (0^_^0);
}