组合数学
组合计数基础
加法原理
完成任务的方法有 $n$ 类，每类有 $a_i$ 种方法，则完成任务的方法数为 $\sum a_i$ 种。
乘法原理
完成任务有 $n$ 个步骤，每个步骤有 $a_i$ 种方法，则完成任务的方案数为 $\prod a_i$ 种。
$\text{A}$（排列数）
从 $n$ 个元素中选出 $m$ 个进行排列（有序），则方案数为：
$A^n_m=n\times (n-1)\times … \times (n-m)=\frac{n!}{m!}$
$\text{C}$（组合数）
从 $n$ 个元素中选出 $m$ 个元素组成一个集合（无序），则方案数为：
$C^n_m=\frac{A^n_m}{m!}=\frac{n!}{m!(n-m)!}$，也写作 $\binom{n}{m}$
组合数的性质：
$\binom{n}{m}=\binom{n}{n-m}$，即 $C_n^m=C_n^{n-m}$
$\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}$，即 $C_n^m=\frac{n}{m}C_{n-1}^{m-1}$
$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$，即 $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
- 杨辉三角
插板法
用于处理将相同元素分组的计算技巧
Q1. 将 $n$ 个元素分为 $k$ 个非空组
可以理解为在 $n$ 个元素间（即 $n-1$ 个间隔空位上）插入 $k-1$ 个板作为分隔
Q2. 组可空
可能出现多个板放到同一个空位上的情况。
但反过来考虑，最终元素 + 板的数量一定为 $n+(k-1)$，即从最终状态倒推着看，是从 $n+(k-1)$ 个位置上选出 $k-1$ 个位置放板
Q3. 每组至少有 $a_i$ 个元素
预支元素，转化为 Q2。
Q4. 从 $n$ 个元素中选出 $k$ 个，要求互不相邻
剩余 $n-k$ 个挡板，划分成 $n-k+1$ 个空位，每个空位最多放一个。
二项式定理
$(a+b)^n=\sum_k \binom{n}{k} a^k b^{n-k}$
$2^n=(1+1)^n=\sum\limits_{i=0}^n\binom{n}{i}$
$0^n=\sum\limits_{i=0}^n(-1)^i\binom{n}{i}=[n=0]$
容斥原理
$|\bigcup\limits_{i=1}^n S_i|=\sum\limits_{x=1}^{n}(-1)^{x-1}\sum
\limits_{a_i<a_{i+1}}|\bigcap\limits_{i=1}^nS_{a_i}|$
每部分出现的次数（系数）为 $\binom{n}{1}-\binom{n}{2}+\binom{n}{3}-…$
$=\binom{n}{0}-\sum\limits_{i=1}^n(-1)^i\binom{n}{i}$
$=1-(1-1)^n$