OGF

· · 个人记录

学习笔记：\text{OGF}

定义\text{(OGF)}：实数序列 a_0,a_2,\cdots,a_n 的普通生成函数是无穷级数

G(x)=\sum_{i=0}^{\infty}a_ix^i

引入一些比较经典的生成函数：

斐波那契生成函数：

由：a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}(n > 1)

有：

F(x)=xF(x)+x^2F(x)+a_0+a_1x-a_0x \therefore F(x)=\dfrac{x}{1-x-x^2}

考虑如何将其展开。

考虑等比数列的封闭形式与展开形式。

待定系数可得：

\dfrac{x}{1-x-x^2}=\dfrac{\dfrac{1}{\sqrt{5}}}{1-\dfrac{1+\sqrt{5}}{2}x}+\dfrac{-\dfrac{1}{\sqrt{5}}}{1-\dfrac{1-\sqrt{5}}{2}x}

那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：

\dfrac{x}{1-x-x^2}=\sum_{x\geq 0}x^n\dfrac{1}{\sqrt{5}}\left( \left( \dfrac{1+\sqrt{5}}{2} \right)^n - \left( \dfrac{1-\sqrt{5}}{2} \right)^n \right)

卡特兰数的生成函数：

卡特兰数的递推式：

H_n=\sum_{i=0}^{n-1}H_iH_{n-i-1}

其中

我们用卷积来构造关于 H(x) 的方程：

H(x)=\sum_{n \geq 0} H_nx_n =1+\sum_{n \geq 1} \sum_{i=0}^{n-1} H_nx^iH_{n-i-1}x^{n-i-1}x =1+xH^2(x)

解得：

H(x)=\dfrac{1\pm \sqrt{1-4x}}{2x}

由于 H_0=H_1=1。

\therefore H(x)=\dfrac{1+ \sqrt{1-4x}}{2x}

我们运用牛顿二项式定理。

(1-4x)^{\frac{1}{2}}=\sum_{n \geq 0}\dbinom{\frac{1}{2}}{n}(-4x)^n (1-4x)^{\frac{1}{2}}=1+\sum_{n \geq 1} \frac{(\frac{1}{2})^{\underline n}}{n!}(-4x)^n

注意到 (\frac{1}{2})^{\underline n}=\dfrac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!}

带回原式：

(1-4x)^{\frac{1}{2}}=1+\sum_{n \geq 1}\dfrac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n (1-4x)^{\frac{1}{2}}=1-\sum_{n \geq 1}\dfrac{(2n-2)!}{(n-1)!n!}2x^n (1-4x)^{\frac{1}{2}}=1-\sum_{n \geq 1}\dbinom{2n-1}{n}\dfrac{1}{2n-1} 2x^n

带回原式：

H(x)=\dfrac{1\pm \sqrt{1-4x}}{2x} H(x)=\dfrac{1}{2x}\sum_{n \geq 1}\dbinom{2n-1}{n}\dfrac{1}{2n-1} 2x^n H(x)=\sum_{n \geq 1}\dbinom{2n-1}{n}\dfrac{1}{2n-1} x^{n-1} H(x)=\sum_{n \geq 0}\dbinom{2n+1}{n+1}\dfrac{1}{2n+1} x^{n} H(x)=\sum_{n \geq 0}\dbinom{2n}{n}\dfrac{1}{n+1} x^{n}

这样我们就得到了卡特兰数的通项公式。

练手题：

这道题明显是卡特兰数的变式题： 设 $h_i$ 表示这 $H_i$ 个二叉树的叶子节点个数之和，有 $h_0=0,h_1=1$。 我们可以根据对称性及其定义可得： $$\forall n \geq 2 : h_n=2\sum_{i=0}^{n-1}h_iH_{n-i-1}$$ 根据生成函数乘法性质： $$h(x)-h_0-h_1x=2h(x)H(x)x$$ 根据 $\therefore H(x)=\dfrac{1+ \sqrt{1-4x}}{2x}

有：

h(x)=\dfrac{x}{\sqrt{1-4x}} h(x)=x\sum_{i=0}^{\infty} \dbinom{-\frac{1}{2}}{i}(-4x)^i h_n=\dbinom{-\frac{1}{2}}{n-1}(-1)^{n-1}2^{2(n-1)}=\dfrac{\prod_{i=0}^{n-2}(-\frac{1}{2}-i)}{(n-1)!}(-1)^{n-1}2^{2(n-1)} =\dfrac{(2n-3)!!}{(n-1)!}2^{n-1}=\dfrac{(2n-2)!}{((n-1)!)^2}=\dbinom{2n-2}{n-1}

那么题意所求的期望为：

\dfrac{h_n}{H_n}=\dfrac{n(n+1)}{2(2n-1)} $\text{P4841}$：[$check$](https://www.luogu.com.cn/problem/P4841) 这里设 $f_n$ 为**点数为 $n$ 的无向连通图**，$g_n$ 为**点数为 $n$ 的无向连通图** 显然： $$g_n=\sum_{i=1}^{n}\dbinom{n-1}{i-1}f_{i}g_{n-i}$$ 仔细思考，又有： $g_n=2^{\binom{n}{2}}$。 带入式子： $$2^{\binom{n}{2}}=\sum_{i=1}^{n}\dbinom{n-1}{i-1}f_{i}2^{\binom{n-i}{2}}$$ $$\dfrac{2^{\binom{n}{2}}}{(n-1)!}=\sum_{i=1}^{n}\dfrac{f_{i}}{(i-1)!}\dfrac{2^{\binom{n-i}{2}}}{(n-i)!}$$ 然后定义： $$f(x)=\sum_{n=1}^{\infty}\dfrac{f_{n}}{(n-1)!}x^i$$ $$g(x)=\sum_{n=0}^{\infty}\dfrac{2^{\binom{n}{2}}}{n!}x^i$$ $$h(x)=\sum_{n=1}^{\infty}\dfrac{2^{\binom{n}{2}}}{(n-1)!}x^i$$ $g(x),h(x)$ 都是已知的，对 $g$ 进行多项式求逆，再乘 $h$ 即可。 [$code$](https://www.luogu.com.cn/blogAdmin/article/edit/400427)