查看“︁代數/本書課文/求和/組合數求和”︁的源代码

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

==二項式定理==
{{quote|<math>\sum_{k=0}^n C^n_k x^{n-k}y^k=(x+y)^n</math>}}

{{Example|<math>\sum_{k=0}^n C^n_k=2^n</math>}}

==朱世杰恒等式==
{{quote|<math>\sum_{k=m}^n C^k_m=C^{n+1}_{m+1}</math>}}

{{Robox|theme=3|title=证明朱世杰恒等式}}
<math>\begin{align}
\sum_{k=m}^n C^k_m & =C^m_m+C^{m+1}_m+C^{m+2}_m+\dots+C^n_m\\
~ & =C^{m+1}_{m+1}+C^{m+1}_m+C^{m+2}_m+\dots+C^n_m\\
~ & =C^{m+2}_{m+1}+C^{m+2}_m+\dots+C^n_m\\
~ & =C^{m+3}_{m+1}+\dots+C^n_m=C^{n+1}_{m+1}
\end{align}</math>
{{Robox/Close}}

===在方冪和上的應用===
把多項式轉化為組合數，再用朱世杰恒等式求和。<ref>{{cite journal|author=田达武|year=2009|title=朱世杰恒等式及其应用|journal=数学教学通讯|issue=36|url=http://www.cnki.com.cn/Article/CJFDTotal-SXUJ200936022.htm}}</ref>

{{ExampleRobox|title=例子：<math>\sum_{k=1}^n k^2</math>}}
<math>\sum_{k=1}^n k^2=\sum_{k=1}^n (k^2-k+k)</math><br/>
<math>=\sum_{k=1}^n (2C^k_2+C^k_1)=2C^{n+1}_3+C^{n+1}_2</math>
{{Robox/Close}}

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

{{Robox|theme=3|title=证明：<math>\sum_{k=1}^n p(k)=
\begin{pmatrix}C^n_1 & C^n_2 & \cdots & C^n_{m+1}\end{pmatrix}
\begin{pmatrix}
C^0_0 & 0 & \cdots & 0\\
-C^1_0 & C^1_1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
(-1)^mC^m_0 & (-1)^{m-1}C^m_1 & \cdots & C^m_m\\
\end{pmatrix}
\begin{pmatrix}p(1)\\p(2)\\\vdots\\p(m+1)\end{pmatrix}</math><ref>{{cite journal|author=陶家元|year=1999|title=高阶等差数列的前n项求和|journal=成都大学学报(自然科学版)|issue=1|url=http://www.cnki.com.cn/Article/CJFDTOTAL-CDDD199901006.htm}}</ref><ref>{{cite journal|author=黄婷 车茂林 彭杰 张莉|year=2011|title=自然数幂和通项公式证明的新方法|journal=内江师范学院学报|issue=8|url=http://www.cnki.com.cn/Article/CJFDTotal-NJSG201108006.htm}}</ref><ref>{{cite journal|author=黄嘉威|year=2016|title=方幂和及其推广和式|journal=数学学习与研究|issue=7|url=http://www.cnki.com.cn/Article/CJFDTOTAL-SXYG201607113.htm}}</ref><br/>
<math>m=\deg(p)</math>}}

<math>p(k)</math>為m階多項式，待定成組合數：

<math>p(k)=\begin{pmatrix}C^{k-1}_0 & C^{k-1}_1 & \cdots & C^{k-1}_m\end{pmatrix}
\begin{pmatrix}a_1\\a_2\\ \vdots\\ a_{m+1}\end{pmatrix}</math>

代入<math>k=1,2,\dots,m+1</math>，得到：

<math>\begin{pmatrix}p(1)\\p(2)\\\vdots\\p(m+1)\end{pmatrix}=
\begin{pmatrix}
C^0_0 & 0 & \cdots & 0\\
C^1_0 & C^1_1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
C^m_0 & C^m_1 & \cdots & C^m_m\\
\end{pmatrix}
\begin{pmatrix}a_1\\a_2\\ \vdots\\ a_{m+1}\end{pmatrix}
</math>

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

<math>\begin{pmatrix}a_1\\a_2\\ \vdots\\ a_{m+1}\end{pmatrix}=
\begin{pmatrix}
C^0_0 & 0 & \cdots & 0\\
-C^1_0 & C^1_1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
(-1)^mC^m_0 & (-1)^{m-1}C^m_1 & \cdots & C^m_m\\
\end{pmatrix}
\begin{pmatrix}p(1)\\p(2)\\\vdots\\p(m+1)\end{pmatrix}
</math>

<math>p(k)=
\begin{pmatrix}C^{k-1}_0 & C^{k-1}_1 & \cdots & C^{k-1}_m\end{pmatrix}
\begin{pmatrix}
C^0_0 & 0 & \cdots & 0\\
-C^1_0 & C^1_1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
(-1)^mC^m_0 & (-1)^{m-1}C^m_1 & \cdots & C^m_m\\
\end{pmatrix}
\begin{pmatrix}p(1)\\p(2)\\\vdots\\p(m+1)\end{pmatrix}</math><br/>
<math>\sum_{k=1}^n p(k)=
\begin{pmatrix}C^n_1 & C^n_2 & \cdots & C^n_{m+1}\end{pmatrix}
\begin{pmatrix}
C^0_0 & 0 & \cdots & 0\\
-C^1_0 & C^1_1 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots\\
(-1)^mC^m_0 & (-1)^{m-1}C^m_1 & \cdots & C^m_m\\
\end{pmatrix}
\begin{pmatrix}p(1)\\p(2)\\\vdots\\p(m+1)\end{pmatrix}</math>

乘出來的結果也剛好是多項式各階差分在點1的值。
{{Robox/Close}}
{{Robox|theme=3|title=证明：<math>\sum_{k=1}^n p(k)=\sum_{j=1}^{m+1} C^{n}_{j}\Delta^{j-1}p(1)</math><ref>{{cite book|author=Károly Jordán|year=1950|title=Calculus of Finite Differences|url=http://crypto.cs.mcgill.ca/~simonpie/webdav/ipad/EBook/Math%C3%A9matique/Calculus/Math%20-%20Calculus%20of%20Finite%20Differences.pdf}}</ref><br/><math>m=\deg(p),\Delta p(n)=p(n+1)-p(n)</math>}}
設<math>p(k)=\sum_{j=0}^{m} a_j C^{k-1}_{j}=a_0+a_1 C^{k-1}_{1}+a_2 C^{k-1}_{2}+\dots+a_m C^{k-1}_{m}</math>

<math>p(1)=a_0</math>

<math>\Delta C^k_l=C^{k+1}_l-C^k_l=C^k_{l-1}</math>

<math>\Delta^j p(k)=a_j+a_{j+1} C^{k-1}_{1}+a_{j+2} C^{k-1}_{2}+\dots+a_m C^{k-1}_{m-j}</math>

<math>\Delta^j p(1)=a_j</math>

<math>p(k)=\sum_{j=0}^{m} C^{k-1}_{j}\Delta^j p(1)</math>

<math>\sum_{k=1}^n p(k)=\sum_{j=0}^{m} C^{n}_{j+1}\Delta^j p(1)=\sum_{j=1}^{m+1} C^{n}_{j}\Delta^{j-1}p(1)</math>

{{Robox/Close}}
{{Example|
<math> \sum_{i=1}^{n} i^{1} = \begin{pmatrix} C^n_1 & C^n_2 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 2 \end{pmatrix}= C^n_1+C^n_2 </math>
:<math> p(k)=k,\Delta p(k)=1</math>
:<math> p(1)=1,\Delta p(1)=1,\sum_{k=1}^{n} k =C^n_1+C^n_2</math>

<math> \sum_{i=1}^{n} [a+d(i-1)] = \begin{pmatrix} C^n_1 & C^n_2 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix} \begin{pmatrix} a \\ a+d \end{pmatrix}= aC^n_1+dC^n_2 </math>（等差數列求和）
:<math> p(k)=a+d(k-1),\Delta p(k)=d</math>
:<math> p(1)=a,\Delta p(1)=d,\sum_{k=1}^{n} [a+d(k-1)] =aC^n_1+dC^n_2</math>
  
<math> \sum_{i=1}^{n} i^{2} = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 \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^n_1+3C^n_2+2C^n_3 </math>
:<math> p(k)=k^2,\Delta p(k)=2k+1,\Delta^2 p(k)=2</math> 
:<math> p(1)=1,\Delta p(1)=3,\Delta^2 p(1)=2,\sum_{k=1}^{n} k^2 =C^n_1+3C^n_2+2C^n_3</math> 

<math> \sum_{i=1}^{n} i^{3} = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 & C^n_4 \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^n_1+7C^n_2+12C^n_3+6C^n_4 </math>
:<math> 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^n_1+7C^n_2+12C^n_3+6C^n_4</math>

<math> \sum_{i=1}^{n} i^{4} = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 & C^n_4 & C^n_5 \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^n_1+15C^n_2+50C^n_3+60C^n_4+24C^n_5 </math>

<math> \sum_{i=1}^{n} i^{5} = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 & C^n_4 & C^n_5 & C^n_6 \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^n_1+31C^n_2+180C^n_3+390C^n_4+360C^n_5+120C^n_6 </math>

<math> \sum_{i=1}^{n} (2i-1)^{2} = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 \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^n_1+8C^n_2+8C^n_3 </math>

<math> \sum_{i=1}^{n} (3i-2)^{3} = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 & C^n_4 \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^n_1+63C^n_2+216C^n_3+162C^n_4 </math>

<math> \sum_{i=1}^{n} \left(i^3+2i+1\right) = \begin{pmatrix} C^n_1 & C^n_2 & C^n_3 & C^n_4 \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^n_1+9C^n_2+12C^n_3+6C^n_4 </math>}}

==范德蒙恒等式==
{{quote|<math>\sum_{k=0}^n C^a_k C^b_{n-k}=C^{a+b}_n</math>}}

{{Robox|theme=3|title=证明范德蒙恒等式}}
甲班有a個同學，乙班有b個同學，從兩個班中選出n名有<math>C^{a+b}_n</math>種方法。<br/>
從甲班選k名，從乙班選n-k名有<math>C^a_k C^b_{n-k}</math>種方法，考慮所有情況k=0,1,...,n，從兩個班中選出n名有<math>\sum_{k=0}^n C^a_k C^b_{n-k}</math>種方法。<ref>{{cite journal|author=李松槐 杨伏香|year=1999|title=用数学模型证明范得蒙(Vandermonde)恒等式|journal=河南教育学院学报(自然科学版)|issue=2|url=http://www.cnki.com.cn/Article/CJFDTOTAL-HLKB199902007.htm}}</ref>
{{Robox/Close}}

==參考資料==
{{reflist}}