两学一做网站网站/优化营商环境条例心得体会

传送门
生成函数好题。
题意简述：求$n$个点的树的叶子数期望值。

---

思路：
考虑fnf_nfn​表示$n$个节点的树的数量。
所以有递推式f0=1,fn=∑i=0n−1fifn−1−i(n>0)f_0=1,f_n=\sum_{i=0}^{n-1}f_if_{n-1-i}(n>0)f0​=1,fn​=∑i=0n−1​fi​fn−1−i​(n>0)
正是一个卷积的形式。
那么fnf_nfn​的生成函数F(x)=xF2(x)+1F(x)=xF^2(x)+1F(x)=xF2(x)+1 注意要填上f0f_0f0​
同理，考虑gng_ngn​表示$n$个节点的树的叶子数总数。
有递推式g0=0,g1=1,gn=2∑i=0n−1fign−i−1(n>1)g_0=0,g_1=1,g_n=2\sum_{i=0}^{n-1}f_ig_{n-i-1}(n>1)g0​=0,g1​=1,gn​=2∑i=0n−1​fi​gn−i−1​(n>1)
所以gng_ngn​的生成函数$G(x)=2xF(x)G(x)+x$ 注意要填上g1g_1g1​
然后F(x)=xF2(x)+1F(x)=xF^2(x)+1F(x)=xF2(x)+1
<=>xF2(x)−F(x)+1=0xF^2(x)-F(x)+1=0xF2(x)−F(x)+1=0
<=>F(x)=1−1−4x2xF(x)=\frac{1-\sqrt{1-4x}}{2x}F(x)=2x1−1−4x​​ 不取1+1−4x2x\frac{1+\sqrt{1-4x}}{2x}2x1+1−4x​​是因为它不能向0收敛
G(x)=x1−2xF(x)=x1−4xG(x)=\frac x{1-2xF(x)}=\frac x{\sqrt{1-4x}}G(x)=1−2xF(x)x​=1−4x​x​
然后我们对$xF(x)$求导：(xF(x))′=11−4x=G(x)x(xF(x))&#x27;=\frac1{\sqrt{1-4x}}=\frac{G(x)}x(xF(x))′=1−4x​1​=xG(x)​
而对于$xF(x)$第$n$项fnxn+1f_nx^{n+1}fn​xn+1求导之后会变成fn(n+1)xnf_n(n+1)x^nfn​(n+1)xn等式右边：gn+1xn+1x=gn+1xn\frac{g_{n+1}x^{n+1}}x=g_{n+1}x^nxgn+1​xn+1​=gn+1​xn，那么gn+1=fn(n+1)g_{n+1}=f_n(n+1)gn+1​=fn​(n+1)
我们令答案的函数是A(x)=∑i=0∞pnxnA(x)=\sum_{i=0}^{\infty}p_nx^nA(x)=∑i=0∞​pn​xn
那么gn=fn−1n=pnfn=&gt;pn=fn−1nfng_n=f_{n-1}n=p_nf_n=&gt;p_n=\frac{f_{n-1}}{nf_n}gn​=fn−1​n=pn​fn​=>pn​=nfn​fn−1​​
仔细观察会发现fnf_nfn​是卡特兰数，然后带入就做完了。
代码：

#include<bits/stdc++.h>
using namespace std;
int main(){double n;return scanf("%lf",&n),printf("%.9lf",n*(n+1)/(4*n-2)),0;
}