脚本宝典收集整理的这篇文章主要介绍了EGF，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
[hat{F}(x)=sum_{n} a_nfrac{x^n}{n!} ]
（全文都是以 EGF 为基础）
封闭形式
[sum_{nge 1} frac{x^n}{n!}=e^x ]
这个有关于麦克劳林级数（泰勒展开的一种特殊情况）
泰勒公式
若 (x) 在 (x_0) 处可导，那么当 (xto x_0) 时，函数的展开式近似于：
[f(x)=f(x_0)+frac{f'(x_0)}{1!}x+frac{f''(x_0)}{2!}x^2... ]
麦克劳林级数是我们在 (x_0to 0) 时的展开，也就是泰勒公式的一个特殊情况
[ln(1-x)=sum_{n=1}^{infty} -frac{1}{n}x^n ]
[ln(1+x)=sum_{n=1}^{infty}frac{(-1)^{n+1}}{n}x^n ]
排列和圆排列
长度为 (n) 的排列数的指数生成函数是
[P(x)=sum_{nge 0} frac{n!x^n}{n!}=frac{1}{1-x} ]
圆排列的定义是排成一个环的方案
(n) 个数的圆排列方案为 ((n-1)!)
[Q(x)=sum_{nge 1} frac{(n-1)!x^n}{n!}=sum_{nge 1} frac{x^n}{n}=-ln(1-x)=ln (frac{1}{1-x}) ]
那么 (exp(Q(x))=P(x))
exp 的直观理解
上述中一个排列的每种方案其实就是将原排列分成若干集合，每种集合组成一种置换环
那么方案数就是每种划分方案后的置换环的方案数的乘积
这个置换环的方案数实际上就是圆排列的方案数
形式化的，假设当前有 (n) 个元素，求 (A) 的方案数，设生成函数为 (F(x))
每种方案可以对应将 (n) 个元素先划分成若干个集合，每个集合 (B) 的方案数的乘积，设 (B) 的生成函数为 (G(x))
那么 (exp(G(x))=F(x))
推广
如果 (n) 个点 带标号 生成树的 EGF 是 (G(x)) ，(n) 个点 带标号 森林的 EGF 是 (F(x)) ，那么 (F(x)=exp(G(x)))
如果 (n) 个点带标号无向连通图的 EGF 是 (G(x)) ，那么 (n) 个点带标号无向图的 EGF 是 (exp(G(x)))
应用
长度为 (n) 的一个错排指 (p_ine i)
求错排的指数生成函数
从置换环的角度来看，实际上就是不存在长度为 1 的置换环，生成函数 (G(x)=sum_{ngeq 2 } frac{x^n}{n}=ln (frac{1}{1-x})-x)
那么错排的生成函数是 (exp(G(x)))
求有多少个映射 (f:{1,2,...,n} to {1,2,...,n}) ，使得
任意一个 (i) 映射 (k) 次后等于映射 (k-1) 次后映射的数是同一个数
考虑将 (i) 和 (f_i) 连边。相当于我们从任意一个 (i) 走 (k) 步和走 (k-1) 步到达的是同一个点
那么整个图就是一些带一个自环的基环树组成的，且环的深度不超过 (k) ，假设根的深度为 (1)
我们将环当成根，把边的方向反一下，那么整个图可以当成一些深度不超过 (k) 的生成树组成的
假设深度不超过 (k) 的生成树的方案数的生成函数为 (F_k(x))
实际上深度不超过 (k) 的生成树就是用一个节点将深度不超过 (k-1) 的森林连起来
那么 (F_k(x)=xexp(F_{k-1}(x)))
答案是 ([x^n]exp (F_k(x)))
给一个 (n) 个数的序列 (a_1,a_2,...,a_n) ，和初值为 0 的变量 (s) ，要求你重复一下操作 (k) 次
在 (1,2,...,n) 中等概率选择一个 (x)
令 (s) 加上 (Pi_{ine x} a_i)
令 (a_x) 减一
求 (k) 次操作后 (s) 的期望
(1leq n leq 5000,1leq kleq 10^9,0leq a_ileq 10^9)
首先随便减两个数，发现最终的结果和减的顺序没有关系
那么我们将一个数所有的减操作放在一起，再归纳一下，设每个数减少 (b_i)，可以得出
[s=prod_{i=1}^n a_i -prod_{i=1}^n (a_i-b_i) ]
那么我们的问题就转换成了 (prod_{i=1}^n (a_i-b_i)) 的期望
考虑计算每种方案的 (prod_{i=1}^n(a_i-b_i)) 的和，最后除 (n^k)
(k) 次序列中，要使得 (i) 出现 (b_i) 次的方案数是
[frac{k!}{b_1!b_2!...b_n!} ]
这和指数生成函数的系数类似
设 (a_j) 的指数生成函数是
[F_j(x)=sum_{ige 0} (a_j-i)frac{x^i}{i!} ]
那么答案就是 ([x^k]prod_{j=1}^nF_j(x))
为了快速计算答案，我们需要将 (F_j(x)) 转换成封闭形式
(F_j(x)=a_je^x-xe^x=(a_j-x)e^x)
(prod_{j=1}^n F_j(x)=e^{nx}prod_{j=1}^n(a_j-x))
(prod_{j=1}^n (a_j-x)) 是个 (n) 次多项式，可以暴力算，假设展开式是 (sum_{i=0}^n c_ix^i) ，那么
[begin{aligned} prod_{j=1}^n F_j(x)&=(sum_{ige 0}frac{n^ix^i}{i!})(sum_{i=0}^n c_ix^i)\ &=sum_{ige 0}sum_{j=0}^i c_jx^jfrac{n^{i-j}x^{i-j}}{(i-j)!}\ &=sum_{ige0}frac{x^i}{i!}sum_{j=0}^i n^{i-j}i^{underline{j}}c_j end{aligned} ]
答案就是这个多项式 (x^k) 的系数
以上是脚本宝典为你收集整理的EGF全部内容，希望文章能够帮你解决EGF所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。