建站实战干货

组合数学专练

知识区

1. 组合恒等式

AI了12个组合恒等式：

这里为您整理了 12 个最经典、最常用的组合恒等式，涵盖了对称性、递推、求和与卷积等核心思想。每个恒等式均附有公式及简要的组合解释或证明思路。

---

1. 对称恒等式（Symmetry）

\[\binom{n}{k} = \binom{n}{n-k} \]

说明：从 (n) 个元素中选 (k) 个，等价于排除 (n-k) 个。适用条件：(0 \le k \le n)。

---

2. 帕斯卡恒等式（Pascal's Identity）

\[\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \]

说明：组合数最核心的递推关系。考虑是否包含某个特定元素，包含则选 (k-1) 个，不包含则选 (k) 个。适用条件：(1 \le k \le n-1)。

---

3. 吸收恒等式（Absorption Identity）

\[k \binom{n}{k} = n \binom{n-1}{k-1} \]

说明：代数变换 (\frac{n!}{(n-k)!(k-1)!}) 的体现。组合意义：先从 (n) 个中选 (k) 个，再在这 (k) 个中选 1 个特殊元素。

---

4. 乘积恒等式（Product Identity）

\[\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m} \]

说明：从 (n) 个中选 (k) 个，再从这 (k) 个中选 (m) 个，等价于先选 (m) 个，再从剩下的 (n-m) 个中补足 (k-m) 个。

---

5. 二项式定理（Binomial Theorem）

\[\sum_{k=0}^{n} \binom{n}{k} x^k = (1+x)^n \]

说明：所有组合恒等式的“母函数”。令 (x=1) 得恒等式 6，令 (x=-1) 得恒等式 7。

---

6. 二项式系数总和

\[\sum_{k=0}^{n} \binom{n}{k} = 2^n \]

说明：(n) 个元素所有子集（包含空集）的总个数。

---

7. 交错和（Alternating Sum）

\[\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \quad (n \ge 1) \]

说明：奇偶子集数量相等。当 (n=0) 时和为 1。

---

8. 奇数项和 = 偶数项和

\[\sum_{k \text{ even}} \binom{n}{k} = \sum_{k \text{ odd}} \binom{n}{k} = 2^{n-1} \quad (n \ge 1) \]

说明：由恒等式 6 和 7 联立推导，奇偶子集各占一半。

---

9. 平方和（Sum of Squares）

\[\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n} \]

说明：范德蒙德恒等式的特例。组合意义：从 (n) 个红球和 (n) 个蓝球中共选 (n) 个。

---

10. 曲棍球棒恒等式（Hockey-Stick Identity）

\[\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1} \]

说明：(\binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{n}{k}=\binom{n+1}{k+1})。利用帕斯卡恒等式逐项累加可证。

---

11. 加权求和（Expected Value Form）

\[\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1} \]

说明：利用吸收恒等式 (k\binom{n}{k}=n\binom{n-1}{k-1}) 得证。组合意义：所有子集大小的总和。

11.5 加权求和补充

\[\sum_{k=0}^n k^2 \binom{n}{k}=\sum_{k=0}^n n\binom{n-1}{k-1}k=\sum_{k=0}^n n\binom{n-1}{k-1}(k-1)+\sum_{k=0}^n n\binom{n-1}{k-1}\\=\sum_{k=0}^n n(n-1)\binom{n-2}{k-2}+n2^{n-1}=n(n-1)2^{n-2}+n2^{n-1}\\=n(n-1)2^{n-2}+2n2^{n-2}=2^{n-2}n(n-1+2)=n(n+1)2^{n-2} \]

---

12. 范德蒙德恒等式（Vandermonde's Identity）

\[\sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r} \]

说明：从 (m) 个男生和 (n) 个女生中选 (r) 个人，枚举男生选了 (k) 个。这是组合卷积中最强大的工具之一。

---

💡 进阶提示

• 恒等式 10 可以变形为 (\sum_{i=0}^n \binom{r+i}{i} = \binom{r+n+1}{n})（平行求和），实质与曲棍球棒等价。
• 以上 12 个恒等式并非互相独立（如 6、7 是 5 的特例，9 是 12 的特例），但它们是解决计数、概率与算法分析（如卡特兰数推导、二项分布期望）中最常用的基石。

如果需要，我可以进一步为你演示这些恒等式在具体题目（如容斥原理或期望推导）中的实战应用。😊

2. 杨辉三角

杨辉三角的坐标都是从0开始的，并且定义 \(\binom{i}{0}=1\)，杨辉三角满足第二条恒等式（帕斯卡恒等式）

并且有一个性质 \(\sum_{i=0}^n \binom{n}{i}=2^n\)，也就是说杨辉三角的一行全部加起来是2的某个幂。

这个其实在组合恒等式里面就有了

题目收集

接下来会收集我在实战中遇到的不会的题目

1. [人口局 DBA](人口局 DBA - 题目详情 - Hydro)

给定 (n) 和进制 (m)，定义 (S(x)) 为 (x) 在 (m) 进制下各位数字之和。

求满足 (0 < x < n) 且 (S(x) = S(n)) 的整数 (x) 的个数，结果对 (10^9+7) 取模。

\(m \le 2000,n的长度\le 2000\)

做法：

令 \(L\) 为 \(n\) 的长度

发现从高位到低位做，看有没有顶满该位，没有顶满的话之后就随便乱选了。

假设现在做到第 \(i\) 位，当前位置没有顶满，那么剩下的 \(L-i\) 位就可以随便选，问题转化成求解很多次这样的方程：

有 \(t=L-i\) 个未知数 \(x_i\)，有多少种 \(x_i\) 的取值满足 \(0 \le x_i \le m-1\)，且 \(\sum x=p\)，\(p\) 是实时维护的，在遍历完 \(i\) 位后

普通插板法不好做，因为 \(x_i\) 的取值有限制，可以考虑对插板法做容斥。枚举有多少个位置不合法

\[总方案数=\sum_{v=0}^{\min(a_i-1,m-1)} \sum_{j=0}^t (-1)^j \binom{t}{j} \binom{p-v-jm+t-1}{t-1} \]

其中 \(v\) 是枚举当前位置放了什么，因为不能顶满，所以 \(v\) 的范围是 \([0,min(a_i-1,m-1)]\) ，然后 \(\binom{t}{j}\) 是选择一些位置让它们不合法，然后 \(\binom{p-v-jm+t-1}{t-1}\) 是插板法计算有多少方案使得至少有 \(j\) 个位置不合法，但是这样子还不能通过这个题，现在是 \(O(n^3)\) 的，我们要优化一维。

观察一下发现容斥的维不可能优化掉，不然容斥个鸡毛。

所以考虑优化掉 \(\sum_{v=0}^{\min(a_i-1,m-1)}\) 这个求和。

先移动一下求和符号，两个求和符号可以调换顺序当且仅当他们里面的内容完全独立无关。

所以：

\[总方案数=\sum_{j=0}^t (-1)^j \binom{t}{j} (\sum_{v=0}^{\min(a_i-1,m-1)} \binom{p-v-jm+t-1}{t-1}) \]

观察到里面的 \(t-1\) 不变，所以结合组合恒等式的10（曲棍球棒恒等式）做差分就可以得到

\[总方案数=\sum_{j=0}^t (-1)^j \binom{t}{j} (\sum_{v=0}^{\min(a_i-1,m-1)} \binom{p-v-jm+t-1}{t-1})\\ =\sum_{j=0}^t (-1)^j \binom{t}{j} (\sum_{k=t-1}^{p-jm+t-1} \binom{k}{t-1}-\sum_{k=t-1}^{p-v-jm+t-2} \binom{k}{t-1})\\ =\sum_{j=0}^t (-1)^j \binom{t}{j} (\binom{p-jm+t}{t}-\binom{p-v-jm+t-1}{t}) \]

现在这个式子的计算就是 \(O(n)\) 的了，所以总复杂度是 \(O(n^2)\)。