文章目錄

• 一、使用生成函數(shù)求解不定方程解個(gè)數(shù)示例

參考博客 :

• 【組合數(shù)學(xué)】生成函數(shù) 簡(jiǎn)要介紹 ( 生成函數(shù)定義 | 牛頓二項(xiàng)式系數(shù) | 常用的生成函數(shù) | 與常數(shù)相關(guān) | 與二項(xiàng)式系數(shù)相關(guān) | 與多項(xiàng)式系數(shù)相關(guān) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 線性性質(zhì) | 乘積性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 移位性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 求和性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 換元性質(zhì) | 求導(dǎo)性質(zhì) | 積分性質(zhì) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 性質(zhì)總結(jié) | 重要的生成函數(shù) ) ★
• 【組合數(shù)學(xué)】生成函數(shù) ( 生成函數(shù)示例 | 給定通項(xiàng)公式求生成函數(shù) | 給定生成函數(shù)求通項(xiàng)公式 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 生成函數(shù)應(yīng)用場(chǎng)景 | 使用生成函數(shù)求解遞推方程 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解多重集 r 組合數(shù) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù) )

一、使用生成函數(shù)求解不定方程解個(gè)數(shù)示例

---

$1$ 克砝碼 $2$ 個(gè) ,
$2$ 克砝碼 $1$ 個(gè) ,
$4$ 克砝碼 $2$ 個(gè) ,
可以稱出哪些重量 , 有多少方案?jìng)€(gè)數(shù) ;

$1$ 克的砝碼 個(gè)數(shù)是 $x_1$ 個(gè) , 取值范圍是 $0\le x_1\le 2$ , 可取值 $0,1,2$

$2$ 克的砝碼個(gè)數(shù)是 $x_2$ 個(gè) , 取值范圍是 $0\le x_2\le 1$ , 可取值 $0,1$

$4$ 克的砝碼個(gè)數(shù)是 $x_3$ 個(gè) , 取值范圍是 $0\le x_3\le 2$ , 可取值 $0,1,2$

$x_1+2x_2+4x_3=r$ , 其中 $r$ 代表可以稱出的重量 ,

寫(xiě)出上述 , 帶限制條件 , 并且?guī)禂?shù) 的不定方程非負(fù)整數(shù)解的 生成函數(shù) :

$x_1$ 項(xiàng) , 帶限制條件 , 沒(méi)有系數(shù) , 其 底是 $y$ , 冪取值 $0,1,2$ , 對(duì)應(yīng)的生成函數(shù)項(xiàng)是 $(1+y+y^2)$

$x_2$ 項(xiàng) , 帶限制條件 , 帶系數(shù) $2$ , 其 底是 $y^2$ , 冪取值 $0,1$ , 對(duì)應(yīng)生成函數(shù)項(xiàng)是 $(y^2{)}^0+(y^2{)}^1=1+y^2$

$x_3$ 項(xiàng) , 帶限制條件 , 帶系數(shù) $4$ , 其 底是 $y^4$ , 冪取值 $0,1,2$ , 對(duì)應(yīng)生成函數(shù)項(xiàng)是 $(y^4{)}^0+(y^4{)}^1+(y^4{)}^2=1+y^4+y^8$

將上述三項(xiàng)乘起來(lái) , 并展開(kāi) :

$G(x)=(1+y+y^2)(1+y^2)(1+y^4+y^8)$

$=1+y+2y^2+y^3+2y^4+y^5+2y^6+y^7+2y^8+y^9+2y^{10}+y^{11}+y^{12}$

上述展開(kāi)后的 $y$ 的次冪數(shù)是重量 , 系數(shù)是 方案?jìng)€(gè)數(shù) , 如 $2y^8$ 項(xiàng)表示 , 稱出 $8$ 克重量 , 有 $2$ 個(gè)方案 ;

總體描述 :

• $1$ 項(xiàng) : 表示 $y^0$ , 稱出 $0$ 克 , 有 $0$ 種方案 ;
• $y$ 項(xiàng) : 表示 $y^1$ , 稱出 $1$ 克 , 有 $1$ 種方案 ;
• $2y^2$ 項(xiàng) : 表示 $2y^2$ , 稱出 $2$ 克 , 有 $2$ 種方案 ;
• $y^3$ 項(xiàng) : 表示 $y^3$ , 稱出 $3$ 克 , 有 $1$ 種方案 ;
• $2y^4$ 項(xiàng) : 表示 $2y^4$ , 稱出 $4$ 克 , 有 $2$ 種方案 ;
• $y^5$ 項(xiàng) : 表示 $y^5$ , 稱出 $5$ 克 , 有 $1$ 種方案 ;
• $2y^6$ 項(xiàng) : 表示 $2y^6$ , 稱出 $6$ 克 , 有 $2$ 種方案 ;
• $y^7$ 項(xiàng) : 表示 $y^7$ , 稱出 $7$ 克 , 有 $1$ 種方案 ;
• $2y^8$ 項(xiàng) : 表示 $2y^8$ , 稱出 $8$ 克 , 有 $2$ 種方案 ;
• $y^9$ 項(xiàng) : 表示 $y^9$ , 稱出 $9$ 克 , 有 $1$ 種方案 ;
• $2y^{10}$ 項(xiàng) : 表示 $2y^{10}$ , 稱出 $10$ 克 , 有 $2$ 種方案 ;
• $y^{11}$ 項(xiàng) : 表示 $y^{11}$ , 稱出 $11$ 克 , 有 $1$ 種方案 ;
• $y^{12}$ 項(xiàng) : 表示 $y^{12}$ , 稱出 $12$ 克 , 有 $1$ 種方案 ;

總結(jié)

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

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