数学2

EGF

对于一个数列 \(<f_n>\) ，其指数型生成函数\(（EGF）\) \(F_n=\sum_{0\le n}\frac{f_n}{n!}x^n\) 。

注意到其中的 \(\frac{1}{n!}\) 这一项，在计算组合数的时候，往往会用到阶乘，那么可以发现两个多项式的二项式卷积结果的 \(EGF\)，为它们的 \(EGF\) 卷积。

(以下记对应字母的大写为它的 \(EGF\) )

\[c_n=\sum_{i=0}^n \binom{n}{i}a_ib_{n-i}\\ \frac{c_n}{n!}=\sum_{i=0}^n \frac{a_i}{i!} \frac{b_{n-i}}{(n-i)!}\\ C_n=\sum_{i=0}^n A_iB_{n-i}\\ C=A\times B \]

如此便能解决一些分成两组，且方案数不同的问题，如n个点构成一个环和一颗树的方案数。

EGF的exp与ln

exp我们用它的泰勒展开式：

\[exp(f)=\sum_{0\le n}\frac{1}{n!} f^n \]

首先它和 \(EGF\) 一样有阶乘，这肯定是用于组合数的计算，此外，它还多了一个 \(f^n\) ，\(exp\)干的事情就是在知晓一组方案的生成函数时，可以知道它分成若干组的方案。

ln我们不需要借用它的泰勒展开式与组合意义，只需要用它是exp的反函数即可。

首先，我们尝试构建这个 \(EGF 的exp\) 的状物：

\[令G=exp(F),F=ln(G)\\ G=\sum_{0\le n}\frac{1}{n!} F^n\\ [x^n]G=\sum_{0\le i\le n}\frac{1}{i}[x^n]F^i\\ [x^n]G=\sum_{0\le i\le n}\frac{1}{i}\sum_{k_1+k_2+...+k_i=n}\frac{1}{\Pi_{1\le j\le i} k_j!}\Pi_{1\le j\le i} f_j!\\ g_n=\sum_{0\le i\le n}\frac{1}{i}\sum_{k_1+k_2+...+k_i=n}\frac{n!}{\Pi_{1\le j\le i} k_j!}\Pi_{1\le j\le i} f_j! \]