TJOI2015 概率论

$$ \text{设}f\left( n \right) \text{表示}n\text{个节点的二叉树的个数} \\ f\left( 0 \right) =\text{1,}f\left( n \right) =\sum_{0\le i\le n-1}{f\left( i \right) \times f\left( n-1-i \right)}=Cat_n\left( \text{枚举左右子树节点数} \right) \\ \text{设}f\left( n \right) \text{的生成函数为}F\left( x \right) ,\text{则有} \\ F\left( x \right) =xF^2\left( x \right) +1 \\ \text{解得}F\left( x \right) =\frac{1-\sqrt{1-4x}}{2x}\left( \text{另一根无意义} \right) \\ \text{对于}g\left( n \right) \\ g\left( 0 \right) =0 \\ g\left( n \right) =2\sum_{0\le i\le n-1}{g\left( i \right) \times f\left( n-1-i \right)}\left( \text{枚举左子树大小} \right) \\ \text{设}g\left( n \right) \text{的生成函数为}G\left( x \right) \\ G\left( x \right) =2xG\left( x \right) F\left( x \right) +x \\ G\left( x \right) =\frac{x}{\sqrt{1-4x}}=x\left( 1-4x \right) ^{-\frac{1}{2}} \\ \text{现在在于如何求出}\frac{g\left( n \right)}{f\left( n \right)} \\ \left( xF\left( x \right) \right) `=\left( \frac{1-\sqrt{1-4x}}{2} \right) `=\frac{1}{\sqrt{1-4x}}=\frac{G\left( x \right)}{x} \\ \text{因为}\left( xF\left( x \right) \right) `\text{是数列}\left( n+1 \right) f\left( n \right) \text{的生成函数} \\ \text{所以}\left( n+1 \right) f\left( n \right) =g\left( n+1 \right) \\ nf\left( n-1 \right) =g\left( n \right) \\ \text{所以}\frac{g\left( n \right)}{f\left( n \right)}=\frac{nf\left( n-1 \right)}{f\left( n \right)}=\frac{nCat_{n-1}}{Cat_n} \\ Cat_n=\frac{\left( \begin{array}{c} 2n\\ n\\ \end{array} \right)}{n+1} \\ \frac{g\left( n \right)}{f\left( n \right)}=\frac{n\left( n+1 \right)}{2\left( 2n-1 \right)} $$

n=int(input())
print("%.9f"%(n*(n+1)/(2*(2*n-1))))