Processing math: 100%

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) .

Contributed by Saharsh Luthra

Solved by 44 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.