鲜花：距离上一次整理数学知识还是在 $2023$ 年，不知不觉已经过去了两年，真快啊……那个时候我还很菜，不过现在的我并没有成为之前想成为的样子。

组合数和基本组合数公式

1. $\binom nm = \frac{n!}{(n – m)! m!}$

   更广义的定义为 $\frac{n^{$m}}{m!}，可在 $n$ 为实数，$m$ 为非负整数时定义。

2. $\binom nm = \binom{n}{n – m}$

   组合意义：$n$ 个选 $m$ 个相当于从 $n$ 个里面选择 $m$ 个不选。

3. $\binom nm = \binom {n – 1}{m} + \binom {n – 1}{m – 1}$（加法公式）

   组合意义：相当于枚举第一个选还是不选。

4. $\sum_{i = 0}^n \binom ni= 2^n$

   组合意义：$n$ 个中任意选相当于选择不同数量的方案数之和。

5. $\binom nm = \frac nm \binom{n – 1}{m – 1}$ （吸收公式）

   常用于 $m\binom nm$ 和 $n \binom {n – 1}{m – 1}$ 相互转换，使得前面那个系数变为定值提到外面去。

   组合意义：从 $n$ 个里选 $m$ 个再选 $1$ 个特殊的等价于先从 $n$ 个里选出特殊的再从剩下 $n – 1$ 里选 $m – 1$ 个。是公式 $6$ 的特殊形式。

6. $\binom nm \binom mk = \binom nk \binom{n – k}{m – k}$

   组合意义：从 $n$ 个选 $m$ 再选 $k$，从 $n$ 个选 $k$ 再从 $n-k$ 个选 $m – k$，显然二者等价。

7. $\sum_{i=0}^n\binom{i}{m}=\binom{n+1}{m+1}$ （上指标求和）

   组合意义：有 $n + 1$ 个位置，从中选取 $m+1$ 个，按照最后一个被选的位置统计。当最后一个位置为 $i + 1$ 时，选出 $m+1$ 个位置的组合数就等价于从前 $i$ 个位置选出 $m$ 个位置的组合数之和。

8. $\sum_{i = 0}^m \binom{n + i} {i} = \binom{n + m + 1}n$（平行求和）

   代数解释：$=\sum_{i = 0}^{m} \binom {n + i}n$，直接套上指标求和公式。

   组合意义：我不知道。

9. $\sum_{i = 0}^m \binom ni (-1)^i = (-1)^k \binom{n – 1}{k}$ （下指标差求和）

10. $\sum_{i = 0}^k \binom ni \binom m{k – i} = \binom{n + m}{k}$（范德蒙德卷积）

    组合意义：从 $n + m$ 种选 $k$ 个相当于从前 $n$ 个选 $i$ 个，后 $m$ 个选 $k – i$。

11. $\sum_{i=0}^n x^iy^{n-i}\binom{n}{i}=(x+y)^n$（二项式定理）

    组合意义：$n$ 个球染色，每个球都可以染成 $x$ 种暖色之一和 $y$ 种冷色之一。

更多组合意义

1. 插板法

   若 $m$ 个变量赋值为正整数和为 $n$ 方案数为 $\binom {n – 1}{m – 1}$。

   组合意义：$n$ 个小石子用 $m – 1$ 个板分成 $m$ 个部分。

   如果赋值成非负整数的方案数量为 $\binom{n + m – 1}{m – 1}$。

   组合意义：将所有数字 $+1$ 最后 $-1$ 即满足调前

2. 捆绑法

   如果集合 $S$ 必须抱团取暖，把他们当成一个整体，最后乘上集合内部排列的方案数即 $|S|!$。

入门题

[ARC144D] AND OR Equation

你并不用在意这个题讲的什么，我们来推式子，尝试化简：

$$\sum_{i = 0}^n \sum_{s = i}^k \binom ni 2^i \binom{s – 1}{i – 1}(k – s + 1)$$

要求 $O(n)$ 计算。

$$\begin{align} &= \sum_{i = 0}^n \binom ni 2^i \sum_{s = i}^k ((k + 1) \binom{s – 1}{i – 1} – i\binom si) \\ &= \sum_{i = 0}^n \binom ni 2^i ((k + 1) \binom ki – i\binom {k + 1}{i+1})\\ &= \sum_{i = 0}^n \binom ni 2^i ((i + 1) \binom {k + 1}{i + 1} – i\binom {k + 1}{i+1}) \\ &= \sum_{i = 0}^n \binom ni 2^i \binom {k + 1}{i+1} \end{align}$$

$(1)$ 简单移项，$(2)$ 上指标求和化简，$(3)$ 吸收公式化简，$(4)$ 简单整理。