组合数学学习笔记

· · 个人记录

组合数学学习笔记

——by sunzz3183

组合

定义

从 n 个元素中选 m 个元素的所有情况数（无顺序），记为

C_{n}^{m}

公式

C_{n}^{m}=\frac{n!}{m!(n-m)!}

代码

  1. 直接求
inline int ksm(int a,int b){int t=1;for(;b;b>>=1,a=a*a%p)if(b&1)t=t*a%p;return t%p;}
inline int C(int n,int m){
    if(n<m)return 0;
    if(m>n-m)m=n-m;
    int a=1,b=1;
    for(int i=1;i<=m;i++)
        a=a*(n-i+1)%p,b=b*i%p;
    return a*ksm(b,p-2)%p;
}
  1. 预处理阶乘求
int fac[N],inv[N];
inline int ksm(int a,int b){int t=1;for(;b;b>>=1,a=a*a%mod)if(b&1)t=t*a%mod;return t%mod;}
void init(int n){
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for(int i=n;i>=1;i--)
        inv[i-1]=inv[i]*i%mod;
}
inline int C(int n,int m){
    if(n<m)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

拓展

因为

C_{n}^m=C_{n}^{n-m}

所以

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

万用表

可以找到大部分组合数的规律

其中第 n 行 m 列为 C_{n+m}^m 或 C_{n+m}^n

排列

从 n 个元素中选 m 个元素的排列的所有情况数（有顺序），记为

P_{n}^{m}

公式

P_{n}^{m}=\frac{n!}{(n-m)!}

Lucas定理

C_n^m \mod p=C_{n/p}^{m/p} \times C_{n\bmod p}^{m\bmod p}\mod p

代码

inline int Lucas(int n,int m){return m?Lucas(n/p,m/p)*C(n%p,m%p)%p:1;}

卡特兰(Catalan)数

意义

从 (0,0) 不越过直线 y=x ，走到 (n,n) 的方案个数。

式子

设 h(n) 为卡特兰数的第 n 项。

令 h(0)=1,h(1)=1，卡特兰数满足递推式

h(n)= h(0)\times h(n-1)+h(1)\times h(n-2) + ... + h(n-1)\times h(0) (n≥2)

另类递推式：

h(n)=h(n-1)\times (4\times n-2)/(n+1) h(n+1)=h(n)\times (4\times n + 2) / (n + 2)

非递推：

h(n)=C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}=\frac{(2n)!}{n!(n+1)!}

拓展

在求一些走到 (n,m) 的时候

f(n,m)=C_{n+m}^n-C_{n+m}^{m-1}=\frac{C_{n+m}^n\times (n-m+1)}{n+1}=\frac{(n+m)!\times (n-m+1)}{m!(n+1)!}

多重集组合数

例题Devu and Flowers

描述

给定 n(1\leq n \leq 20) 个数，每个数最多选 a_i(1\leq a_i \leq 10^{12})，一共选 m(1\leq m \leq 10^{14}) 个数，问方案数。

分析

显然，当 a_i\geq m 时，答案为

C_{n+m-1}^{n-1}

那么如果不满足这种情况呢？

设第 i 个数字为 b_i，此题可以转化为，从可重集

S=\left \{ b_1\cdot a_1,b_2\cdot a_2,\cdots ,b_n\cdot a_n \right \}

选 m 个数的方案数。

根据容斥可得：

C_{n+m-1}^{n-1}-\sum\limits_{i=1}^n C_{n+m-a_i-2}^{n-1}+\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n C_{n+m-a_i-a_j-3}^{n-1}-\cdots +(-1)^n C_{n+m-\sum\limits_{i=1}^na_i-n-1}^{n-1}

实现时通过枚举二进制 0\sim 2^n-1 来加减。