只是之前写过的，拿出来新开个专题
\[\dbinom n m=\dbinom{n}{n-m}\tag{1} \]
组合推理:选 \(m\) 的和选 \(m\) 的补集的情况数是一样的
\[\dbinom n m=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\tag{2} \]
组合推理:考虑选不选第 \(n\) 个，不选的情况为 \(\dbinom{n-1}{m}\)，选的情况为 \(\dbinom{n-1}{m-1}\)
\[k\dbinom nk=n\dbinom {n-1}{k-1}\tag{3} \]
吸收恒等式，组合意义为从 \(n\) 个人中选 \(k\) 个人，并指定一人成为队长，由组合数定义也可推出，作为组合数其中一种推导式使用，可以与这个恒等式相搭配：\((n−k)\dbinom nk=n\dbinom {n-1}k\)，实现组合数上标下标的增减
\[\dbinom rm\dbinom mk=\dbinom rk \dbinom {r-k}{m-k}\tag{4} \]
组合推理：左式的组合意义是从 \(r\) 个中选 \(m\) 个，再从这 \(m\) 个中选 \(k\) 个，所以可以先从 \(r\) 个中选 \(k\) 个，再从剩下的 \(r-k\) 个中选剩下的 \(m-k\) 个
\[ \sum\limits_{k=0}^n \dbinom{m_1}{k} \dbinom{m_2}{n-k}=\dbinom{m_1+m_2}{n}\tag{5} \]
两种证明：
- 组合意义
把 \(m_1+m_2\) 个东西分成个数分别为 \(m_1\) 和 \(m_2\) 的两份，然后从这两份中取总计 \(n\) 份的东西
- 二项式定理
\[\begin{aligned} (1+x)^{m_1}(1+x)^{m_2} & = (1+x)^{m_1+m_2}\\ \sum\limits_{i=1}^{m_1}x^i\dbinom{m_1}{i}\sum\limits_{i=1}^{m_2}x^i\dbinom{m_2}{i} & = \sum\limits_{i=1}^{m_1+m_2}x^i\dbinom{m_1+m_2}{i} \end{aligned} \]
\(\dbinom{m_1+m_2}{n}\) 就是 \(x^{n}\) 的系数
因为 \(x^n=x^{n-i}x^i\) (显然吧)
所以易得， \(\dbinom{m_1+m_2}{n}\) 就等于 \(\sum\limits_{i=0}^n \dbinom{m_1}{i} \dbinom{m_2}{n-i}\)
\[\sum\limits^n_{i=1}\dbinom ni^2=\dbinom{2n}n\tag{6} \]
这是上式的特殊情况，取 \(m_1=m_2\)
\[\sum\limits^{n}_{i=1}i\dbinom ni=n2^{n-1}\tag{7} \]
证明：
\[(1+x)^n=\sum\limits^n_{i=0}\dbinom ni x^i \]
把此式两边求导，得到：
\[n(1+x)^{n-1}=\sum\limits^n_{i=1}i\dbinom ni x^{i-1} \]
将 \(x=1\) 代入，即是原式
\[n(n+1)2^{n-2}=\sum^n_{i=1}i^2\dbinom ni\tag{8} \]
这个式子是对上式的进一步求导，不再赘述，其实只要可以的话，可以得到 \(\sum\limits^n_{i=1}i^p\dbinom ni\) 对于任意正整数的恒等式，但求导也会越来越复杂
但是呢，据《组合数学》所言，这东西有组合意义，不会推，谁会证在评论说一下
\[\sum\limits^n_{i=1}i\dbinom ni^2=n\dbinom{2n-1}{n-1}\tag{9} \]
组合推理：考虑 \(n\) 个男生和 \(n\) 个女生，选取 \(n\) 个人组成团队，一个男生是领导（其实在这种意义下 \(\dbinom ni^2\) 应写作 \(\dbinom ni\dbinom n{n-i}\)）
\[\sum\limits^n_{i=0}(-1)^i\dbinom{n}{i}=[n=0]\tag{10} \]
二项式定理的特殊情况，取 \(a=1,b=-1\)，仅当 \(n=0\) 时式子取值为 \(1\)，可以反演
有一个推论：\(\sum\limits^{n}_{2\mid i}\dbinom{n}{i}=\sum\limits^{n}_{2\not\mid i}\dbinom{n}{i}\) 移项即可推出
\[\sum\limits^n_{i=0}(-1)^i\dbinom ni^2= \begin{cases} 0& n\ne 2m&(m\in \mathbb{Z})\\ (-1)^m\dbinom {2m} m& n=2m \end{cases}\tag{11} \]
证明：由 \((1-x^2)^n=(1+x)^n(1-x)^n\) 可推导
\[\begin{aligned} (1-x^2)^n&=(1+x)^n(1-x)^n\\ \sum\limits^n_{i=0}(-1)^i\dbinom nix^{2i}&=\sum\limits^n_{i=0}\dbinom nix^{i}\sum\limits^n_{i=0}(-1)^i\dbinom nix^{i} \end{aligned} \]
对着这个式子可以推出 \(x^n\) 的系数，对于左边式子来说，只有 \(n\) 为偶数时才有系数，对于 \(n\) 为奇数，系数为 \((-1)^m\dbinom{2m}m\)，而右边式子 \(x^n\) 的系数为 \(\sum\limits^n_{i=0}(-1)^i\dbinom{n}{n-i}\dbinom ni=\sum\limits^n_{i=0}(-1)^i\dbinom ni^2\)，系数相等，由此得证
\[\sum\limits^n_{i=0}\dbinom ni =2^n\tag{12} \]
二项式定理特殊情况，\(a=1,b=1\)
组合意义：\(\dbinom ni\) 表示 n 个元素中含 i 个元素的子集数量，求和即为 n 个元素的子集数量 \(2^n\)
\[\sum\limits^n_{i=0}\dbinom ik=\dbinom{n+1}{k+1}\tag{13} \]
组合推理：在 \(n+1\) 个球里拿 \(k+1\) 个，最后一个拿的是第 \(i\) 个，则情况数为 \(\dbinom ik\)，累加即为总数——\(\dbinom{n+1}{k+1}\)
\[\sum\limits^n_{i=0}\dbinom {m+i}i=\dbinom{n+m+1}{n}\tag{14} \]
证明（会用到 \((13)\) ）：
\[\begin{aligned} \sum\limits^n_{i=0}\dbinom {m+i}i&=\sum\limits^n_{i=0}\dbinom {m+i}m\\ &=\sum\limits^{n+m}_{i=m}\dbinom {i}m+0\\ &=\sum\limits^{n+m}_{i=m}\dbinom {i}m+\sum\limits^{m-1}_{i=0}\dbinom {i}m\\ &=\sum\limits^{n+m}_{i=0}\dbinom im\\ &=\dbinom{n+m+1}{m+1}=\dbinom{n+m+1}{n} \end{aligned} \]
这个东西也可以进行扩展到上下均有值的情况
\[\begin{aligned} \sum\limits^n_{i=0}\dbinom {m+i}{s+i}&=\sum\limits^n_{i=0}\dbinom {m+i}{m-s}\\ &=\sum\limits^{n+m}_{i=0}\dbinom i{m-s}\\ &=\dbinom{n+m+1}{m-s+1}=\dbinom{n+m+1}{n+s} \end{aligned} \]
\[\sum\limits^{n}_{i=0}\dbinom nk r^k=(1+r)^n\tag{15} \]
又是二项式定理，\(a=m,b=1\)
\[\sum^n_{i=0}\dbinom {n-i}i=f_{n+1} \quad\texttt{（$f_i$ 为斐波那契数列第 $i$ 项）}\tag{16} \]
设原数列为 \(g_i\) 则显然 \(g_0=f_1,g_1=f_2\)，只需要验证是否存在 \(g_i=g_{i-1}+g_{i-2}\) 即可
然后我们把它放在杨辉三角里，结论就显而易见了：
这个表格最上面一行是 \(g_i\) ，在杨辉三角中表现为对它所在斜线的数进行求和
又因为杨辉三角的递推式，观察表格，显然就能得出结论
我觉得这东西应该有一个巧妙的组合意义，但我想不出来（
原文地址：http://www.cnblogs.com/Rolling-star/p/16817907.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
