传送门
生成函数好题。
题意简述：求nnn个点的树的叶子数期望值。
思路：
考虑fnf_nfn表示nnn个节点的树的数量。
所以有递推式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−1fifn−1−i(n>0)
正是一个卷积的形式。
那么fnf_nfn的生成函数F(x)=xF2(x)+1F(x)=xF^2(x)+1F(x)=xF2(x)+1 注意要填上f0f_0f0
同理，考虑gng_ngn表示nnn个节点的树的叶子数总数。
有递推式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−1fign−i−1(n>1)
所以gng_ngn的生成函数G(x)=2xF(x)G(x)+xG(x)=2xF(x)G(x)+xG(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−4xx
然后我们对xF(x)xF(x)xF(x)求导：(xF(x))′=11−4x=G(x)x(xF(x))'=\frac1{\sqrt{1-4x}}=\frac{G(x)}x(xF(x))′=1−4x1=xG(x)
而对于xF(x)xF(x)xF(x)第nnn项fnxn+1f_nx^{n+1}fnxn+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+1xn+1=gn+1xn，那么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∞pnxn
那么gn=fn−1n=pnfn=>pn=fn−1nfng_n=f_{n-1}n=p_nf_n=>p_n=\frac{f_{n-1}}{nf_n}gn=fn−1n=pnfn=>pn=nfnfn−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;
}