Find the expectation value

356 Views Asked by At

Given the number of nodes, $N$ in a tree, there are many possible ordered trees. We need to find the expectation value of the number of nodes with only $1$ child.
Assume that all ordered trees have equal probability of selection.
Eg:
$N=1, ans=0/1$
$N=2, ans=1/1$
$N=3, ans=(2+0)/2=1$
For $N=3$, there are only 2 possible ordered trees: A-B-C with A as root or B as root.
When A is root, A,B have 1 child.
When B is root, none of them have 1 child.