用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:生成函数_2

这是本文档旧的修订版!


指数生成函数(EGF)

算法简介

形如 $F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!}$ 的函数, $a_n$ 可以提供关于这个序列的信息,一般用于解决有标号组合计数问题。

基本性质

$$F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!},G(x)=\sum_{n=0}^{\infty}b_n\frac {x^n}{n!}$$

$$F(x)G(x)=\sum_{n=0}^{\infty}\sum_{i=0}^n a_ib_{n-i}\frac {x^n}{i!(n-i)!}=\sum_{n=0}^{\infty}\sum_{i=0}^n {n\choose i}a_ib_{n-i}\frac {x^n}{n!}$$

算法例题

2020-2021/teams/legal_string/jxm2001/生成函数_2.1597234684.txt.gz · 最后更改: 2020/08/12 20:18 由 jxm2001