文章目錄

• 一、使用生成函數求解不定方程解個數
• • 1、帶限制條件
  • 2、帶系數

參考博客 :

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

一、使用生成函數求解不定方程解個數

---

不定方程的解個數 :

$x_1+x_2+?+x_k=r$

$x_i$ 為自然數 ;

之前通過組合對應的方法 , 已經解決 , 其解個數是 $C(k+r?1,r)$

不定方程解的個數 , 推導過程參考 : 【組合數學】排列組合 ( 多重集組合數 | 所有元素重復度大于組合數 | 多重集組合數 推導 1 分割線推導 | 多重集組合數 推導 2 不定方程非負整數解個數推導 ) 二、多重集組合 所有元素重復度大于組合數 推導 2 ( 不定方程非負整數解個數推導 )

上述情況下 , $x_i$ 的取值都是沒有上限的 , 如果 $x_i$ 取值受限 , 如 $x_1$ 取值必須滿足 $2\le x_1\le 5$ 條件時 , 就不能使用上述公式進行計算 , 這里需要 使用到生成函數求解 ;

1、帶限制條件

$x_1+x_2+?+x_k=r$

如果 $x_i$ 取值受到約束 , $l_i\le x_i\le n_i$ , 則對應的 生成函數項的 $y$ 次冪值從 $l_i$ 到 $n_i$ ;

對應的生成函數項是 $y^{l_i}+y^{l_i+1}+?+y^{n_i}$

完整的生成函數是 :

$G(y)=(y^{l_1}+y^{l_1+1}+?+y^{n_1})(y^{l_2}+y^{l_2+1}+?+y^{n_2})?(y^{l_k}+y^{l_k+1}+?+y^{n_k})$

將上述生成函數結果乘出來 , $y^r$ 前的系數 , 就是不定方程 的解的個數 ;

2、帶系數

$p_1{x}_1+p_2{x}_2+?+p_k{x}_k=r$

$x_i\in N$ , 非負整數解 , 對 $x_i$ 不設置上限 ;

帶系數的函數非負整數解 , 生成函數的項的基本的 底是 $y^{p_i}$ , 冪的取值范圍是 $0,1,2,?$ ,

每個生成函數項是 $(y^{p_i}{)}^0+(y^{p_i}{)}^1+(y^{p_i}{)}^2+(y^{p_i}{)}^3+?$ ,

化簡后的項是 $1+y^{p_i}+y^{2p_i}+y^{3p_i}+?$

將所有的 $k$ 項相乘 , 就是對應的生成函數 :

$G(y)=(1+y^{p_1}+y^{2p_1}+y^{3p_1+?})(1+y^{p_2}+y^{2p_2}+y^{3p_2+?})?(1+y^{p_k}+y^{2p_k}+y^{3p_k+?})$

該方程的非負整數解個數是 $y^r$ 前的系數 ;

總結

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

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