wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

[[ item.c ]]

二项式定理

## 二项式定理常用恒等式
**吸收恒等式**
```math
\displaystyle
k\binom{r}{k} = r\binom{r-1}{k-1}
```

**上指标反转**
```math
\displaystyle
\binom{r}{k} = (-1)^k \binom{k-r-1}{k}
```

**三项式版恒等式**
```math
\displaystyle
\binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}
```
> 这个直接展开即可证明

**加法恒等式**
```math
\displaystyle
\binom{r}{k} = \binom{r-1}{k-1} + \binom{r-1}{k}
```
> 这个证明，最方便的是组合意义，最后一个元素选 or 不选

**平行求和法**
```math
\displaystyle
\sum_{k \leqslant n}\binom{r+k}{k} = \binom{r+n+1}{n}
```
> 证明如下，根据加法公式
```math
\binom{r+n+1}{n} = \binom{r+n}{n} + \binom{r+n}{n-1} = \binom{r+n}{n} + \binom{r+n-1}{n-1} + \binom{r+n-2}{n-2} + \cdots \\
= \sum_{k = 0}^{n} \binom{r+k}{k}
```

**上指标求和**
```math
\displaystyle
\sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}
```
> 证明如下，同样应用加法公式
```math
\binom{n+1}{m+1} = \binom{n}{m+1} + \binom{n}{m} = \binom{n-1}{m+1} + \binom{n-1}{m} + \binom{n}{m} \\
\quad \\
= \binom{n-2}{m+1} + \binom{n-2}{m} + \binom{n-1}{m} + \binom{n}{m} \\
\vdots \\
= \sum_{k=0}^{n}\binom{k}{m}
```

**范德蒙卷积**
```math
\displaystyle
\sum_{k=0}^{n} \binom{m_1}{k} \binom{m_2}{n - k} = \binom{m_1 + m_2}{n}
```
> 证明，考虑$$(1+x)^{m_1} \cdot (1+x)^{m_2} = (1+x)^{m_1 + m_2}$$，等式两边$$x^n$$的项系数相等

## 二项式定理扩展等式
**来自排序文献**
化简
```math
\displaystyle
T = \sum_{k=0}^{n} k \binom{m-k-1}{m-n-1} / \binom{m}{n} \\
\quad \\
\textbf{let }S = \sum_{k=0}^{n} k \binom{m-k-1}{m-n-1}
```
可以考虑利用**吸收恒等式**
> 吸收恒等式，有
```math
\displaystyle
S = \sum_{k}m \binom{m-k-1}{m-n-1} - \sum_{k}(m-k)\binom{m-k-1}{m-n-1} \\
\quad \\
= m \sum_k\binom{m-k-1}{m-n-1} - (m-n) \sum_k\binom{m-k}{m-n} = mA - (m-n)B
```

> 那么，对于$$B$$，考虑换元，$$k \in [0, n], m - k \in [m-n, m]$$，令$$t = m - k$$
```math
\displaystyle
\sum_{t \in [m-n, m]} \binom{t}{m-n} = \sum_{t \in [0, m]} \binom{t}{m-n} = \binom{m+1}{m-n+1}
```
这里是因为$$t < m-n$$的项都是`0`

> 对于$$A$$，是一样的，令$$m-1 = m'$$，化简后有
```math
\displaystyle
(m'+1)\binom{m'+1}{m'-n+1} = m\binom{m}{m-n}
```

> 综上，我们有
```math
\displaystyle
S = m\binom{m}{m-n} - (m-n)\binom{m+1}{m-n+1} \\
\quad \\
= m\binom{m}{m-n} - (m-n)\dfrac{m+1}{m-n+1}\binom{m}{m-n} = \dfrac{n}{m-n+1}\binom{m}{m-n}
```

所以，我们有$$T = \dfrac{n}{m-n+1}$$

## 一些问题
### 2025暑期多校训练营9
#### G
**[Permutation](https://ac.nowcoder.com/acm/contest/108306/G)**
给定一个排列和初始为空的序列`a`，执行以下操作**恰好$$n$$次**，每次操作删除最左边或者最右边的数字
或者将最小值加入到`a`的末尾，问最后能有多少个不同的$$a$$

**算法分析**
排列，那么考虑哪些区间以$$x$$作为最小值？不难想到**小根笛卡尔树**

考虑**钦定**$$a$$中一定要选到$$x$$，那么此时所有$$< x$$的数都要被删除，只保留一段都是$$\geqslant x$$的区间
而这样的区间，**恰好是**小根笛卡尔树，$$x$$及其子树$$sub(x)$$，对应原序列中**连续的一段$$\geqslant x$$**的数
而所有$$< x$$的数，恰好在区间的两端，完全可以符合题中的要求，从两端依次删去

也就是说，你要选到$$x$$，就**必须花费**$$del = n - sz(x)$$的代价把$$< x$$的数全部删掉
那么$$n$$次操作中，你只有$$n - del = sz(x)$$的机会来构建`a`数组

不难发现，$$a$$数组的大小$$k = [1\cdots sz(x)]$$都可以，考虑构建大小为$$k$$的数组中，选哪些数？
这是一个**多重集合的组合问题**，只不过我们钦定$$x$$一定要选

能选的数，一定是$$x$$往上到根节点的所有数，分别选了
```math
\displaystyle
i_1 + i_2 + \cdots + i_{dep(x)} = k
```
我们规定$$i(dep(x)) > 0$$，所以做换元，$$j(dep(x)) = i(dep(x)) - 1$$，问题转化成
```math
\displaystyle
i_1 + i_2 + \cdots + j_{dep(x)} = k - 1,\quad  k \geqslant 1
```
不定方程非负整数解的个数，方案数是$$\displaystyle \binom{k-1 + dep(x)-1}{k-1}$$
那么，总的来看，方案数是
```math
\displaystyle
\sum_{k = 1}^{sz(x)} \binom{k-1+dep(x) - 1}{k-1}
```
根据**平行求和法**，$$k' = k - 1$$
```math
\displaystyle
\sum_{k'=0}^{sz(x) - 1} \binom{A + k'}{k'} = \binom{A + sz(x)}{sz(x) - 1} = \binom{dep(x) - 1 + sz(x)}{sz(x) - 1}
```
这就是答案，把笛卡尔树上每个$$x$$加起来，就是最后所求

看完文章有啥想法

算法小站

wiki 主题

数学

二项式定理

目录