组合数学基础

组合数学基础

排列与组合

• 排列：${\mathrm{A}}_n^m=n(n-1)\cdots (n-m+1)=\frac{n!}{(n-m)!}$
• 组合：$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\frac{n!}{m!(n-m)!}$
• 二项式定理：$(a+b{)}^n={\sum }_{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})a^{n-i}{b}^i$
• 多重集排列：$\frac{n!}{n_1!n_2!\cdots n_k!}$

Lucas 定理

对于素数 $p$，有：

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\equiv \left(\genfrac{}{}{0ex}{}{\lfloor n/p\rfloor }{\lfloor k/p\rfloor }\right)\left(\genfrac{}{}{0ex}{}{n\mathrm{mod}p}{k\mathrm{mod}p}\right)(\mathrm{mod}p)$$

long long lucas(long long n, long long k, long long p) {
  if (k == 0) return 1;
  return C(n % p, k % p, p) * lucas(n / p, k / p, p) % p;
}

Catalan 数

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\frac{(2n)!}{n!(n+1)!},C_n=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$$

递推：$C_n=\frac{4n-2}{n+1}{C}_{n-1}$，$C_0=1$

应用：合法括号序列、二叉树计数、出栈序列、网格路径（不越过对角线）。

容斥原理

$$\left|\bigcup _{i=1}^n{S}_i\right|=\sum _i|S_i|-\sum _{i<j}|S_i\cap S_j|+\cdots +(-1{)}^{n-1}|S_1\cap \cdots \cap S_n|$$

练习题目

题目	描述
P3807 【模板】卢卡斯定理	Lucas 定理求组合数
P1044 [NOIP2003] 栈	Catalan 数
P1450 [HAOI2008] 硬币购物	容斥原理+背包

相关链接

• 快速幂与模运算
• GCD与EXGCD
• 素数筛
• 路径D-DSA算法刷题

来源：OI-wiki combination.md & catalan.md & inclusion-exclusion-principle.md

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |