总结

C-代表-Combination–组合数 

A-代表-Arrangement–排列数(在旧教材为P-permutation–排列) 

N-代表-元素的总个数 

M-代表-参与选择的元素个数 

!-代表-阶乘

博客（http://jingyan.baidu.com/article/63acb44ac60d4e61fcc17e2e.html）



排序公式

从n个不同元素中，任取m个元素按照一定的顺序排成一列



用例测试：

4种颜色，按不同颜色进行排列，有多少种排列方法？
6种颜色，按不同颜色进行排列，有多少种排序方法？
6种颜色，取出4种颜色进行排列，有多少种排序方法？




计算公式：



组合公式

从n个不同元素中，任取m个元素并成一组；（不顺序要求）



用例测试：

从4种颜色中，取出2种颜色，能形成多少种组合？




计算公式：

首先，对于D(n)，有1~n这样n个元素错排，所以对于第一个元素①，它现在可能的位置有(n-1)个，倘若它在第k个元素的位置上，对于第k个元素而言，它所在的位置就有两种可能—第一种，它处在非第一个元素①位置上，所以对于接下来的排列就相当于是n-1个元素的错排，即D(n-1);第二种，它处在第一个元素①的位置上，所以在排列D(n)中有两个元素找到了位置，那么接下来的队列就相当于是n-2个元素的错排。因此，对于D(n)都有D(n)=(n-1)*(D(n-1)+D(n-2))【特殊的，D(1)=0，D(2)=1】。

容斥定理

正整数1,2, 3, ……, n的全排列有 n! 种，其中第k位是k的排列有 (n-1)! 种；当k分别取1, 2, 3, ……, n时，共有n*(n-1)!种排列是至少放对了一个的，由于所求的是错排的种数，所以应当减去这些排列；但是此时把同时有两个数不错排的排列多排除了一次，应补上；在补上时，把同时有三个数不错排的排列多补上了一次，应排除；……；继续这一过程，得到错排的排列种数为D(n) = n! - n!/1! + n!/2! - n!/3! + … + (-1）^n*n!/n!= ∑(k=2~n) (-1)^k * n! / k!   或者  

为方便起见，设D(k) = k! N(k), k = 1, 2, …, n,

则N(1) = 0, N(2) = 1/2.

n ≥ 3时，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)

即 nN(n) = (n-1) N(n-1) + N(n-2)

于是有N(n) - N(n-1) = - [N(n-1) - N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) - N(1)] = (-1)^n / n!.

因此

N(n-1) - N(n-2) = (-1)^(n-1) / (n-1)!,

N(2) - N(1) = (-1)^2 / 2!.

相加，可得

N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!

因此

D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

此即错排公式。

递推代码

long long rc[maxn];
inline void get_cp()
{
    rc[0]=1ll;
    for(int i=2;i<=n;i++)
        rc[i]=(i-1)*(rc[i-2]+rc[i-1])%mod;
}

 

 

 

今天集训问错排是什么被hszx教练嘲讽了，痛下决心学一下竟然还挺简单的


错位排序递推公式：
设f[i]为i个数错位排序 (任意1<=i<=n a[i]!=i)
f[0]=1,f[1]=0;
f[i]=(f[i-1]*f[i-2])*(i-1)  (i>=2)
公式理解：
情况1:插入第i个元素时，前i-1个已经错位排好，则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种，前i-1位错排f[i-1]种，记f[i-1]*(i-1)
情况2:插入第i个元素时，前i-1个中恰有一个元素a[j]使得a[j]=j，其他i-2个错位排好，则将i与j交换，j在i-2位中的插入共i-1种，前i-2位错排f[i-2]种，记f[i-2]*(i-1)
以上两种情况求和可得


f[i]=(f[i-1]*f[i-2])*(i-1)  (i>=2)
递推代码

long long cp[maxn];
inline void get_cp()
{
	cp[0]=1ll;
	for(int i=2;i<=n;i++)
		cp[i]=(i-1)*(cp[i-2]+cp[i-1])%mod;
}
模板题：bzoj4517

附代码（写慢了，不预处理阶乘逆元能降一个log QAQ）

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1000005
#define mod 1000000007
int n=maxn,m,T;
long long stair[maxn];
long long invs[maxn];
long long cp[maxn];
long long ans[maxn];
inline long long qpow(long long b,long long t)
{
	long long ans=1ll;
	while(t)
	{
		if(t&1) ans=(ans*b)%mod;
		t>>=1;
		b=(b*b)%mod;
	}
	return ans;
}
inline long long inv(long long x)
{
	return qpow(x,mod-2);
}
inline void init()
{
	stair[0]=1ll;
	invs[0]=1ll;
	for(int i=1;i<=n;i++)
	{
		stair[i]=stair[i-1]*i%mod;
		invs[i]=inv(stair[i]);
	}
	cp[0]=1ll;
	for(int i=2;i<=n;i++)
		cp[i]=(i-1)*(cp[i-2]+cp[i-1])%mod;
}
inline long long comb(int a,int b)
{
	return stair[a]*invs[b]%mod*invs[a-b]%mod;
}
int main()
{
 	scanf("%d",&T);
 	init();
 	while(T--)
 	{
 		scanf("%d%d",&n,&m);
 		printf("%lld\n",comb(n,m)*cp[n-m]%mod);
 	}
}

全错位排序
全错位排列被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例。
“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：

一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？

f[n]表示有n个信封全错位情况数

可以把问题分成两种情况：①前面n-1封信全部装错 ②前面n-1封信只有一个正确，其余全部装错
①前面n-1封信全装错，第n封信与前面n-1封信任意一封交换。可得(n-1)*f[n-1]种情况
②前面n-1封信只有一个正确，其余全部装错，第n封信可以与那封正确的交换，这样有f[n-2]*(n-1)种情况
可以推出f[n] = (n-1)(f[n-1]+f[n-2])