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

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

朱世杰恒等式

Template:Robox $\begin{array}{cc}\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{array}$ Template:Robox/Close

在方冪和上的應用

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

Template:ExampleRobox $\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}$ Template:Robox/Close

求多項式的和

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

$p(k)$為m階多項式，待定成組合數：

$p(k)=\left(\begin{array}{cccc}{C}_0^{k-1}& C_1^{k-1}& \cdots & C_m^{k-1}\end{array}\right)\left(\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_{m+1}\end{array}\right)$

代入$k=1,2,\dots ,m+1$，得到：

$\left(\begin{array}{c}p(1)\\ p(2)\\ ⋮\\ p(m+1)\end{array}\right)=\left(\begin{array}{cccc}{C}_0^0& 0& \cdots & 0\\ C_0^1& C_1^1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ C_0^m& C_1^m& \cdots & C_m^m\end{array}\right)\left(\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_{m+1}\end{array}\right)$

帕斯卡矩陣的逆等於自身交錯地加上負號，於是可直接求出待定系數：

$\left(\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_{m+1}\end{array}\right)=\left(\begin{array}{cccc}{C}_0^0& 0& \cdots & 0\\ -C_0^1& C_1^1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ (-1{)}^m{C}_0^m& (-1{)}^{m-1}{C}_1^m& \cdots & C_m^m\end{array}\right)\left(\begin{array}{c}p(1)\\ p(2)\\ ⋮\\ p(m+1)\end{array}\right)$

$p(k)=\left(\begin{array}{cccc}{C}_0^{k-1}& C_1^{k-1}& \cdots & C_m^{k-1}\end{array}\right)\left(\begin{array}{cccc}{C}_0^0& 0& \cdots & 0\\ -C_0^1& C_1^1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ (-1{)}^m{C}_0^m& (-1{)}^{m-1}{C}_1^m& \cdots & C_m^m\end{array}\right)\left(\begin{array}{c}p(1)\\ p(2)\\ ⋮\\ p(m+1)\end{array}\right)$
$\sum _{k=1}^{n}p(k)=\left(\begin{array}{cccc}{C}_1^n& C_2^n& \cdots & C_{m+1}^n\end{array}\right)\left(\begin{array}{cccc}{C}_0^0& 0& \cdots & 0\\ -C_0^1& C_1^1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ (-1{)}^m{C}_0^m& (-1{)}^{m-1}{C}_1^m& \cdots & C_m^m\end{array}\right)\left(\begin{array}{c}p(1)\\ p(2)\\ ⋮\\ p(m+1)\end{array}\right)$

乘出來的結果也剛好是多項式各階差分在點1的值。 Template:Robox/Close Template:Robox 設$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$

$\mathrm{\Delta }{C}_l^k=C_l^{k+1}-C_l^k=C_{l-1}^k$

${\mathrm{\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}$

${\mathrm{\Delta }}^{j}p(1)=a_j$

$p(k)=\sum _{j=0}^m{C}_j^{k-1}{\mathrm{\Delta }}^{j}p(1)$

$\sum _{k=1}^{n}p(k)=\sum _{j=0}^m{C}_{j+1}^n{\mathrm{\Delta }}^{j}p(1)=\sum _{j=1}^{m+1}{C}_j^n{\mathrm{\Delta }}^{j-1}p(1)$

范德蒙恒等式

Template:Robox 甲班有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$種方法。 Template:Robox/Close