文章目錄

• 一、組合恒等式 ( 遞推式 )
• 二、組合恒等式 ( 變下項(xiàng)求和 ) 簡(jiǎn)單和
• 二、組合恒等式 ( 變下項(xiàng)求和 ) 交錯(cuò)和

一、組合恒等式 ( 遞推式 )

---

組合恒等式 ( 遞推式 ) :

1 . $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n?k}\right)$ , 作用 : 化簡(jiǎn)

2 . $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n}{k}\left(\genfrac{}{}{0ex}{}{n?1}{k?1}\right)$ , 作用 : 求和時(shí)消去變系數(shù) ;

3 . $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n?1}{k}\right)+\left(\genfrac{}{}{0ex}{}{n?1}{k?1}\right)$ , 作用 : 求和時(shí)拆項(xiàng) , 將一個(gè)組合數(shù)拆分成兩項(xiàng)之和 , 或兩項(xiàng)之差 , 然后合并 ;

二、組合恒等式 ( 變下項(xiàng)求和 ) 簡(jiǎn)單和

---

簡(jiǎn)單和 :

$$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$$

1. 證明 ( 二項(xiàng)式定理 ) : 通過二項(xiàng)式定理可以證明 , $(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n?k}$ 中 , 使 $x=y=1$ , 即可得到上面的 簡(jiǎn)單和 組合恒等式 ;

2. 證明 ( 組合分析 ) : 將等號(hào) 左邊 和 右邊 各看做某個(gè) 組合計(jì)數(shù)問題的解 ,

( 1 ) 左側(cè) 組合計(jì)數(shù)問題 : $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 可以看做 $n$ 個(gè)元素的所有子集個(gè)數(shù) ; ( 這也是集合中的冪集個(gè)數(shù) ) ;

這是分類計(jì)數(shù) , 最后將所有的類個(gè)數(shù)相加 , 即包含 $0$ 個(gè)元素個(gè)數(shù) , 包含 $1$ 個(gè)元素子集個(gè)數(shù) , $?$ , 包含 $n$ 個(gè)元素子集個(gè)數(shù) ;

( 2 ) 右側(cè) 組合計(jì)數(shù)問題 : $n$ 個(gè)元素中 , 每個(gè)元素都有 放入子集中 , 不放入子集中 , 兩種選擇 , 那么所有元素的選擇有 , $\begin{array}{c}2\times 2\times ?\times 2\\ n個(gè)\end{array}=2^n$ 個(gè)選擇 , 這是 分步計(jì)數(shù)的乘法法則 ,

這是分步計(jì)數(shù) , 最后將所有的分步結(jié)果相乘 , 即第 $1$ 個(gè)元素選擇個(gè)數(shù) , 第 $2$ 個(gè)元素選擇個(gè)數(shù) , $?$ , 第 $n$ 個(gè)元素選擇個(gè)數(shù) ;

3. 應(yīng)用場(chǎng)景 : 在序列求和場(chǎng)景使用 ;

二、組合恒等式 ( 變下項(xiàng)求和 ) 交錯(cuò)和

---

交錯(cuò)和 :

$$\sum _{k=0}^n(?1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0$$

1. 證明 ( 二項(xiàng)式定理 ) : 通過二項(xiàng)式定理可以證明 , $(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n?k}$ 中 , 使 $x=?1,y=1$ , 即可得到上面的 交錯(cuò)和 組合恒等式 ;

2. 證明 ( 組合分析 ) : 將等號(hào) 左邊 和 右邊 各看做某個(gè) 組合計(jì)數(shù)問題的解 , 完全展開上述組合數(shù) , 這里需要先移項(xiàng) , 將 $k$ 為奇數(shù)的情況下 , $(?1{)}^k$ 為 $?1$ , 將這種情況的分項(xiàng)移到右邊 , 就有了如下公式 :

$$\sum _{k=0}^{偶數(shù)}\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\sum _{k=1}^{奇數(shù)}\left(\genfrac{}{}{0ex}{}{n}{k}\right)$$

( 1 ) 左側(cè) 組合計(jì)數(shù)問題 : ${\sum }_{k=0}^{偶數(shù)}\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 可以看做 $n$ 個(gè)元素的所有 偶數(shù)個(gè) 子集個(gè)數(shù) ;

( 2 ) 右側(cè) 組合計(jì)數(shù)問題 : ${\sum }_{k=1}^{奇數(shù)}\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 可以看做 $n$ 個(gè)元素的所有 奇數(shù)個(gè) 子集個(gè)數(shù) ;

上述 奇數(shù)子集個(gè)數(shù) 與 偶數(shù)子集個(gè)數(shù) 是相等的 ;

3. 應(yīng)用場(chǎng)景 : 在序列求和場(chǎng)景使用 ;

總結(jié)

以上是生活随笔為你收集整理的【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。