文章目錄

• 一、使用生成函數(shù)求解多重集 r 組合數(shù)
• 二、使用生成函數(shù)求解多重集 r 組合數(shù) 示例

參考博客 :

• 【組合數(shù)學(xué)】生成函數(shù) 簡要介紹 ( 生成函數(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)用場景 | 使用生成函數(shù)求解遞推方程 )

一、使用生成函數(shù)求解多重集 r 組合數(shù)

---

$S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\}$ 是多重集 , 其含有 $k$ 個(gè)種類的元素 , $n_1,n_2,?,n_k$ 是每種元素的重復(fù)度 ,

該 多重集的 $r$ 組合數(shù) , 是 不定方程 $x_1+x_2+?+x_k=r$ 的非負(fù)整數(shù)解 , 前提是 $x_i\le n_i$ , 每個(gè)元素所取的個(gè)數(shù) $x_i$ , 不能超過其重復(fù)度 $n_i$ ;

相當(dāng)于 $a_1$ 取 $x_1$ 個(gè) , $a_2$ 取 $x_2$ 個(gè) , $?$ , $a_k$ 取 $x_k$ 個(gè) , 總共取 $r$ 個(gè) ;

$n_i$ 是無窮個(gè)數(shù)時(shí) , 多重集的 $r$ 組合數(shù)是 $C(k+r?1,r)$

回顧多重集排列組合 :

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

上述的 多重集 $r$ 組合數(shù) $C(k+r?1,r)$ 是在重復(fù)度不受限制的情況下的選取結(jié)果 , 如果重復(fù)度受限制 , 就需要使用生成函數(shù)進(jìn)行計(jì)算 ;

如添加如下限制 : $a_1$ 最多能取 $3$ 個(gè) , $a_2$ 最少取 $4$ 個(gè) , 最多取 $10$ 個(gè) ;

生成函數(shù) :

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

多重集中的每個(gè)元素的取值個(gè)數(shù)作為 $y$ 的次冪 , 如 $a_1$ 元素的取值個(gè)數(shù)是 $0$ 到 $n_1$ , 則該項(xiàng)對應(yīng)的 生成函數(shù)項(xiàng)是 從 $y$ 的 $0$ 次冪 , 到 $y$ 的 $n_1$ 次冪 相加 ; 構(gòu)成項(xiàng) $(1+y+?+y^{n_1})$ ;

將所有元素的上述 生成函數(shù)項(xiàng) 乘到一起 , 就構(gòu)成上述生成函數(shù) ;

按照多項(xiàng)式乘法 , 多重集中取 $r$ 個(gè)元素 ,

從第一個(gè)因式 $(1+y+?+y^{n_1})$ 拿出 $y^{x_1}$ ,

從第二個(gè)因式 $(1+y+?+y^{n_2})$ 拿出 $y^{x_2}$ ,

$?$

從第 $k$ 個(gè)因式 $(1+y+?+y^{n_k})$ 拿出 $y^{x_k}$ ,

如果上述乘積 $y^{x_1}{y}^{x_2}?y^{x_k}$ 的結(jié)果 是 $y^r$ , 即 $y^{x_1}{y}^{x_2}?y^{x_k}=y^r$ , 相當(dāng)于指數(shù) $x_1+x_2+?+x_k=r$ , 也就是不定方程的非負(fù)整數(shù)解 ;

二、使用生成函數(shù)求解多重集 r 組合數(shù) 示例

---

多重集 $S=\{3?a,4?b,5?c\}$ , 求該多重集的 $10$ 組合數(shù) ;

上述多重集元素的 重復(fù)度 $3,4,5$ 都不超過 $10$ ;

對應(yīng) $a$ 元素 , 其 重復(fù)度取值范圍是 $0$ ~ $3$ , 對應(yīng)的生成函數(shù)項(xiàng)是 $y^0+y^1+y^2+y^3$

對應(yīng) $b$ 元素 , 其 重復(fù)度取值范圍是 $0$ ~ $4$ , 對應(yīng)的生成函數(shù)項(xiàng)是 $y^0+y^1+y^2+y^3+y^4$

對應(yīng) $c$ 元素 , 其重 復(fù)度取值范圍是 $0$ ~ $5$ , 對應(yīng)的生成函數(shù)項(xiàng)是 $y^0+y^1+y^2+y^3+y^4+y^5$

將上述項(xiàng)相乘 , 得到完整的生成函數(shù) ;

$G(x)=(y^0+y^1+y^2+y^3)(y^0+y^1+y^2+y^3+y^4)(y^0+y^1+y^2+y^3+y^4+y^5)$

$=(1+y^1+y^2+y^3)(1+y^1+y^2+y^3+y^4)(1+y^1+y^2+y^3+y^4+y^5)$

$=(1+2y^1+3y^2+4y^3+4y^4+3y^5+2y^6+y^7)(1+y^1+y^2+y^3+y^4+y^5)$

統(tǒng)計(jì)上述兩項(xiàng)相乘 , $y$ 的次冪值為 $10$ 的項(xiàng) :

第一個(gè)因式的 $3y^5$ 與第二個(gè)因式的 $y^5$ , 相乘為 $3y^{10}$

第一個(gè)因式的 $2y^6$ 與第二個(gè)因式的 $y^4$ , 相乘為 $2y^{10}$

第一個(gè)因式的 $y^7$ 與第二個(gè)因式的 $y^3$ , 相乘為 $y^{10}$

$y^{10}$ 項(xiàng)前的系數(shù)是 $3+2+1=6$

因此上述 多重集的 $10$ 組合 ,選擇方案有 $6$ 種 ;

總結(jié)

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

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