代數/本書課文/求和/組合數求和

利用組合數的性質可以構造出求和公式。

二項式定理

$\sum _{k=0}^{n}C_{k}^{n}x^{n-k}y^{k}=(x+y)^{n}$

Example

例子：

$\sum _{k=0}^{n}C_{k}^{n}=2^{n}$

朱世傑恆等式

$\sum _{k=m}^{n}C_{m}^{k}=C_{m+1}^{n+1}$

證明朱世傑恆等式 ${\begin{aligned}\sum _{k=m}^{n}C_{m}^{k}&=C_{m}^{m}+C_{m}^{m+1}+C_{m}^{m+2}+\dots +C_{m}^{n}\\~&=C_{m+1}^{m+1}+C_{m}^{m+1}+C_{m}^{m+2}+\dots +C_{m}^{n}\\~&=C_{m+1}^{m+2}+C_{m}^{m+2}+\dots +C_{m}^{n}\\~&=C_{m+1}^{m+3}+\dots +C_{m}^{n}=C_{m+1}^{n+1}\end{aligned}}$

在方冪和上的應用

把多項式轉化為組合數，再用朱世傑恆等式求和。

例子：$\sum _{k=1}^{n}k^{2}$ $\sum _{k=1}^{n}k^{2}=\sum _{k=1}^{n}(k^{2}-k+k)$ $=\sum _{k=1}^{n}(2C_{2}^{k}+C_{1}^{k})=2C_{3}^{n+1}+C_{2}^{n+1}$

求多項式的和

將多項式轉化為組合數的過程一般化，對一個多項式求和有如下公式：

證明：$\sum _{k=1}^{n}p(k)={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&\cdots &C_{m+1}^{n}\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}}$ $m=\deg(p)$ $p(k)$為m階多項式，待定成組合數： $p(k)={\begin{pmatrix}C_{0}^{k-1}&C_{1}^{k-1}&\cdots &C_{m}^{k-1}\end{pmatrix}}{\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{m+1}\end{pmatrix}}$ 代入$k=1,2,\dots ,m+1$，得到： ${\begin{pmatrix}p(1)\\p(2)\\\vdots \\p(m+1)\end{pmatrix}}={\begin{pmatrix}C_{0}^{0}&0&\cdots &0\\C_{0}^{1}&C_{1}^{1}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\C_{0}^{m}&C_{1}^{m}&\cdots &C_{m}^{m}\\\end{pmatrix}}{\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{m+1}\end{pmatrix}}$ 帕斯卡矩陣的逆等於自身交錯地加上負號，於是可直接求出待定係數： ${\begin{pmatrix}a_{1}\\a_{2}\\\vdots \\a_{m+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}}$ $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}}$ $\sum _{k=1}^{n}p(k)={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&\cdots &C_{m+1}^{n}\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}}$ 乘出來的結果也剛好是多項式各階差分在點1的值。

證明：$\sum _{k=1}^{n}p(k)=\sum _{j=1}^{m+1}C_{j}^{n}\Delta ^{j-1}p(1)$ $m=\deg(p),\Delta p(n)=p(n+1)-p(n)$ 設$p(k)=\sum _{j=0}^{m}a_{j}C_{j}^{k-1}=a_{0}+a_{1}C_{1}^{k-1}+a_{2}C_{2}^{k-1}+\dots +a_{m}C_{m}^{k-1}$ $p(1)=a_{0}$ $\Delta C_{l}^{k}=C_{l}^{k+1}-C_{l}^{k}=C_{l-1}^{k}$ $\Delta ^{j}p(k)=a_{j}+a_{j+1}C_{1}^{k-1}+a_{j+2}C_{2}^{k-1}+\dots +a_{m}C_{m-j}^{k-1}$ $\Delta ^{j}p(1)=a_{j}$ $p(k)=\sum _{j=0}^{m}C_{j}^{k-1}\Delta ^{j}p(1)$ $\sum _{k=1}^{n}p(k)=\sum _{j=0}^{m}C_{j+1}^{n}\Delta ^{j}p(1)=\sum _{j=1}^{m+1}C_{j}^{n}\Delta ^{j-1}p(1)$

Example

例子：

$\sum _{i=1}^{n}i^{1}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}\end{pmatrix}}{\begin{pmatrix}1&0\\-1&1\end{pmatrix}}{\begin{pmatrix}1\\2\end{pmatrix}}=C_{1}^{n}+C_{2}^{n}$

$p(k)=k,\Delta p(k)=1$

$p(1)=1,\Delta p(1)=1,\sum _{k=1}^{n}k=C_{1}^{n}+C_{2}^{n}$

$\sum _{i=1}^{n}[a+d(i-1)]={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}\end{pmatrix}}{\begin{pmatrix}1&0\\-1&1\end{pmatrix}}{\begin{pmatrix}a\\a+d\end{pmatrix}}=aC_{1}^{n}+dC_{2}^{n}$（等差數列求和）

$p(k)=a+d(k-1),\Delta p(k)=d$

$p(1)=a,\Delta p(1)=d,\sum _{k=1}^{n}[a+d(k-1)]=aC_{1}^{n}+dC_{2}^{n}$

$\sum _{i=1}^{n}i^{2}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0\\-1&1&0\\1&-2&1\end{pmatrix}}{\begin{pmatrix}1^{2}\\2^{2}\\3^{2}\end{pmatrix}}=C_{1}^{n}+3C_{2}^{n}+2C_{3}^{n}$

$p(k)=k^{2},\Delta p(k)=2k+1,\Delta ^{2}p(k)=2$

$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}$

$\sum _{i=1}^{n}i^{3}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0\\-1&1&0&0\\1&-2&1&0\\-1&3&-3&1\end{pmatrix}}{\begin{pmatrix}1^{3}\\2^{3}\\3^{3}\\4^{3}\end{pmatrix}}=C_{1}^{n}+7C_{2}^{n}+12C_{3}^{n}+6C_{4}^{n}$

$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}$

$\sum _{i=1}^{n}i^{4}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}&C_{5}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0&0\\-1&1&0&0&0\\1&-2&1&0&0\\-1&3&-3&1&0\\1&-4&6&-4&1\end{pmatrix}}{\begin{pmatrix}1^{4}\\2^{4}\\3^{4}\\4^{4}\\5^{4}\end{pmatrix}}=C_{1}^{n}+15C_{2}^{n}+50C_{3}^{n}+60C_{4}^{n}+24C_{5}^{n}$

$\sum _{i=1}^{n}i^{5}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}&C_{5}^{n}&C_{6}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0&0&0\\-1&1&0&0&0&0\\1&-2&1&0&0&0\\-1&3&-3&1&0&0\\1&-4&6&-4&1&0\\-1&5&-10&10&-5&1\end{pmatrix}}{\begin{pmatrix}1^{5}\\2^{5}\\3^{5}\\4^{5}\\5^{5}\\6^{5}\end{pmatrix}}=C_{1}^{n}+31C_{2}^{n}+180C_{3}^{n}+390C_{4}^{n}+360C_{5}^{n}+120C_{6}^{n}$

$\sum _{i=1}^{n}(2i-1)^{2}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0\\-1&1&0\\1&-2&1\end{pmatrix}}{\begin{pmatrix}1^{2}\\3^{2}\\5^{2}\end{pmatrix}}=C_{1}^{n}+8C_{2}^{n}+8C_{3}^{n}$

$\sum _{i=1}^{n}(3i-2)^{3}={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0\\-1&1&0&0\\1&-2&1&0\\-1&3&-3&1\end{pmatrix}}{\begin{pmatrix}1^{3}\\4^{3}\\7^{3}\\10^{3}\end{pmatrix}}=C_{1}^{n}+63C_{2}^{n}+216C_{3}^{n}+162C_{4}^{n}$

$\sum _{i=1}^{n}\left(i^{3}+2i+1\right)={\begin{pmatrix}C_{1}^{n}&C_{2}^{n}&C_{3}^{n}&C_{4}^{n}\end{pmatrix}}{\begin{pmatrix}1&0&0&0\\-1&1&0&0\\1&-2&1&0\\-1&3&-3&1\end{pmatrix}}{\begin{pmatrix}4\\13\\34\\73\end{pmatrix}}=4C_{1}^{n}+9C_{2}^{n}+12C_{3}^{n}+6C_{4}^{n}$

范德蒙恆等式

$\sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}=C_{n}^{a+b}$

證明範德蒙恆等式 甲班有a個同學，乙班有b個同學，從兩個班中選出n名有$C_{n}^{a+b}$種方法。 從甲班選k名，從乙班選n-k名有$C_{k}^{a}C_{n-k}^{b}$種方法，考慮所有情況k=0,1,...,n，從兩個班中選出n名有$\sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}$種方法。