组合数学

排列数

不可重排列 $A_n^r=\frac{n!}{(n-r)!}$

圆排列 $\frac{A_n^r}{r}$

+多重集的排列

$a_1,a_2,a_3,...,a_n$ 互不相同，每个元素有无穷多个，则从中取 r 个形成排列的方案数为 $n^r$

$a_1,a_2,a_3,...,a_n$ 互不相同，每个元素的个数都大于等于 r ，则从中取 r 个形成排列的方案数为 $n^r$

$a_1,a_2,a_3,...,a_n$ 互不相同，每个元素的个数都比 r 小。设 $k_1,k_2,k_3,...,k_n$ 为 $a_1,a_2,a_3,...,a_n$ 的个数，则从中取 r 个形成排列的方案数为 $\frac{(k_1+k_2+K_3+...+k_n)!}{k_1!k_2!k_3!...k_n!}$

$a_1,a_2,a_3,...,a_n$ 互不相同，至少有一个元素的个数比 r 小。设 $k_1,k_2,k_3,...,k_n$ 为 $a_1,a_2,a_3,...,a_n$ 的个数，则从中取 r 个形成排列的方案数为 $r\times \frac{r!}{k_1!k_2!...k_n!}$

组合数

不可重组合 $C_n^r=\frac{n!}{r!(n-r)!}$

不相邻组合 $C_{n-r+1}^r$

+多重集的组合

$a_1,a_2,a_3,...,a_n$ 互不相同，每个元素有无穷多个，则从中取 r 个的方案数为 $C_{n+r-1}^r$

$a_1,a_2,a_3,...,a_n$ 互不相同，每个元素的个数都大于等于 r ，则从中取 r 个的方案数为 $C_{n+r-1}^r$

+常用公式

$C_n^r=C_n^{n-r}$

帕斯卡恒等式 $C_n^r=C_{n-1}^r+C_{n-1}^{r-1}$

二项式定理 $(x+y)^n=\sum_{i=0}^{n}C_n^ix^{n-i}y^i$

$\sum_{i=0}^{n}C_n^i=2^n$

$C_n^0+C_n^2+C_n^4+C_n^6...=C_n^1+C_n^3+C_n^5+C_n^7...$

$\sum_{i=0}^{n}2^iC_n^i=3^n$

Lucas定理推论 $C_n^r$ 为奇数，则

错排

n 个元素的错排方案数记为 $D_n$

则有 $D_1=0,D_2=1$

$D_n=(n-1)(D_{n-1}+D_{n-2})$

斐波那契数列

$F_1=F_2=1$
$F_n=F_{n-1}+F_{n-2}$

卡特兰数

组合数 $Cat_n=C_{2n}^n-C_{2n}^{n-1}$

递推 $Cat_{n+1}=\frac{2(2n+1)}{n+2}Cat_n$

+应用

• n 个数有 $Cat_n$ 种出栈顺序

• n 个节点的二叉树有 $Cat_n$ 种构型

• n+1 个节点的满二叉树有 $Cat_n$ 种

• 在 $n\times n$ 的格子的右下三角形中行走，每次横走或竖走，有 $Cat_n$ 种走法

• 将 n+2 边形剖分成三角形，有 $Cat_n$ 种方案

• 有 n 个左括号和右括号的合法括号表达式有 $Cat_n$ 种

第一类斯特林数

$S_1[n][m]$ 表示把 n 个不同的元素排列成 m 个圆排列的方案数
有 $S_1[n][m]=S_1[n-1][m]\times (n-1)+S_1[n-1][m-1]$

边界 $S_1[0][0]=1$

第二类斯特林数

$S_2[n][m]$ 表示把 n 个不同的小球放到 m 个相同盒子，且每个盒子不为空的方案数

有 $S_2[n][m]=S_2[n-1][m]\times m+S_2[n-1][m-1]$
边界 $S_2[0][1]=1$

贝尔数

$B_n$ 表示把 n 个不同元素划分为若干个非空集合的方案数

递推公式 $B_{n+1}=\sum_{i=0}^{n}C_n^iB_i$

借助第二类斯特林数 $B_n=\sum_{i=0}^{n} S_2[n][i]$

盒子与球模型

n 个盒子，r 个球

球不同盒不同有空盒

每个球之间相互独立，自行选择在哪一个盒子

方案数为 $n^r$

球相同盒不同

每个球相同，用隔板法

没有空盒

方案数为 $C_{r-1}^{n-1}$

有空盒

提前向每个盒子中放入一个球，再做没有空盒的情况

方案数为 $C_{r+n-1}^{n-1}$

球相同盒相同

考虑dp

有空盒

$dp[r][n]$ 表示将 r 个小球放到 n 个盒子中，允许空盒的方案数
边界 $dp[0][...]=1,dp[...][1]=1$

转移，对于 $dp[i][j]$

如果 $i<j$，$dp[i][j]=dp[i][i]$；

如果 $i>=j$，$dp[i][j]=dp[i-j][j]+dp[i][j-1]$

没有空盒

先在每个盒子里都放上一个球

方案数为 $dp[r-n][n]$

球不同盒相同

考虑第二类斯特林数

没有空盒

方案数为 $S_2[r][n]$

有空盒

枚举有几个盒子为空

方案数为 $\sum_{i=1}^{n} S_2[r][n-i]$

球不同盒不同没空盒

在盒相同的基础上对盒做一个全排列

方案数为 $n!\times S_2[r][n]$

组合数取模

$m,n\le 1000$ 使用帕斯卡恒等式递推

mod 较大时，使用线性推阶乘逆元

mod 比较小时，使用Lucas定理

Lucas定理

需要借助线性推阶乘逆元

cpp
1
inline int c(int n,int m,int mod){return m>n? 0:fac[n]*inv[m]%mod*inv[n-m]%mod;}

注意lucas的边界

cpp
1
int lucas(int n,int m,int p){return m? c(n%p,m%p,p)*lucas(n/p,m/p,p):1;}