【组合数学】指数生成函数 ( 证明指数生成函数求解多重集排列 )

韩曙亮

发布于 2023-03-28 18:43:06

6310

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、证明指数生成函数求解多重集排列

参考博客 : 按照顺序看

一、证明指数生成函数求解多重集排列

多重集

S=\{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}

多重集

S

的

r

排列数组成数列

\{ a_r \}

, 对应的指数生成函数是 :

G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)

★

其中每个生成函数项

f_{n_i}(x)

是

f_{n_i}(x) = 1 + x + \cfrac{x^2}{2!} + \cdots + \cfrac{x^{n_i}}{n_i!}

★

将

G_e(x)

展开 , 其中的

r

系数就是多重集的排列数 ; ★

证明上述指数生成函数用途 :

将上述指数生成函数展开 ,

指数生成函数项

G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)

, 由

k

个因式相乘得到 ,

每个因式都会提供一个

\cfrac{x^{m_1}}{m_1!}

成分 ,

\cfrac{x^{m_1}}{m_1!}

来自第一个因式 ,

\cfrac{x^{m_2}}{m_2!}

来自第二个因式 ,

\vdots

\cfrac{x^{m_k}}{m_k!}

来自第

k

个因式 ,

上述因式相乘

\cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}

其中

m_1 + m_2 + \cdots + m_r = r \ \ \ ,

0 \leq m_i \leq n_i \ \ ,

i= 0,1,2, \cdots , k

\cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}

对应了指数生成函数展开后的分项 ;

\ \ \ \ \cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}

=\cfrac{x^{m_1 + m_2 + \cdots + m_k}}{m_1!m_2!\cdots m_k!}

=\cfrac{x^{r}}{m_1!m_2!\cdots m_k!} \cdot \cfrac{r!}{r!}

=\cfrac{x^{r}}{r!} \cdot \cfrac{r!}{m_1!m_2!\cdots m_k!}

\cfrac{r!}{m_1!m_2!\cdots m_k!}

是多重集

r

个元素的全排列数

选了

r

个元素 , 选择的方法数是

m_1 + m_2 + \cdots + m_r = r

非负整数解个数 , 配置完成后 , 再进行全排列 , 就可以得到

r

排列 ;

( 先选择 , 再进行全排列 )

a_r = \sum\cfrac{r!}{m_1!m_2!\cdots m_k!}

上述求和 , 每个分项都是满足

m_1 + m_2 + \cdots + m_r = r

方程的非负整数解 , 每个非负整数解都对应了多重集的

S

的

r

组合 ;

组合的全排列数是

\cfrac{r!}{m_1!m_2!\cdots m_k!}

,

上述求和

a_r = \sum\cfrac{r!}{m_1!m_2!\cdots m_k!}

是针对所有满足方程的一切非负整数解进行求和 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-30，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度