组合数学基础

程序设计中的组合数学基础

组合数学

乘法原理&加法原理

乘法原理：做一件事，完成它需要分成$n$个步骤，做第一步有$m_1$种不同的方法，做第二步有$m_2$种不同的方法，…，做第$n$步有$m_n$种不同的方法，那么完成这件事共有$N=m_1*m_2*m_3*…*m_n$种不同的方法（前提：任意两个步骤间互相独立）

加法原理：做一件事，完成它有$n$类方式，第一类方式有$M_1$种方法，第二类方式有$M_2$种方法，…，第$n$类方式有$M_n$种方法，那么完成这件事情共有$M_1+M_2+…+M_n$种方法

排列&组合

$$A_n^m=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}\\ 全排列：A_n^n=n!\\ 特别的：0!=1\\ C_n^m=\frac{n!}{m!(n-m)!}$$

常用恒等式

$$C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\\C_n^m=C_n^{n-m}\\$$

二项式定理

$$(x+y)^n=\sum_{i=0}^nC_n^{n-i}x^iy^{n-i}$$

组合问题

Q：有$k$种物品共$n$个，其中第$i$种物品有$a_i$，问最后一共多少种排列？

A：先全当成一种，然后去重

$$ans=\frac{n!}{a_1!a_2!a_3!...a_k!}$$

Q：$n$个元素排成一排，分成$m$个非空的段的方案数

A：隔板法，在$n-1$个空位里插入$m-1$个隔板的方案数

$$ans=C_{n-1}^{m-1}$$

Q：$n$个元素排成一排，分成$m$个可空的段的方案数

A：假想$n$个元素中加入$m$个元素，然后对这$n+m$个元素应用上一题的方法，最后再考虑把每一段减去一个元素，就是答案

$$ans=C_{n+m-1}^{m-1}$$

Q：$\sum_{i=0}^{n}(C_n^i)^2=?$

A：

$$\sum_{i=0}^{n}(C_n^i)^2=\sum_{i=0}^nC_n^iC_n^{n-i}$$

上式其实就是从$2n$个元素里取$n$个元素的取法总数，所以

$$ans=C_{2n}^n$$

Q：计算模意义下的$C_n^m=\frac{n!}{m!(n-m)!}$

• 定义计算法

  只需要计算模意义下的阶乘和阶乘的逆元就可以了

• 杨辉三角递推法

  考虑$Cn^m=C\{n-1}^m+C_{n-1}^{m-1}$，开一个二维数组，初始化$C_i^0=1$，递推即可

int C[N+5][N+5];
void solve(){
    C[0][0]=1;
    for(int i=1;i<=N;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}