组合数学
组合数定义式
\(\binom{n}{m}=\frac{n!}{m!(n - m)!}\)，表示 \(n\) 个数中选 \(m\) 个。
下降幂
\(n^{\underline{m}}=n(n - 1)(n - 2)\cdots(n - m + 1)\)
上升幂
\(n^{\overline{m}}=n(n + 1)(n + 2)\cdots(n + m - 1)\)
相关结论
- \(n^{\overline{m}}=(n + m - 1)^{\underline{m}}\)，用于处理上升幂
- \(n^{\underline{m}}=(-1)^{m}(m - n - 1)^{\overline{m}}\)，用于处理 \(n < 0\) 情况
- \(\binom{n}{m}=\frac{n^{\underline{m}}}{m!}\)
特殊情况
- \(0^{0}=0!=x^{0}=1\)
- 当 \(m>n\) 或 \(m<0\) 时，\(\binom{n}{m}=0\)
- 当 \(m = 0\) 或 \(m=n\) 时，\(\binom{n}{0}=\binom{n}{n}=1\)
各种定理
1. 递推式（春游）
\(\binom{n}{k}=\binom{n - 1}{k}+\binom{n - 1}{k - 1}\)
2. 翻转
\(\binom{n}{k}=\binom{n}{n - k}\)，条件：\(n>0\)
3. 吸收公式（用于处理常数或参数）
- \(k\binom{n}{k}=n\binom{n - 1}{k - 1}\)，用组合数定义展开证明
- \(\frac{1}{k}\binom{n}{k}=\frac{1}{n}\binom{n - 1}{k - 1}\)
- \((n - k)\binom{n}{k}=n\binom{n - 1}{k}\)，用“春游”证明
4. 上指标反转
\(\binom{n}{k}=(-1)^{k}\binom{k - n - 1}{k}\)，用下降幂性质证
5. 二项式定理
- \((x + y)^{n}=\sum_{k = 0}^{n}\binom{n}{k}x^{k}y^{n - k}\)
- 当 \(n\in\mathbb{R}\) 且 \(|x|<|y|\) 时，\((x + y)^{n}=\sum_{k = 0}^{+\infty}\binom{n}{k}x^{k}y^{n - k}\)（泰勒展开可证明）
- 常用：
- \((x + 1)^{n}=\sum_{k = 0}^{n}\binom{n}{k}x^{k}\)
- \((x - 1)^{n}=\sum_{k = 0}^{n}(-1)^{n - k}\binom{n}{k}x^{k}\)
- \(\binom{n}{k}\)是\((x + 1)^{n}\)的\(x^k\)项系数。这可以用来证明其他定理。（如lucas）
6.
- \(\sum_{k = 0}^{n}\binom{n}{k}=2^{n}\)，是二项式定理中 \(x = y = 1\) 的情况
- 可用于有类似下指标求和的式子：\(\sum_{k = m}^{n}\binom{n}{k}=\sum_{k = 0}^{n}\binom{n}{k}-\sum_{k = 0}^{m - 1}\binom{n}{k}=2^{n}-2^{m}\)
7. 平行求和
\(\sum_{k = 0}^{m}\binom{n + k}{k}=\binom{n + m + 1}{m}\)，右边用“春游”展开可证
8. 上指标求和
\(\sum_{k = 0}^{n}\binom{k}{m}=\binom{n + 1}{m + 1}\)，用“春游”展开
9.
\(\sum_{k = 0}^{m}(-1)^{k}\binom{n}{k}=(-1)^{m}\binom{n - 1}{m}\)
10. 卷积
- \(\sum_{k}\binom{r}{k}\binom{s}{n - k}=\binom{r + s}{n}\)，从 \(r + s\) 个元素中选 \(n\) 个，等于从 \(r\) 中选 \(k\) 个，从 \(s\) 中选 \(n - k\) 个，\(k\in(0,n)\)
- 该式用于处理大部分的 \(\sum\)
- 变型：\(\sum_{k}\binom{-r}{m + k}\binom{-s}{n - k}(-1)^{k}=(-1)^{m + n}\binom{-r - s}{m + n}\)
11.
\(\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r - k}{m - k}\)
- 用定义展开证明
- 组合意义：从 \(r\) 中选 \(m\) 个，再从这 \(m\) 个中选 \(k\) 个，等价于先选 \(k\) 个要用的，再从 \(r - k\) 个中选 \(m - k\) 个陪衬的。
多项式系数
- \(n\) 个不同的物品分成 \(m\) 组，第 \(i\) 组有 \(a_{i}\) 个，总方案数：\(\frac{n!}{\prod_{i = 1}^{m}a_{i}!}\)（\(\sum_{i = 1}^{m}a_{i}=n\)），可写作：\(\binom{n}{a_{1},a_{2},\cdots,a_{m}}\)
- \(\binom{n}{a_{1},a_{2},\cdots,a_{m}}=\prod_{k = 1}^{m - 1}\binom{\sum_{i = k}^{k}a_{i}}{\sum_{i=k+1}a_{i}}\)
[注：上文是用AI把笔记的照片转文字的来的，可能会有错]
取模意义下的组合数
一些引理
-
\(\binom{p}{n} \bmod p = [n = 0 \vee n = p]\)，
证明：\(\binom{p}{n}=\frac{p!}{n!(p - n)!}\)，因为分子只有一个p，分母只有在n=p或n=0时有p。
- \[\begin{align} (a + b)^p &\equiv a^p + b^p \pmod{p}\\ 证明 ：(a + b)^p &\equiv \sum_{n = 0}^{p} \binom{p}{n} a^{n}b^{p - n} \pmod{p}（二项式定理）\\ &\equiv a^p + b^p \pmod{p}（引理一） \end{align} \]
Lucas定理
一般来说，我们预处理阶乘，然后用定义式来计算组合数，但是当遇到n和m很大的时候，不支持\(O(n)\)的复杂度时，就要用到Lucas定理。
对于质数 \(p\),
\[\binom{n}{m} \bmod p = \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \cdot \binom{n \bmod p}{m \bmod p} \bmod p \]证明：
$\binom{n}{m} $ 是 \((x + 1)^n\) 的 \(x^m\) 项系数。
拓展Lucas
用于处理模数M不是质数的情况。
设
\[M = p_1^{\alpha_1}\cdots p_m^{\alpha_m} \]我们可以求出每一个 \(\binom{n}{m} \bmod p^{\alpha_i}\)，然后CRT合并就行
我们吧n!，m!和\(（n-m）!\)中，所有p的因子提出来，
会有形如 \(\frac{\frac{n!}{p^{x}}}{\frac{m!}{p^{y}}\frac{(n - m)!}{p^{z}}}p^{x - y - z}\bmod p^{\alpha}\)的式子。
现在分母可以exgcd求逆了，我们只需要求形如下面这样的式子：
\[\frac{n!}{p^{x}}\bmod p^{\alpha} \]\[n!=p^{\lfloor \frac{n}{p}\rfloor}\cdot\left(\left\lfloor \frac{n}{p}\right\rfloor\right)!\cdot\left(\prod_{i,\gcd(i,p)=1}^{p^{\alpha}}i\right)^{\lfloor \frac{n}{p^{\alpha}}\rfloor}\cdot\left(\prod_{i,\gcd(i,p)=1}^{n\bmod p^{\alpha}}i\right) \]前面两个是n中p的倍数，第三个是n对p的循环节，最后一个是n对p的余数。
因为要求的是n！扣掉p的因子对\(p^\alpha\)取模，所以把\(p^{\lfloor \frac{n}{p}\rfloor}\)直接扔掉，然后继续递归求解\(\left(\left\lfloor \frac{n}{p}\right\rfloor\right)!\)
感觉这玩意非常难写，而且好像用处不大。
标签：lfloor,frac,组合,sum,rfloor,数学,binom,bmod From： https://www.cnblogs.com/water-flower/p/18686837