利用组合数的性质可以构造出求和公式。
二项式定理[编辑]
![{\displaystyle \sum _{k=0}^{n}C_{k}^{n}x^{n-k}y^{k}=(x+y)^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d993d1f04b0b12ab6c95e09e339e5aed09c961b8)
Example例子:
朱世杰恒等式[编辑]
![{\displaystyle \sum _{k=m}^{n}C_{m}^{k}=C_{m+1}^{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f23d13f49e13f9ded6402faa17e69388bd7d6eac)
证明朱世杰恒等式
|
在方幂和上的应用[编辑]
把多项式转化为组合数,再用朱世杰恒等式求和。[1]
例子: ![{\displaystyle \sum _{k=1}^{n}k^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/514b46af9ae9d53e4a83b5fd2c4ff8b88df20c3b)
![{\displaystyle \sum _{k=1}^{n}k^{2}=\sum _{k=1}^{n}(k^{2}-k+k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34653e8b700dcb1bffb7128febc22ca26fb54342)
|
求多项式的和[编辑]
将多项式转化为组合数的过程一般化,对一个多项式求和有如下公式:
证明: [2][3][4]
![{\displaystyle m=\deg(p)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2851f448d100e717d8d424c2461d3bd0a8efad8)
为m阶多项式,待定成组合数:
代入 ,得到:
帕斯卡矩阵的逆等于自身交错地加上负号,于是可直接求出待定系数:
![{\displaystyle p(k)={\begin{pmatrix}C_{0}^{k-1}&C_{1}^{k-1}&\cdots &C_{m}^{k-1}\end{pmatrix}}{\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\-C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\(-1)^{m}C_{0}^{m}&(-1)^{m-1}C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/674be51ad8feac7f6f8b3b0cff0d93314db0267e)
乘出来的结果也刚好是多项式各阶差分在点1的值。
|
证明: [5]![{\displaystyle m=\deg(p),\Delta p(n)=p(n+1)-p(n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8936d810838cc90219d0df89fc4c699126a5d2b)
设
|
Example例子:
![{\displaystyle p(k)=k,\Delta p(k)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4346f28b918b5488ee370f6b1643fc518f1ba0c)
![{\displaystyle p(1)=1,\Delta p(1)=1,\sum _{k=1}^{n}k=C_{1}^{n}+C_{2}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07048229b5587900da67a6a47ab476d770a110dd)
(等差数列求和)
![{\displaystyle p(k)=a+d(k-1),\Delta p(k)=d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b32ae005bb7ec115eecf3f9d239dccf4162a09ed)
![{\displaystyle p(1)=a,\Delta p(1)=d,\sum _{k=1}^{n}[a+d(k-1)]=aC_{1}^{n}+dC_{2}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23a5714bc297e2064969f92760ce688ee2eea8b2)
![{\displaystyle p(k)=k^{2},\Delta p(k)=2k+1,\Delta ^{2}p(k)=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1ac87cec927deecab5c0bedf6158767bec41074)
![{\displaystyle p(1)=1,\Delta p(1)=3,\Delta ^{2}p(1)=2,\sum _{k=1}^{n}k^{2}=C_{1}^{n}+3C_{2}^{n}+2C_{3}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e2ed32fd91026568114204ae261c042b4168309)
![{\displaystyle p(k)=k^{3},\Delta p(k)=3k^{2}+3k+1,\Delta ^{2}p(k)=3(2k+1)+3=6k+6,\Delta ^{3}p(k)=6,\sum _{k=1}^{n}k^{3}=C_{1}^{n}+7C_{2}^{n}+12C_{3}^{n}+6C_{4}^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c990c70adf32bf4f57b48926ca9309ff5bd068a)
范德蒙恒等式[编辑]
![{\displaystyle \sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}=C_{n}^{a+b}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78a7d74e185a049fdcd823e43f525ed90daa2400)
参考资料[编辑]