EXPTREE: How to calculate P????

How to calculate P in this question???. I dont Understand Editorial. Please Help me.

Problem

Editorial

2 Likes

Go through this article http://www.cs.tau.ac.il/~nachumd/papers/Enumerations.pdf.
Link by @ruskinmanku in EXPTREE Editorial Section.

1 Like

This question is all about searching(According to me ). The link above takes you to some papers which has pre-calculated formulas. The no. of vertices which have d(for this d=1) childeren is (2n-1-d)!/((n-1)!*(n-d)!).
The no. of total possible trees is (2n)!/((n!n!)(n+1)).Where ā€˜nā€™ is no. of edges . Apply the formula and get the answer. For the modulo inverse http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/ .Hope this help.

1 Like

Well getting a formal proof is something really hard, you will find yourself ending in reading papers. My solution was the easiest thing that came up to my mind. Anyway, this solution is kind of intuitive :slight_smile:

I have added small extra explanation in the editorial and also a note which tells the purpose of the editorial