组合数

约 887 个字 26 行代码 预计阅读时间 3 分钟

讲课链接

排列组合

排列就是指从给定个数的元素中取出指定个数的元素进行排序

组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序

排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。

加法原理

做一件事情，完成它有$n$类办法，$a_i$ 表示第$i$类方法的数目，那么完成这件事共有$\sum\limits_{i=1}^n a_i$ 种不同的方法

乘法原理

做一件事情，完成它有$n$个步骤，$a_i$ 表示第$i$个步骤的方法数目，那么完成这件共事有$\prod\limits_{i=1}^n a_i$种不同的方法。

排列数

$n$ 个数选 $m$ 个排列，情况总数=$A_n^m=\frac{n!}{(n-m)!}$

全排列，指 $n$ 个数选 $n$ 个排列，情况总数=$A_n^n=n!$

组合数

$n$ 个数选 $m$ 个组合，情况总数=$C_n^m=\frac{n!}{m!(n-m)!}$

组合数也常用$\displaystyle\binom{n}{m}$表示

组合数也被称为“二项式系数”

多重集

包含重复元素的广义集合。

设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$

表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集

多重集的排列数

从 $S$ 中选择 $r$ 个元素排列

$$\frac{n!}{\prod_{i=1}^k(n_i!)}$$

相当于把相同元素的排列数除掉了

多重集的组合数

从 $S$ 中选择 $r$ 个元素组合

这个问题等价于 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的数目，可以用插板法解决，答案为

$$\binom{r+k-1}{k-1}$$

不相邻的排列

$1 \sim n$ 这 $n$ 个自然数中选 $k$ 个，这 $k$ 个数中任何两个数都不相邻的组合有 $\displaystyle \binom {n-k+1}{k}$ 种。

圆排列

$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)!}$$

组合数性质

$$\binom{n}{m}=\binom{n}{n-m}\tag{1}$$

相当于将选出的集合对全集取补集，故数值不变。（对称性）

$$\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2}$$

由定义导出的递推式。

$$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3}$$

组合数的递推式（杨辉三角的公式表达）

$$\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4}$$

这是二项式定理的特殊情况。取 $a=b=1$ 就得到上式。

$$\sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{5}$$

拆组合数的式子，在处理某些数据结构题时会用到。

$$\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{6}$$

这是 $(5)$ 的特殊情况，取 $n=m$ 即可。

$$\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{7}$$

带权和的一个式子，通过对 $(3)$ 对应的多项式函数求导可以得证。

$$\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{8}$$

与上式类似，可以通过对多项式函数求导证明。

$$\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{9}$$

在恒等式证明中较常用。

$$\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{10}$$

通过定义可以证明。

$$\sum_{i=0}^n\binom{n-i}{i}=F_{n+1}\tag{11}$$

其中 $F$ 是斐波那契数列。

预处理组合数

const int N=1e6+3;
long long fac[N],inv[N];
long long fast_power(long long base, long long exponent)
{
    long long result = 1;
    for (; exponent > 0; exponent >>= 1)
    {
        if (exponent & 1)
            result = result * base % mod;
        base = base * base % mod;
    }
    return result;
}
void getC()
{
    fac[0]=1;
    for(int i=1;i<N;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[N-1]=fast_power(fac[N-1],mod-2);
    for(int i=N-1;i;--i)
        inv[i-1]=inv[i]*i%mod;
}
long long C(int n,int m)
{
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}