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

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

时间：2020-06-15 15:20:53

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

参考博客 :按照顺序看

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

多重集 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak}S=\{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \}S={n1⋅a1,n2⋅a2,⋯,nk⋅ak}

多重集 SSS 的 rrr 排列数组成数列 {ar}\{ a_r \}{ar} , 对应的指数生成函数是 :

Ge(x)=fn1(x)fn2(x)⋯fnk(x)G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)Ge(x)=fn1(x)fn2(x)⋯fnk(x) ★

其中每个生成函数项 fni(x)f_{n_i}(x)fni(x) 是

fni(x)=1+x+x22!+⋯+xnini!f_{n_i}(x) = 1 + x + \cfrac{x^2}{2!} + \cdots + \cfrac{x^{n_i}}{n_i!}fni(x)=1+x+2!x2+⋯+ni!xni ★

将 Ge(x)G_e(x)Ge(x) 展开 , 其中的 rrr 系数就是多重集的排列数 ;★

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

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

指数生成函数项 Ge(x)=fn1(x)fn2(x)⋯fnk(x)G_e(x) = f_{n_1}(x) f_{n_2}(x) \cdots f_{n_k}(x)Ge(x)=fn1(x)fn2(x)⋯fnk(x) , 由 kkk 个因式相乘得到 ,

每个因式都会提供一个 xm1m1!\cfrac{x^{m_1}}{m_1!}m1!xm1 成分 ,

xm1m1!\cfrac{x^{m_1}}{m_1!}m1!xm1 来自第一个因式 ,

xm2m2!\cfrac{x^{m_2}}{m_2!}m2!xm2 来自第二个因式 ,

⋮\vdots⋮

xmkmk!\cfrac{x^{m_k}}{m_k!}mk!xmk 来自第 kkk 个因式 ,

上述因式相乘 xm1m1!⋅xm2m2!⋯xmkmk!\cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}m1!xm1⋅m2!xm2⋯mk!xmk

其中 m1+m2+⋯+mr=r,m_1 + m_2 + \cdots + m_r = r \ \ \ ,m1+m2+⋯+mr=r,

0≤mi≤ni,0 \leq m_i \leq n_i \ \ ,0≤mi≤ni, i=0,1,2,⋯,ki= 0,1,2, \cdots , ki=0,1,2,⋯,k

xm1m1!⋅xm2m2!⋯xmkmk!\cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}m1!xm1⋅m2!xm2⋯mk!xmk 对应了指数生成函数展开后的分项 ;

xm1m1!⋅xm2m2!⋯xmkmk!\ \ \ \ \cfrac{x^{m_1}}{m_1!} \cdot \cfrac{x^{m_2}}{m_2!} \cdots \cfrac{x^{m_k}}{m_k!}m1!xm1⋅m2!xm2⋯mk!xmk

=xm1+m2+⋯+mkm1!m2!⋯mk!=\cfrac{x^{m_1 + m_2 + \cdots + m_k}}{m_1!m_2!\cdots m_k!}=m1!m2!⋯mk!xm1+m2+⋯+mk

=xrm1!m2!⋯mk!⋅r!r!=\cfrac{x^{r}}{m_1!m_2!\cdots m_k!} \cdot \cfrac{r!}{r!}=m1!m2!⋯mk!xr⋅r!r!

=xrr!⋅r!m1!m2!⋯mk!=\cfrac{x^{r}}{r!} \cdot \cfrac{r!}{m_1!m_2!\cdots m_k!}=r!xr⋅m1!m2!⋯mk!r!

r!m1!m2!⋯mk!\cfrac{r!}{m_1!m_2!\cdots m_k!}m1!m2!⋯mk!r! 是多重集 rrr 个元素的全排列数

选了 rrr 个元素 , 选择的方法数是 m1+m2+⋯+mr=rm_1 + m_2 + \cdots + m_r = rm1+m2+⋯+mr=r 非负整数解个数 , 配置完成后 , 再进行全排列 , 就可以得到 rrr 排列 ;

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

ar=∑r!m1!m2!⋯mk!a_r = \sum\cfrac{r!}{m_1!m_2!\cdots m_k!}ar=∑m1!m2!⋯mk!r!

上述求和 , 每个分项都是满足 m1+m2+⋯+mr=rm_1 + m_2 + \cdots + m_r = rm1+m2+⋯+mr=r 方程的非负整数解 , 每个非负整数解都对应了多重集的 SSS 的 rrr 组合 ;

组合的全排列数是 r!m1!m2!⋯mk!\cfrac{r!}{m_1!m_2!\cdots m_k!}m1!m2!⋯mk!r! ,

上述求和 ar=∑r!m1!m2!⋯mk!a_r = \sum\cfrac{r!}{m_1!m_2!\cdots m_k!}ar=∑m1!m2!⋯mk!r! 是针对所有满足方程的一切非负整数解进行求和 ;

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。