Expected Number of Leaves in a Random Rooted Binary Tree

ZJY began studying probability theory to boost her intelligence and encountered the following problem: Given a random rooted binary tree with (n) nodes (where all structurally distinct trees appear with equal probability), what is the expected number of leaves?

A node is considered a leaf if it has no children. Note that any binary tree (with at most two children per node) generated obeys the recurrence below. In particular, if we denote by (T(n)) the total number of binary trees with (n) nodes and by (L(n)) the sum of leaf counts over all such trees, then every tree satisfies the identity [ L(n) = \begin{cases} 1, & n=1,\[1mm] 2\cdot L(n-1) + \sum_{i=1}^{n-2} \Bigl(L(i)\cdot T(n-i-1) + T(i)\cdot L(n-i-1)\Bigr), & n \ge 2, \end{cases} ] with [ T(n) = \begin{cases} 1, & n=1,\[1mm] 2\cdot T(n-1) + \sum_{i=1}^{n-2} T(i)\cdot T(n-i-1), & n \ge 2. \end{cases} ] Thus, the expected number of leaves is given by (\frac{L(n)}{T(n)}).

For your reference, here is the pseudo‐code for checking isomorphism between two trees:

[ \def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{Algorithm 1} & \text{Check}(T_1, T_2) \ \hline 1 & \textbf{Require: Two trees with roots } T_1 \text{ and } T_2 \ 2 & \quad \textbf{if } T_1 = \text{null or } T_2 = \text{null then} \ 3 & \quad\quad \textbf{return } (T_1 = \text{null and } T_2 = \text{null}) \ 4 & \quad \textbf{else} \ 5 & \quad\quad \textbf{return } \text{Check}(T_1\to\mathit{leftson}, T_2\to\mathit{leftson}) \text{ and } \text{Check}(T_1\to\mathit{rightson}, T_2\to\mathit{rightson}) \ 6 & \quad \textbf{endif} \ \hline \end{array} ]

inputFormat

The input consists of a single integer (n) ((1 \le n\le 1000), though the practical limits ensure that the computed values do not overflow) representing the number of nodes in the binary tree.

outputFormat

Output the expected number of leaves in the random rooted binary tree, printed as a floating-point number with 6 decimal places.

sample

1

1.000000