组合计数

Posted on

组合计数

加乘原理

乘法原理：完成一个工程需要分 $n$ 个步骤，$a_i(1 \le i \le n)$ 代表第 $i$ 个步骤的不同方法数目。那么完成这件事共有 $S = a_1 \times a_2 \times \cdots \times a_n$ 种不同的方法。

加法原理：完成一个工程可以有 $n$ 类办法，$a_i(1 \le i \le n)$ 代表第 $i$ 类方法的数目。那么完成这件事共有 $S=a_1+a_2+\cdots +a_n$​ 种不同的方法。

例题(快速幂)：计算$x^ymod\ p$

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;
}

排列数

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

从 $n$ 个不同元素中取出 $m$($m\leq n$) 个元素的所有排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数，用符号 $\mathrm A_n^m$表示。
$$
\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!}
$$

组合数

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

从 $n$ 个不同元素中取出 $m \leq n$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\dbinom{n}{m}$ 来表示；
$$
\dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!}
$$

例题：计算$\dbinom{n}{m} mod\ p$

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;

圆排列

$n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
所以有
$$
\mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)!
$$

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

$$
\mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!}
$$

抽屉原理

将 $n$ 个物体，划分为 $k$ 组，那么至少存在一个分组，含有大于或等于 $\left \lceil \dfrac{n}{k} \right \rceil$ 个物品。

推广的形式也可以使用反证法证明：若每个分组含有小于 $\left \lceil \dfrac{n}{k} \right \rceil$ 个物体，则其总和 $S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n$ 矛盾。

此外，划分还可以弱化为覆盖结论不变。
给定集合 $S$, 一个 $S$ 的非空子集构成的簇 ${A_1,A_2\ldots A_k}$

  • 若满足 $\bigcup_{i=1}^k A_i$ 则称为 $S$ 的一个覆盖（cover）；
  • 若一个覆盖还满足 $i\neq j\to A_i\cap A_j=\varnothing$ 则称为 $S$ 的一个划分。

鸽巢原理可以有如下叙述：对于 $S$ 的一个覆盖 ${A_1,A_2\ldots A_k}$ 有至少一个集合 $A_i$ 满足 $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$。

容斥原理

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

$$
\begin{aligned}
\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\
&+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n|
\end{aligned}
$$

即

$$
\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|
$$
证明：

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

$$
\begin{aligned}
Cnt=&|{T_i}|-|{T_i\cap T_j|i<j}|+\cdots+(-1)^{k-1}\left|\left{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right}\right|\
&+\cdots+(-1)^{m-1}|{T_1\cap\cdots\cap T_m}|\
=&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\
=&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\
=&1-(1-1)^m=1
\end{aligned}
$$

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