文章目錄

• 一、證明指數(shù)生成函數(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ù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解多重集 r 組合數(shù) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù) )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù)示例 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 使用生成函數(shù)求解不定方程解個(gè)數(shù)示例 2 | 擴(kuò)展到整數(shù)解 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 正整數(shù)拆分 | 無序 | 有序 | 允許重復(fù) | 不允許重復(fù) | 無序不重復(fù)拆分 | 無序重復(fù)拆分 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 正整數(shù)拆分 | 無序不重復(fù)拆分示例 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 正整數(shù)拆分 | 正整數(shù)拆分基本模型 | 有限制條件的無序拆分 )
• 【組合數(shù)學(xué)】生成函數(shù) ( 正整數(shù)拆分 | 重復(fù)有序拆分 | 不重復(fù)有序拆分 | 重復(fù)有序拆分方案數(shù)證明 )
• 【組合數(shù)學(xué)】指數(shù)生成函數(shù) ( 指數(shù)生成函數(shù)概念 | 排列數(shù)指數(shù)生成函數(shù) = 組合數(shù)普通生成函數(shù) | 指數(shù)生成函數(shù)示例 )

一、證明指數(shù)生成函數(shù)求解多重集排列

---

多重集 $S=\{n_1?a_1,n_2?a_2,?,n_k?a_k\}$

多重集 $S$ 的 $r$ 排列數(shù) 組成數(shù)列 $\{a_r\}$ , 對應(yīng)的指數(shù)生成函數(shù)是 :

$G_e(x)=f_{n_1}(x)f_{n_2}(x)?f_{n_k}(x)$ ★

其中每個(gè)生成函數(shù)項(xiàng) $f_{n_i}(x)$ 是

$f_{n_i}(x)=1+x+\frac{x^2}{2!}+?+\frac{x^{n_i}}{n_i!}$ ★

將 $G_e(x)$ 展開 , 其中的 $r$ 系數(shù)就是多重集的排列數(shù) ; ★

證明上述指數(shù)生成函數(shù)用途 :

將上述 指數(shù)生成函數(shù) 展開 ,

指數(shù)生成函數(shù)項(xiàng) $G_e(x)=f_{n_1}(x)f_{n_2}(x)?f_{n_k}(x)$ , 由 $k$ 個(gè)因式相乘得到 ,

每個(gè)因式都會(huì)提供一個(gè) $\frac{x^{m_1}}{m_1!}$ 成分 ,

$\frac{x^{m_1}}{m_1!}$ 來自第一個(gè)因式 ,

$\frac{x^{m_2}}{m_2!}$ 來自第二個(gè)因式 ,

$?$

$\frac{x^{m_k}}{m_k!}$ 來自第 $k$ 個(gè)因式 ,

上述因式相乘 $\frac{x^{m_1}}{m_1!}?\frac{x^{m_2}}{m_2!}?\frac{x^{m_k}}{m_k!}$

其中 $m_1+m_2+?+m_r=r,$

$0\le m_i\le n_i,$ $i=0,1,2,?,k$

$\frac{x^{m_1}}{m_1!}?\frac{x^{m_2}}{m_2!}?\frac{x^{m_k}}{m_k!}$ 對應(yīng)了指數(shù)生成函數(shù)展開后的分項(xiàng) ;

$\frac{x^{m_1}}{m_1!}?\frac{x^{m_2}}{m_2!}?\frac{x^{m_k}}{m_k!}$

$=\frac{x^{m_1+m_2+?+m_k}}{m_1!m_2!?m_k!}$

$=\frac{x^r}{m_1!m_2!?m_k!}?\frac{r!}{r!}$

$=\frac{x^r}{r!}?\frac{r!}{m_1!m_2!?m_k!}$

$\frac{r!}{m_1!m_2!?m_k!}$ 是多重集 $r$ 個(gè)元素的全排列數(shù)

選了 $r$ 個(gè)元素 , 選擇的方法數(shù)是 $m_1+m_2+?+m_r=r$ 非負(fù)整數(shù)解個(gè)數(shù) , 配置完成后 , 再 進(jìn)行全排列 , 就可以得到 $r$ 排列 ;

( 先選擇 , 再進(jìn)行全排列 )

$a_r=\sum \frac{r!}{m_1!m_2!?m_k!}$

上述求和 , 每個(gè)分項(xiàng)都是滿足 $m_1+m_2+?+m_r=r$ 方程的非負(fù)整數(shù)解 , 每個(gè)非負(fù)整數(shù)解都對應(yīng)了多重集的 $S$ 的 $r$ 組合 ;

組合的全排列數(shù)是 $\frac{r!}{m_1!m_2!?m_k!}$ ,

上述求和 $a_r=\sum \frac{r!}{m_1!m_2!?m_k!}$ 是 針對所有滿足方程的一切非負(fù)整數(shù)解進(jìn)行求和 ;

總結(jié)

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

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