文章目錄

• 一、生成函數應用場景
• 二、使用生成函數求解遞推方程

參考博客 :

• 【組合數學】生成函數 簡要介紹 ( 生成函數定義 | 牛頓二項式系數 | 常用的生成函數 | 與常數相關 | 與二項式系數相關 | 與多項式系數相關 )
• 【組合數學】生成函數 ( 線性性質 | 乘積性質 )
• 【組合數學】生成函數 ( 移位性質 )
• 【組合數學】生成函數 ( 求和性質 )
• 【組合數學】生成函數 ( 換元性質 | 求導性質 | 積分性質 )
• 【組合數學】生成函數 ( 性質總結 | 重要的生成函數 ) ★
• 【組合數學】生成函數 ( 生成函數示例 | 給定通項公式求生成函數 | 給定生成函數求通項公式 )

一、生成函數應用場景

---

生成函數應用場景 :

• 求解遞推方程
• 多重集 $r$ 組合計數
• 不定方程解個數
• 整數拆分

多重集 $r$ 組合計數 , 之前 只能計數特殊情況下的組合數 , 也就是選取數 $r$ 小于多重集每一項的重復度 , 才有 組合數 $N=C(k+r?1,r)$ , 如果 $r$ 大于重復度 , 就需要使用生成函數進行求解 ;

不定方程的解個數 , 之前只能求解 沒有約束的情況 , 如果對變量有約束 , 如 $x_1$ 只能在某個區間取值 , 這種情況下 , 就必須使用生成函數進行求解 ;

整數拆分 , 將一個正數拆分多若干整數之和 , 拆分方案個數 , 也可以通過生成函數進行計算 ;

回顧多重集排列組合 :

• 可重復的元素 , 有序的選取 , 對應 多重集的排列 ; $全排列=\frac{n!}{n_1!n_2!?n_k!}$ , 非全排列 $k^r,r\le n_i$
• 可重復的元素 , 無序的選取 , 對應 多重集的組合 ; $N=C(k+r?1,r)$

二、使用生成函數求解遞推方程

---

遞推方程 : $a_n?5a_{n?1}+6a_{n?2}=0$

初值 : $a_0=1,a_1=2$

$\{a_n\}$ 數列為 $\{a_0,a_1,a_2,a_3,?,a_n,?\}$

$a_n$對應的生成函數是 $G(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+?$

根據遞推方程 , 同時為了使得后面的項可以約掉 , 使用 $?5x$ 乘以 $G(x)$ 生成函數 , 使用 $+6x^2$ 乘以 $G(x)$ , 得到如下三個式子 ,

$?5x$ 乘以 $G(x)$ 得到的第一項就是 $x$ 的一次方項 , 將該項對應到 $G(x)$ 中的 $x$ 一次方項下面 ,

$+6x^2$ 乘以 $G(x)$ 得到的第一項就是 $x$ 的二次方項 , 將該項對應到 $G(x)$ 中的 $x$ 二次方項下面 ;

$G(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+?$

$?5xG(x)=?5a_{0}x?5a_1{x}^2?5a_2{x}^3??$

$6x^{2}G(x)=+6a_0{x}^2+6a_x^3+?$

---

$(1?5x+6x^2)G(x)=a_0+(a_1?5a_0)x$

上述橫線下的式子是 橫線上面 三個式子相加的結果 ;

觀察上述右側 第三列 , 圖中紅框部分 ;

上述冪次對齊后 , 出現的等號右側的第三列 $+a_2{x}^2?5a_1{x}^2+6a_0{x}^2$ , 將其中 $x^2$ 提取出來得到 $(a_2?5a_1+6a_0)x^2$ , 正好對應遞推方程 $a_n?5a_{n?1}+6a_{n?2}=0$ ,

因此有 $a_2?5a_1+6a_0=0$ , 進而可以得到 $(a_2?5a_1+6a_0)x^2=0$

由此可以看出 , 如果三個式子全部相加 , 下圖 右側藍色矩形框內 , 全部都是 $0$ ;

目前右側只剩下 $a_0+a_{1}x?5a_{0}x$ 三項 ; 其中的 $a_0=1,a_1=?2$ 是初值 ;

最終等式右側是 : $1?2x?5x=1?7x$

將上述式子代入到 $(1?5x+6x^2)G(x)=a_0+(a_1?5a_0)x$ 中 , 使用 $1?2x?5x=1?7x$ 替換等式右側的式子 , 得到 :

$(1?5x+6x^2)G(x)=1?7x$

$G(x)=\frac{1?7x}{1?5x+6x^2}$

使用 給定 生成函數 , 求對應的級數 的 方法 , 將上述式子展開 , 參考 【組合數學】生成函數 ( 生成函數示例 | 給定通項公式求生成函數 | 給定生成函數求通項公式 ) 二、給定生成函數求級數 方法 ,

先將分母進行因式分解 , 然后設置兩個待定系數 , 通分后 , 根據 $x$ 項系數寫出方程組 , 最終解該方程組 , 最終可以得到 :

$G(x)=\frac{1?7x}{1?5x+6x^2}=\frac{5}{1?2x}?\frac{4}{1?3x}$

$\frac{5}{1?2x}$ 對應的級數是 : $\sum _{n=0}^{\infty }5(2x{)}^n=5\sum _{n=0}^{\infty }{2}^n{x}^n$

$\frac{4}{1?3x}$ 對應的級數是 : $\sum _{n=0}^{\infty }(?4)(3x{)}^n=?4\sum _{n=0}^{\infty }{3}^n{x}^n$

最終生成函數的級數形式為 : $G(x)=5\sum _{n=0}^{\infty }{2}^n{x}^n?4\sum _{n=0}^{\infty }{3}^n{x}^n$

遞推方程的通解 : $a_n=5?2^n?4?3^n$

基本思路 : 有原來的遞推方程 , 導出關于生成函數的遞推方程 ;

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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