Problem #148
Levels in Tree
Consider a tree with n nodes rooted at node 1 . We define parent[i] as the parent of ith node. For each 2 <= i <= n , parent[i] can assume any value from 1 to i - 1 with equal probability. Let F(n) the expected value of the sum of levels of all nodes. 1st node is at level 1 and for each 2 <= i <= n , if node i has level x , parent[i] has level x - 1 .
Given F(10) = 29.28968
Enter your answer as the greatest integer less than or equal to F(12345678) .