组合数学的常见式子
递推式
\[\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m} \]证明(组合意义):
同学和老师出去春游共有 \(n\) 个人，一项活动只能去 \(m\) 个人,考虑老师去或不去，老师去在 \(n-1\) 个同学中选 \(m-1\) 个，否则在 \(n-1\) 个同学中选 \(m\) 个。
特征:
加号连接，两个组合数的 \(n\) 相同, \(m\) 相差1。
对称性
\[\binom{n}{m}=\binom{n}{n-m} \]对于\(n,m\in Z\)
证明(组合意义):
从 \(n\) 个数中选 \(m\) 个数，等同于从 \(n\) 个数中选 \(n-m\) 个数不选。
吸收/相伴等式
\[\frac{\binom{n}{m} }{\binom{n-1}{m-1}}=\frac{n}{m} \]\[\frac{\binom{n}{m} }{\binom{n-1}{m}}=\frac{n}{n-m} \]\[\frac{\binom{n}{m} }{\binom{n}{m-1}}=\frac{n-m+1}{m} \]证明：
将式子转为阶乘的形式，即可证明等式两边相等。
特征:
除号连接，分号上为 \(\binom{n}{m}\) ，分号下的 \(n\) 或者 \(m\) 减一。
上指标反转
\[\binom{n}{m}=\left ( -1 \right ) ^{m} \binom{m-n-1}{m} \]证明：
\[\binom{r}{m}=\binom{-n}{m}=\frac{-n\left(-n-1\right )\left(-n-2\right )...\left(-n-m+1\right )}{m!} \]\[=\left(-1\right)^{m}\frac {n\left(n+1\right)\left(n+2\right)...\left(n+m-1\right)}{m!} \]\[=\left(-1\right)^{m}\binom{n+m-1}{m} \]\[=\left(-1\right)^{m}\binom{m-r-1}{m} \]特征：
有一个(-1)^m。
三项式系数恒等式
\[\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k} \]证明(组合意义):
\(n\) 个数选出 \(m\) 个再在 \(m\) 个中选 \(k\) ，等同与从 \(n\) 个数中选 \(k\) ,在从 \(n-k\) 中找 \(m-k\) 。（因为等式右边先选出 \(k\) 在找 \(m-k\) 与 \(k\) 一起等同于一开始选 \(m\) ）
特征：
第一个组合数的 \(m\) 等于第二个的 \(n\) 。
上指标求和
\[\sum_{i=0}^{n} \binom{i}{m}=\binom{n+1}{m+1} \]证明(组合意义):
\(n+1\) 个数选出 \(m+1\) 个，考虑最后一个数是第 \(i+1\) 个数，则需要从前 \(i\) 个数中选 \(m\) 个数。
特征：
有 \(\sum\) 以及上指标变化，下指标不变
下指标求和（整行）
\[\sum_{i=0}^{n} \binom{n}{i}=2^n \]证明(组合意义):
\(n\) 个数中任选出 \(0\) 到 \(n\) 个数等于 \(n\) 个数的所以子集，每个数可选可不选，所以共2^n种可能。
特征：
有 \(\sum\) 以及下指标变化，上指标不变
下指标卷积
\[\sum_{i=0}^{k} \binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k} \]证明(组合意义):
\(n\) 个数中选出 \(i\) 个数 从 \(m\) 个数中选 \(k-i\) 个数，等于在 \(n+m\) 个数中选 \(k\)。
特征：
有 \(\sum\) 以及下指标的和不变，上指标不变
上指标卷积
\[\sum_{i=0}^{n} \binom{i}{a}\binom{n-i}{b}=\binom{n+1}{a+b+1} \]证明(组合意义):
\(n\) 个数分成左右两边，左边 \(a\) 中选出 \(i\) 个数 , 右边从 \(b\) 个数中选 \(n-1\) 个数，等于给原数加一个分隔符，从 \(n+1\) 个数中选 \(a+b+1\)。
特征：
有 \(\sum\) 以及下指标的和不变，上指标不变
练习题
1.
\[\sum_{i=0}^{m}\binom{n+i}{i} \]\[\sum_{i=0}^{m}\binom{n+i}{i}=\sum_{i=0}^{m}\binom{n+i}{n} \]对称性
\[=\binom{n+m+1}{n+1} \]上指标求和
2.
给 \(q\) 组询问，每次给出 \(n\) , \(m\) ，求 \(\sum_{i=0}^{m}\binom{n}{i}\)
q, n, m ≤ 105，对 1e9 + 7 取模。
1.当已知 \(\sum_{i=0}^{m}\binom{n}{i}\)求 \(\sum_{i=0}^{m}\binom{n+1}{i}\)时，因为
以下面的表格为例,第3行等于第2行加第1行.（第一行和第二行的和均为\(\sum_{i=0}^{m}\binom{n}{i}\)，第三行的和为\(\sum_{i=0}^{m}\binom{n+1}{i}+\binom{n}{m}\)）
| \(\binom{n}{0}\) | \(\binom{n}{1}\) | \(\binom{n}{2}\) | \(\binom{n}{3}\) | |
|---|---|---|---|---|
| \(\binom{n}{0}\) | \(\binom{n}{1}\) | \(\binom{n}{2}\) | \(\binom{n}{3}\) | |
| \(\binom{n+1}{0}\) | \(\binom{n+1}{1}\) | \(\binom{n+1}{2}\) | \(\binom{n+1}{3}\) | \(\binom{n}{3}\) |
2.当已知 \(\sum_{i=0}^{m}\binom{n}{i}\)求 \(\sum_{i=0}^{m+1}\binom{n}{i}\)时
\[\sum_{i=0}^{m+1}\binom{n}{i}=\sum_{i=0}{m}\binom{n}{i}+\binom{n}{m+1} \]所以每一步都可以 \(o(1)\) 转移，莫队离线处理。
3.下指标点积
\[\sum_{i=0}{m}\binom{n}{i}\binom{m}{i}=\sum_{i=0}{m}\binom{n}{i}\binom{m}{m-i} \]上指标为常数，下指标和为常数（下指标卷积）
\[=\binom{n+m}{m} \]4.
求
\[\sum_{i=m}^{n}(-1)^i\binom{n}{i}\binom{i}{m} \]\[\sum_{i=m}^{n}(-1)^i\binom{n}{i}\binom{i}{m}=\sum_{i=m}^{n}(-1)^i\binom{n}{m}\binom{n-m}{i-m} \]三项式系数恒等式
\[=\binom{n}{m}\sum_{i=m}^{n}(-1)^i\binom{n-m}{i-m} \\ = \] 标签：right,组合,sum,个数,指标,数学,binom,left From： https://www.cnblogs.com/storms11/p/18281575