组合计数

2025-01-21 17:03:25

交换求和顺序：

$\sum_{i=1}^{n} \sigma_{0}(i)=\sum_{i=1}^{n} \sum_{d \mid i} 1=\sum_{d=1}^{n} \sum_{i=1}^{n}[d \mid i]=\sum_{d=1}^{n}\left\lfloor\frac{n}{d}\right\rfloor $
给定序列 $a$ ，求其所有区间的区间和：答案是 $\sum_{i=1}^{n} a_{i} \times i \times(n-i+1) $。

\[(a + b)^{n} = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^{k} \]

\[\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \quad(n \geq m \geq k) \]

先从 $n$ 个中选出 $m$ 个，再从选出的 $m$ 个里面选出 $k$ 个 $\Longleftrightarrow$ 先从 $n$ 个中选出最终的 $k$ 个，再从剩下的 $n-k$ 个中选出第一步选中但第二步末选中的 $m-k$ 个。

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

利用$\binom{n}{m}= \frac{n!}{m!(n-m)!}$ 展开即可得到证明。

\[\sum_{j=w}^{k} \binom{x}{j} = \sum_{i=1}{x}\binom{i-1}{w-1}\binom{n-i}{k-w} \]

相当于从 $n$ 个元素中选出 $k$ 个，但前 $x$ 个元素中必须选出至少 $w$ 个；这等价于选出的第 $w$ 个元素的位置在 $x$ 之前。

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

考察 $n+m+1$ 元集的 $n+1$ 元子集的最后一个元素。

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

从 $n+m$ 个元素中选出前 $k$ 个，考察前 $n$ 个元素中选出的数的个数。

有 $n$ 种物品，第 $i$ 种物品有 $a_i$ 个，认为相同物品之间互不区分，则将这 $\sum a_i$ 个物品排列的方案数为

\[\frac{(\sum_{i=1}^n a_i)!}{\prod a_i!} \]

将 $n$ 个相同的物品无序地分为 $m$ 组，每组都非空的方案数：相当于往 $n-1$ 个空位里面插入 $m-1$ 个板，因此方案数为 $\binom{n-1}{m-1}$。

如果不要求每组非空，考虑直接给每组都加一个，方案数为 $\binom{n+m-1}{m-1}$。

求方程 $\sum_{i=1}^m x_i = n, x_i \in \mathbb{Z}, x_i \geq 0$ 的整数解个数：$\binom{n+m-1}{m-1}$。

如果再给出序列 $y_1...m$，要求 $x_i \geq y_i$？
相当于 $\sum_{i=1}^m (x_i - y_i) = n - \sum_{i=1}^m y_i$，故方案数为 $\binom{n+m-\sum_{i=1}^m y_i-1}{m-1}$。

如果要求 $x_i \leq y_i$ 呢？此时有两种做法：

DP：$f(i, j)$ 表示前 $i$ 个数和为 $j$ 的方案数，转移用前缀和优化。$O(nm)$
容斥：钦定 $S \subseteq \{1, 2, \cdots, m\}$ 以内的限制不被满足，其余的不管，转化为要求 $x_i > y_i$ 的情形。$O(2^m \times \text{poly}(m))$

求有多少长为 $2n$ 的合法括号序列。答案记作 $C_n$，这就是卡特兰数。

把左括号看成往右走，有括号看成往上走，那么这个就对应一条 $(0,0)$ 到 $(n,n)$ 的路径，且不能穿过 $y=x$（但可以触碰）。

路径一共有 $\binom{2n}{n}$ 种，考虑怎么算穿过的方案数，也就是触碰了 $y=x+1$ 这条直线。

我们在最后触碰的位置 $(p, p+1)$ 把 $(0,0) \rightarrow (p, p+1)$ 这一部分翻折，发现就唯一对应一条 $(-1,1) \rightarrow (n,n)$ 的路径，于是方案数就是 $\binom{2n}{n-1}$。于是我们有以下这样的关系

\[C_n = \binom{2n}{n} - \binom{2n}{n-1} \]

这就是卡特兰数。

另一方面，从括号序列的角度，我们还能给出另一种递推式：枚举第一个左括号匹配的右括号的位置为 $2k$，有

\[C_n = \sum_{k=1}^{n} C_{k-1} C_{n-k} \]

其中 $C_0 = 1$。

卡特兰数 $C_n$ 常用套路