當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )

發布時間：2025/6/17 编程问答 19 豆豆

生活随笔收集整理的這篇文章主要介紹了【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 ) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

一、組合恒等式 ( 變下項求和 ) 變系數求和 1
二、組合恒等式 ( 變下項求和 ) 變系數求和 1 證明 ( 二項式定理 + 求導 )
三、組合恒等式 ( 變下項求和 ) 變系數求和 2
四、組合恒等式 ( 變下項求和 ) 變系數求和 2 證明 ( 使用已知恒等式證明 )

一、組合恒等式 ( 變下項求和 ) 變系數求和 1

組合恒等式 ( 變下項求和 ) 變系數求和 :

$∑k=0nk(nk)=n2n?1\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}$

$k$ 隨著求和的項不斷變化 , 變化范圍 $0$ ~ $n$ ;

1. 證明方法 :

二項式定理 : 使用二項式定理 + 求導可以證明該組合恒等式 ;
組合恒等式代入 : 使用已知組合恒等式代入 , 消去變系數 ; 即使用之前的 $3$ 個遞推式 , 簡單和 , 交錯和 , $5$ 個組合恒等式代入 ;

二、組合恒等式 ( 變下項求和 ) 變系數求和 1 證明 ( 二項式定理 + 求導 )

使用二項式定理 + 求導方法證明下面的恒等式 :

$∑k=0nk(nk)=n2n?1\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}$

二項式定理 : $y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k}$

1. $y = 1$ 時有該情況 : $+1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k$ , 上述公式中 , 將常數項 $k = 0$ 的情況單獨計算出來 , $(n0)x0=1\dbinom{n}{0}x^0 = 1$ , 計算過程如下 :

$+1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k = \dbinom{n}{0}x^0 + \sum\limits_{k=1}^n \dbinom{n}{k}x^k = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k$

2. 引入求導 : 要在加和式 $∑k=1n(nk)xk\sum\limits_{k=1}^n \dbinom{n}{k}x^k$ 中出現 $k$ 變化數 , 需要對 $x$ 進行求導 ;

這里直接對 $+1)^n = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k$ 等式兩邊進行求導 ;

( 1 ) 左邊組合式 ( 根據下面的冪函數導數公式計算 ) : $x +1)^n$ 導數為 $n(x+1)^{n-1}$

( 2 ) 右邊組合式 ( 根據下面的導數運算規則和冪函數導數公式計算 ) : $\sum\limits_{k=1}^n \dbinom{n}{k}x^k$ 導數為 , $1$ 的導數為 $0$ , 加上 $∑k=1n(nk)xk\sum\limits_{k=1}^n \dbinom{n}{k}x^k$ 的導數 $∑k=1nk(nk)xk?1\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}$ , 最終結果是 $∑k=1nk(nk)xk?1\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}$

( 3 ) 左右兩邊的導數是相等的 :

$n(x+1)n?1=∑k=1nk(nk)xk?1n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}$

冪函數求導 : ( 很重要 )

原函數 : $y = x^n$
對應導數 : $y' = nx^{n-1}$ \

/
常數的導數是 $0$ ;
/
導數四則運算 : $\pm v)' = u' \pm v'$
/
參考 : 導數 - 百度百科

3. 求導后的結果如下 :

$n(x+1)n?1=∑k=1nk(nk)xk?1n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}$

假設求導結果中的 $x = 1$ , 有如下結果 :

$n2n?1=∑k=1nk(nk)n2^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}$

當 $k = 0$ 時 , 有 $\dbinom{n}{k} = 0 \times \dbinom{n}{0} = 0$ ,

因此加上 $k = 0$ 的情況 , 即 $k$ 從 $0$ 開始累加 , 也不影響上述結果 :

$n2n?1=∑k=0nk(nk)n2^{n-1} = \sum\limits_{k=0}^n k \dbinom{n}{k}$

三、組合恒等式 ( 變下項求和 ) 變系數求和 2

組合恒等式 ( 變下項求和 ) 變系數求和 :

$∑k=0nk2(nk)=n(n+1)2n?2\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}$

$k$ 隨著求和的項不斷變化 , 變化范圍 $0$ ~ $n$ ;

證明方法 :

二項式定理 : 使用二項式定理 + 求導可以證明該組合恒等式 ;
組合恒等式代入 : 使用已知組合恒等式代入 , 消去變系數 ; 即使用之前的 $3$ 個遞推式 , 簡單和 , 交錯和 , $5$ 個組合恒等式代入 ;

四、組合恒等式 ( 變下項求和 ) 變系數求和 2 證明 ( 使用已知恒等式證明 )

使用已知恒等式證明下面的恒等式 :

$∑k=0nk2(nk)=n(n+1)2n?2\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}$

1. 已知恒等式列舉 :

① 遞推式 $1$ : $(nk)=(nn?k)\dbinom{n}{k} = \dbinom{n}{n-k}$
② 遞推式 $2$ : $(nk)=nk(n?1k?1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}$
③ 遞推式 $3$ 帕斯卡 / 楊輝三角公式 : $(nk)=(n?1k)+(n?1k?1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$
④ 變下項求和 1 簡單和 : $∑k=0n(nk)=2n\sum_{k=0}^{n}\dbinom{n}{k} = 2^n$
⑤ 變下項求和 2 交錯和 : $∑k=0n(?1)k(nk)=0\sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0$

2. 變下限 : 從 $∑k=0nk2(nk)\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k}$ 開始推導 , $k = 0$ 時 , $k2(nk)=0k^2 \dbinom{n}{k} = 0$ , 可以忽略 , 這里可以從 $1$ 開始累加 ;

$∑k=0nk2(nk)=∑k=1nk2(nk)\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = \sum\limits_{k=1}^{n} k^2 \dbinom{n}{k}$

使用 $(nk)=nk(n?1k?1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}$ 恒等式替換其中的 $(nk)\dbinom{n}{k}$ :

$\sum\limits_{k=1}^{n} k^2 \dfrac{n}{k} \dbinom{n - 1}{k - 1}$

3. 消去變系數 : 消去一個 $k$ 后 , 變成如下公式 :

$=∑k=1nkn(n?1k?1)=\sum\limits_{k=1}^{n} k n \dbinom{n - 1}{k - 1}$

4. 常量外提 : 其中的 $n$ 相對于求和來說 , 是一個常量 , 可以提到求和符號之外 :

$=n∑k=1nk(n?1k?1)=n\sum\limits_{k=1}^{n} k \dbinom{n - 1}{k - 1}$

5. 變形及拆解 : 在組合數中有 $(n?1k?1)\dbinom{n - 1}{k - 1}$ , 為了與 $k ? 1$ 進行匹配 , 這里將 $k$ 進行變形 , $k = (k ? 1) + 1$ , 可以湊出一個 $k ? 1$ 來 ;

$=n∑k=1n[(k?1)+1](n?1k?1)=n\sum\limits_{k=1}^{n} [( k - 1 ) +1] \dbinom{n - 1}{k - 1}$

利用求和公式 , 將上述式子拆解成兩個和式 ,

$=n∑k=1n(k?1)(n?1k?1)+n∑k=1n(n?1k?1)=n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}$

6. 第一個組合式轉換 : $n∑k=1n(k?1)(n?1k?1)n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1}$ 求和 ,

$k = 1$ 時 , 組合數的下項 , 加和式中的系數 $k ? 1 = 0$ , 將 $k$ 作下限的變換 , $k$ 取值是 $1$ ~ $n$ , 則 $k ? 1$ 取值是 $0$ ~ $(n ? 1)$ ,

相當于使用 $k^{'} = k ? 1$ 替代之前的 $k$ , $k^{'}$ 取值范圍 $0$ ~ $(n ? 1)$ ,

因此最終可以變為 $n∑k′=0n?1(k′)(n?1k′)n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}$

使用 $∑k=0nk(nk)=n2n?1\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}$ 組合恒等式 ,

上述 $∑k′=0n?1(k′)(n?1k′)\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}$ 的結果是 $n-1)2^{n-2}$ ,

前面乘以 $n$ , 最終的 $n∑k′=0n?1(k′)(n?1k′)=n(n?1)2n?2n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} = n(n-1)2^{n-2}$

7. 第二個組合式轉換 : $n∑k=1n(n?1k?1)n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}$ 該組合式中 $k$ 取值是 $1$ ~ $n$ , 將 $k$ 變為從 $0$ 開始 , 即使用 $k^{'} = k ? 1$ 替代 $k$ ,

則有 $n∑k′=0n?1(n?1k′)n\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'}$ , 該求和可以轉變成基本求和 ,

使用簡單和組合恒等式 $∑k=0n(nk)=2n\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n$ ,

$∑k′=0n?1(n?1k′)\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'}$ 就是 $2^{n-1}$ , 前面乘以 $n$ , $n∑k=1n(n?1k?1)n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}$ 就是 $n2^{n-1}$

$=n∑k=1n(k?1)(n?1k?1)+n∑k=1n(n?1k?1)=n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}$

$n(n-1)2^{n-2} + n2^{n-1}$

$=n(n?1)2n?2+n2×2n?2=n(n-1)2^{n-2} + n 2 \times2^{n-2}$

$n(n+1)2^{n-2}$

總結 :
先利用遞推式 , 消掉變系數 $k$ ,
將求和的每個式子湊成基本求和公式 , 或已知求和公式 ,
然后進行求和變限 , 即使用 $k^{'} = k ? 1$ 替換 $k$ ,
通過上述技巧 , 完成證明 ;

總結

以上是生活随笔為你收集整理的【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：【组合数学】组合恒等式 ( 递推组合恒
下一篇：【组合数学】组合恒等式 ( 变上项求和