文章目錄

• 一、組合恒等式 ( 變上項求和 1 )
• 二、組合恒等式證明方法 ( 三種 )
• 三、組合恒等式 ( 變上項求和 1 ) 證明

組合恒等式參考博客 :

• 【組合數學】組合恒等式 ( 遞推 組合恒等式 | 變下項求和 組合恒等式 簡單和 | 變下項求和 組合恒等式 交錯和 )
• 【組合數學】組合恒等式 ( 變下項求和 3 組合恒等式 | 變下項求和 4 組合恒等式 | 二項式定理 + 求導 證明組合恒等式 | 使用已知組合恒等式證明組合恒等式 )

回顧四個變下項求和的組合恒等式 : 之前介紹的組合恒等式 中的組合數 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ , 是下項 $k$ 一直在累加改變 , 具有 $\sum _{k=0}^n$ 累加性質 , 上項 $n$ 是不變的 ;

( 1 ) 簡單和 : $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$

( 2 ) 交錯和 : $\sum _{k=0}^n(?1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0$

( 3 ) 變下項求和 3 : $\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n{2}^{n?1}$

( 4 ) 變下項求和 4 : ${\sum }_{k=0}^n{k}^2\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n(n+1)2^{n?2}$

一、組合恒等式 ( 變上項求和 1 )

---

變上項求和 1 :

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

上述公式中 , 組合數 $\left(\genfrac{}{}{0ex}{}{l}{k}\right)$ 中 , 下項 $k$ 是不變的 , 上項 $l$ 一直是改變的 , 其取值范圍是 $0$ ~ $n$ ;

該表達式中有若干項都是 $0$ :

• 當 $l<k$ 時 , $\left(\genfrac{}{}{0ex}{}{l}{k}\right)=0$ , 從 $l$ 個元素中選取 $k$ 個元素 , 沒有方案 ;
• 當 $l=k$ 時 , $\left(\genfrac{}{}{0ex}{}{l}{k}\right)=1$ ;
• 當 $l>k$ 時 , $\left(\genfrac{}{}{0ex}{}{l}{k}\right)$ 才為大于 $1$ 的值 ;

二、組合恒等式證明方法 ( 三種 )

---

1 . 證明方法 : 之前使用過兩種證明方法 , ① 二項式定理 + 求導 , ② 使用現有組合恒等式推導 ;

在這里使用第三類證明方法 , ③ 組合分析 , 組合分析方法是要構造一個組合計數問題 , 左邊和右邊都是同一個計數問題的解 ;

2 . 組合分析方法使用 : 使用組合分析方法證明組合數時 , 先指定集合 , 指定元素 , 指定兩個計數問題 , 公式兩邊是對同一個問題的計數 ;

指定計數問題 : 下面兩個計數問題都是同一個問題的計數 ;

• ① 問題 1 : 等號左側代表的計數問題 ;
• ② 問題 2 : 等號右側代表的計數問題 ;

參考 : 【組合數學】二項式定理與組合恒等式 ( 二項式定理 | 三個組合恒等式 遞推式 | 遞推式 1 | 遞推式 2 | 遞推式 3 帕斯卡/楊輝三角公式 | 組合分析方法 | 遞推式組合恒等式特點 ) 五、組合分析方法

3 . 組合分析方法使用總結 : 使用組合分析方法證明組合數時 , 先指定集合 , 指定元素 , 指定兩個計數問題 , 公式兩邊是對同一個問題的計數 ;

三、組合恒等式 ( 變上項求和 1 ) 證明

---

現在開始構造選取問題 :

1 . 指定集合 : 假定有 $n+1$ 個元素的集合 , 記作 $S=\{a_1,a_2,?,a_{n+1}\}$ ,

2 . 指定等號右側的計數問題 : 從上述集合 $S$ 中 , 選取 $k+1$ 個元素的子集 , 選擇方法的個數是 $\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ 個 ;

3 . 指定等號左側的計數問題 : 等號左側是 $\sum _{l=0}^n\left(\genfrac{}{}{0ex}{}{l}{k}\right)$ ;

計數問題類型確定 ( 分類選取 ) : 組合式中存在 和號 $\sum$ , 說明該計數問題采用了 分類計數原理 , 對應加法法則 ; 該計數問題肯定是分類選取 ;

$S$ 集合 , 從 $n+1$ 個元素中選取 $k+1$ 個元素 ;

( 1 ) 第 $1$ 類 , 指定某個特定元素 $a_1$ , 在子集中必須含有 $a_1$ , 則只能從剩余的 $n$ 個元素中選取 $k$ 個 , 方案數是 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ;

( 2 ) 第 $2$ 類 , 與 第 $1$ 類不重疊 ,
不含 $a_1$ , 但是必須含有 $a_2$ ,
不含 $a_1$ 那就要從 $n$ 個元素中選取 ( 從 $n+1$ 個元素中去掉一個 ) ,
必須含有 $a_2$ ( 從 $n$ 個元素中再去掉一個, 即 $n?1$ 個 ) , 那么就要從 $n?1$ 個元素中選取 $k$ 個元素 ,
最終結果是 $\left(\genfrac{}{}{0ex}{}{n?1}{k}\right)$

( 3 ) 第 $3$ 類 , 與 第 $1,2$ 類不重疊 ,
不含 $a_1,a_2$ , 但是必須含有 $a_3$ ,
不含 $a_1,a_2$ 那就要從 $n?1$ 個元素中選取 ( 從 $n+1$ 個元素中去掉 $2$ 個 , 即 $n?1$ ) ,
必須含有 $a_3$ ( 從 $n?1$ 個元素中再去掉一個, 即 $n?2$ 個 ) , 那么就要從 $n?2$ 個元素中選取 $k$ 個元素 ,
最終結果是 $\left(\genfrac{}{}{0ex}{}{n?2}{k}\right)$

$$?$$

( 4 ) 第 $n+1$ 類 , 與 第 $1,2,?,n$ 類不重疊 ,
不含 $a_1,a_2,a_3,?,a_n$ , 但是必須含有 $a_{n+1}$ ,
不含 $a_1,a_2,a_3,?,a_n$ 那就要從 $1$ 個元素中選取 ( 從 $n+1$ 個元素中去掉 $n$ 個 , 即 $1$ ) ,
必須含有 $a_{n+1}$ ( 從 $1$ 個元素中再去掉一個, 即 $0$ 個 ) , 那么就要從 $0$ 個元素中選取 $k$ 個元素 ,
最終結果是 $\left(\genfrac{}{}{0ex}{}{0}{k}\right)$

5 . 在上述兩個計數問題都是同一個計數問題 , 都是從 $n+1$ 個元素中選取 $k+1$ 個元素 ;

總結

以上是生活随笔為你收集整理的【组合数学】组合恒等式 ( 变上项求和 1 组合恒等式 | 三种组合恒等式证明方法总结 | 证明变上项求和 1 组合恒等式 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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