利用組合數的性質可以構造出求和公式。
∑ k = 0 n C k n x n − k y k = ( x + y ) n {\displaystyle \sum _{k=0}^{n}C_{k}^{n}x^{n-k}y^{k}=(x+y)^{n}}
∑ k = 0 n C k n = 2 n {\displaystyle \sum _{k=0}^{n}C_{k}^{n}=2^{n}}
∑ k = m n C m k = C m + 1 n + 1 {\displaystyle \sum _{k=m}^{n}C_{m}^{k}=C_{m+1}^{n+1}}
∑ k = m n C m k = C m m + C m m + 1 + C m m + 2 + ⋯ + C m n = C m + 1 m + 1 + C m m + 1 + C m m + 2 + ⋯ + C m n = C m + 1 m + 2 + C m m + 2 + ⋯ + C m n = C m + 1 m + 3 + ⋯ + C m n = C m + 1 n + 1 {\displaystyle {\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}}}
把多項式轉化為組合數,再用朱世傑恆等式求和。[1]
∑ k = 1 n k 2 = ∑ k = 1 n ( k 2 − k + k ) {\displaystyle \sum _{k=1}^{n}k^{2}=\sum _{k=1}^{n}(k^{2}-k+k)} = ∑ k = 1 n ( 2 C 2 k + C 1 k ) = 2 C 3 n + 1 + C 2 n + 1 {\displaystyle =\sum _{k=1}^{n}(2C_{2}^{k}+C_{1}^{k})=2C_{3}^{n+1}+C_{2}^{n+1}}
將多項式轉化為組合數的過程一般化,對一個多項式求和有如下公式:
p ( k ) {\displaystyle p(k)} 為m階多項式,待定成組合數:
p ( k ) = ( C 0 k − 1 C 1 k − 1 ⋯ C m k − 1 ) ( a 1 a 2 ⋮ a m + 1 ) {\displaystyle 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 , … , m + 1 {\displaystyle k=1,2,\dots ,m+1} ,得到:
( p ( 1 ) p ( 2 ) ⋮ p ( m + 1 ) ) = ( C 0 0 0 ⋯ 0 C 0 1 C 1 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ C 0 m C 1 m ⋯ C m m ) ( a 1 a 2 ⋮ a m + 1 ) {\displaystyle {\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}}}
帕斯卡矩陣的逆等於自身交錯地加上負號,於是可直接求出待定系數:
( a 1 a 2 ⋮ a m + 1 ) = ( C 0 0 0 ⋯ 0 − C 0 1 C 1 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ( − 1 ) m C 0 m ( − 1 ) m − 1 C 1 m ⋯ C m m ) ( p ( 1 ) p ( 2 ) ⋮ p ( m + 1 ) ) {\displaystyle {\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 ) = ( C 0 k − 1 C 1 k − 1 ⋯ C m k − 1 ) ( C 0 0 0 ⋯ 0 − C 0 1 C 1 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ( − 1 ) m C 0 m ( − 1 ) m − 1 C 1 m ⋯ C m m ) ( p ( 1 ) p ( 2 ) ⋮ p ( m + 1 ) ) {\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}}} ∑ k = 1 n p ( k ) = ( C 1 n C 2 n ⋯ C m + 1 n ) ( C 0 0 0 ⋯ 0 − C 0 1 C 1 1 ⋯ 0 ⋮ ⋮ ⋱ ⋮ ( − 1 ) m C 0 m ( − 1 ) m − 1 C 1 m ⋯ C m m ) ( p ( 1 ) p ( 2 ) ⋮ p ( m + 1 ) ) {\displaystyle \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的值。
設 p ( k ) = ∑ j = 0 m a j C j k − 1 = a 0 + a 1 C 1 k − 1 + a 2 C 2 k − 1 + ⋯ + a m C m k − 1 {\displaystyle 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 {\displaystyle p(1)=a_{0}}
Δ C l k = C l k + 1 − C l k = C l − 1 k {\displaystyle \Delta C_{l}^{k}=C_{l}^{k+1}-C_{l}^{k}=C_{l-1}^{k}}
Δ j p ( k ) = a j + a j + 1 C 1 k − 1 + a j + 2 C 2 k − 1 + ⋯ + a m C m − j k − 1 {\displaystyle \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}}
Δ j p ( 1 ) = a j {\displaystyle \Delta ^{j}p(1)=a_{j}}
p ( k ) = ∑ j = 0 m C j k − 1 Δ j p ( 1 ) {\displaystyle p(k)=\sum _{j=0}^{m}C_{j}^{k-1}\Delta ^{j}p(1)}
∑ k = 1 n p ( k ) = ∑ j = 0 m C j + 1 n Δ j p ( 1 ) = ∑ j = 1 m + 1 C j n Δ j − 1 p ( 1 ) {\displaystyle \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)}
∑ i = 1 n i 1 = ( C 1 n C 2 n ) ( 1 0 − 1 1 ) ( 1 2 ) = C 1 n + C 2 n {\displaystyle \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}}
∑ i = 1 n [ a + d ( i − 1 ) ] = ( C 1 n C 2 n ) ( 1 0 − 1 1 ) ( a a + d ) = a C 1 n + d C 2 n {\displaystyle \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}} (等差數列求和)
∑ i = 1 n i 2 = ( C 1 n C 2 n C 3 n ) ( 1 0 0 − 1 1 0 1 − 2 1 ) ( 1 2 2 2 3 2 ) = C 1 n + 3 C 2 n + 2 C 3 n {\displaystyle \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}}
∑ i = 1 n i 3 = ( C 1 n C 2 n C 3 n C 4 n ) ( 1 0 0 0 − 1 1 0 0 1 − 2 1 0 − 1 3 − 3 1 ) ( 1 3 2 3 3 3 4 3 ) = C 1 n + 7 C 2 n + 12 C 3 n + 6 C 4 n {\displaystyle \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}}
∑ i = 1 n i 4 = ( C 1 n C 2 n C 3 n C 4 n C 5 n ) ( 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 ) ( 1 4 2 4 3 4 4 4 5 4 ) = C 1 n + 15 C 2 n + 50 C 3 n + 60 C 4 n + 24 C 5 n {\displaystyle \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}}
∑ i = 1 n i 5 = ( C 1 n C 2 n C 3 n C 4 n C 5 n C 6 n ) ( 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 ) ( 1 5 2 5 3 5 4 5 5 5 6 5 ) = C 1 n + 31 C 2 n + 180 C 3 n + 390 C 4 n + 360 C 5 n + 120 C 6 n {\displaystyle \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}}
∑ i = 1 n ( 2 i − 1 ) 2 = ( C 1 n C 2 n C 3 n ) ( 1 0 0 − 1 1 0 1 − 2 1 ) ( 1 2 3 2 5 2 ) = C 1 n + 8 C 2 n + 8 C 3 n {\displaystyle \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}}
∑ i = 1 n ( 3 i − 2 ) 3 = ( C 1 n C 2 n C 3 n C 4 n ) ( 1 0 0 0 − 1 1 0 0 1 − 2 1 0 − 1 3 − 3 1 ) ( 1 3 4 3 7 3 10 3 ) = C 1 n + 63 C 2 n + 216 C 3 n + 162 C 4 n {\displaystyle \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}}
∑ i = 1 n ( i 3 + 2 i + 1 ) = ( C 1 n C 2 n C 3 n C 4 n ) ( 1 0 0 0 − 1 1 0 0 1 − 2 1 0 − 1 3 − 3 1 ) ( 4 13 34 73 ) = 4 C 1 n + 9 C 2 n + 12 C 3 n + 6 C 4 n {\displaystyle \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}}
∑ k = 0 n C k a C n − k b = C n a + b {\displaystyle \sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}=C_{n}^{a+b}}
甲班有a個同學,乙班有b個同學,從兩個班中選出n名有 C n a + b {\displaystyle C_{n}^{a+b}} 種方法。 從甲班選k名,從乙班選n-k名有 C k a C n − k b {\displaystyle C_{k}^{a}C_{n-k}^{b}} 種方法,考慮所有情況k=0,1,...,n,從兩個班中選出n名有 ∑ k = 0 n C k a C n − k b {\displaystyle \sum _{k=0}^{n}C_{k}^{a}C_{n-k}^{b}} 種方法。[6]