Forget formal proof. Right at the beginning of the paper there is formula for the number of nodes with d children.
I have added an extra small explanation
I have added an extra small explanation
I have added extra explanation, and also a note 
Sure you are right, but in description gcd(P,Q) = 1 so just being precise
Sure you are right, but in problemās description gcd(P,Q) = 1 so just being precise
1 Like
Can anybody please elaborate on the observation 2 part please -āLetās consider all different (n-1) ordered trees, and think about applying this operation. Choosing an arbitrary node of a tree and linking it to a single child (nth node) and removing all edges between our chosen node and its children, then linking them to our new node. So our new node would serve as a single child of the chosen oneā
How to perform this operation?
I tried to explain it as much as possible, If you donāt understand at all why are we doing this you should check the link I have added right now (linearity of expectation)
Okay,thanks!
āObserve that each node in a tree consisting of n nodes and having only one child can be formed by applying this operation to only one tree of (n-1) nodes. Itās exactly the same as choosing an opened bracket and its corresponding closing bracket in a simple balanced bracket sequence framing the subexpression between by a pair of brackets (our new node).ā
Would you mind adding in a pictorial representation to describe how the operation is done?
1 Like
What difference does it make if I write 2*(n)%MOD and (n+n)%MOD?
Under the rules of long contests, āit is alright to refer to tutorials, books and other materials, learn a concept and then apply the same to solve a problem during a contest.ā Hence itās fine to do research as long as you do it on your own and you donāt actively discuss with other participants.
1 Like
Thatās fair enough. Although in this particular case the paper starts with stating a few results, the formula required to solve the problem among them, and one would be able to use it without going through the rest of the paper to follow the derivation.
Can someone explain in detail more about what ordered trees mean in this context? I have checked on various site - stackoverflow etc . but couldnt understand muchā¦
Thanks in advance.
Thanks mate. Saw this but couldnt understand much. I dont seem to understand the concept behind the word ordering.
After some hours of hard thinking, I came up with this explanation/proof for the calculation of p. Hope it is useful and to get feedback in case Iām mistaken.
We want to count the number of vertices with one child in all trees of n + 1 vertices (n edges). Letās call this number pā.
Imagine to lay out all the C_n trees and label each treeās vertices from 0 to n, top-to-bottom, left-to-right (the root is always 0).
To find pā, you could fix a tree, count the number of vertices with one child in this tree, and then sum over all the trees. This doesnāt lead to an easy closed formula.
Instead, fix a vertex v in [1ā¦n] and count how many trees, among the C_n, are such that parent[v] has only one child v. Summing over all vās will give us pā.
For each v, removing (parent[v], v) from the tree by the operation explained above, gives us a n-vertice tree. There are exactly C_{n-1} such trees and they must all appear in our original layout (of C_n trees).
Furthermore, there is no double-counting: otherwise there would be v1, v2 in [1ā¦n] from trees T1, T2 resp., such that removing (parent[v1], v1) and (parent[v2], v2) leads to the same tree, except for the labels. This means T1=T2 would appear twice in out original layout, which is impossible by construction.
There are n vertices, each associated with C_{n-1} trees, therefore pā = n * C_{n-1}. For p, just let n = k - 1 and substitute.
1 Like
I know, itās kinda subjective. Of course, following the derivation is still best. But I donāt think we can control the way the paper was written, and either way, there was a need to code/derive more concepts beyond the formula after all. And so, officially, reading a research paper is not cheating, but if you are still unsure, you can leave it to your conscience and ethics to decide. I hope that was clear
I have explained my solution here Though it is very long I have made an attempt to explain everything.