随机贴个欧拉数的 BGF 推导

· · 个人记录

发现我有丶拉，最近好好读了一下 Analytic Combinatorics 发现里面提到的「符号化容斥」还挺好用的。

这里以欧拉数为例。我们知道我们一般做二项式反演都要先作「钦定」，因此我们考虑直接把「钦定」这件事的信息算进 GF 里。
首先考虑只是可能钦定若干个升高，即每个升高可以被钦定或者不钦定，但不计数其他信息的这样的方案数。
我们知道这就是考虑 k-1 个极长连续升高会把这个子串连成一个长度 k 的上升段，且必然有 k \ge 2。
这样其即是

\frac1{1-z-(\mathrm e^z - 1 - z)} = \frac1{2-\mathrm e^z}

考虑用一个元 t 计数被钦定的升高的个数，那么即

\frac1{1-z-\frac{\mathrm e^{tz} - 1 - tz}t} = \frac t{1+t-\mathrm e^{tz}}

令其为 G(z,t)，令欧拉数的真实 GF 为 F(z,t)，那么我们知道 F 到 G 有每个升高钦定与否的区别，因此

G(z,t) = F(z,1+t)

即

F(z,t) = G(z,t-1) = \frac{t-1}{t-\mathrm e^{(t-1)z}}

没了，就这！

另外原来 jly 作业题是 Analytic Combinatorics 原题（