加乘原理

乘法原理：完成一个工程需要分 个步骤， 代表第 个步骤的不同方法数目。那么完成这件事共有 种不同的方法。

加法原理：完成一个工程可以有 类办法， 代表第 类方法的数目。那么完成这件事共有 ​ 种不同的方法。

例题(快速幂)：计算

1
2
3
4
5
6
int pow(int x,int y){ 
	int res=1;
	x%=p;
	for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
    return res;
}

排列数

从 个不同元素中，任取 （）个元素按照一定的顺序排成一列，叫做从 个不同元素中取出 个元素的一个排列；

从 个不同元素中取出 () 个元素的所有排列的个数，叫做从 个不同元素中取出 个元素的排列数，用符号 表示。

组合数

从 个不同元素中，任取 个元素组成一个集合，叫做从 个不同元素中取出 个元素的一个组合；

从 个不同元素中取出 个元素的所有组合的个数，叫做从 个不同元素中取出 个元素的组合数，用符号 来表示；

例题：计算

1
2
3
4
5
6
int inv(int x,int p){ //求逆元
	return pow(x,p-2);
}
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; //预处理出阶乘
return ((fac[n]*inv(fac[m],p))%p*inv(fac[n-m],p))%p;

圆排列

个人全部来围成一圈，所有的排列数记为 。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。 所以有

由此可知部分圆排列的公式：

抽屉原理

将 个物体，划分为 组，那么至少存在一个分组，含有大于或等于 个物品。

推广的形式也可以使用反证法证明：若每个分组含有小于 个物体，则其总和 矛盾。

此外，划分还可以弱化为覆盖结论不变。
给定集合 , 一个 的非空子集构成的簇

  • 若满足 则称为 的一个覆盖（cover）；
  • 若一个覆盖还满足 则称为 的一个划分。

鸽巢原理可以有如下叙述：对于 的一个覆盖 有至少一个集合 满足 。

容斥原理

设 U 中元素有 n 种不同的属性，而第 i 种属性称为 ，拥有属性 的元素构成集合 ，那么

即

证明：

对于每个元素使用二项式定理计算其出现的次数。对于元素，假设它出现在 的集合中，那么它的出现次数为

于是每个元素出现的次数为 1，那么合并起来就是并集;