PROBLEM LINK:
Author: Aleksandr Kulkov
Primary Tester: Misha Chorniy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Medium
PREREQUISITES:
Combinatorics,Math,Number Theory
PROBLEM:
Consider an ordered tree with N vertices. Your task is to calculate the expected value of the number of vertices having exactly one child in such tree assuming that it is uniformly chosen from the set of all ordered trees of size N.
Consider the answer to be a proper fraction P/Q, where gcd(P, Q) = 1. Then your task is to output two integers PQ-1 mod 109+7 and PQ-1 mod 109+9
EXPLANATION:
OBSERVATION 1:
The number of ordered trees consisting of n nodes is equal to the (n-1)th catalan number. Imagine the Depth-First-Search order of the nodes of the trees, entering each node corresponds to an open bracket ( , and finishing each node corresponds to a closed bracket ) . So if we represented the DFS order of a tree it will form a simple balanced bracket sequence.
Two different ordered trees must have different bracket representations. So we can say that the number of ordered trees consisting of n nodes is equal to the number of balanced bracket sequences consisting of (n-1) pairs of brackets. (n-1) because our tree is connected so we must fix the root (the first and the last bracket in the expression). If the subexpression (the expression excluding the first and last bracket) is balanced, that guarantees that we will never exit the root before the last bracket and our tree is connected.
It’s well known that the number of balanced bracket sequences of n pairs of brackets is equal to the nth catalan number.
C_n = \frac{(2n)!}{(n+1)!n!}
Before reading the next observation you should be familiar with Linearity Of Expectation.
OBSERVATION 2:
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.
A node having one child in a tree is equivalent to a pair of brackets, with a balanced expression between them and surrounded by a pair of brackets.
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).
Thus our nominator P would be
P = ( number of trees of n-1 nodes * (n-1) )
We multiplied by n-1 which denotes the number of ways to choose the vertex we decided to apply this operation on.
Q = ( number of trees of n nodes )
answer = \frac{C_{n-2} * (n-1)}{C_{n-1}}
According to the catalan number formula we wrote above, this can be reduced to:
answer = \frac{n * (n-1)}{4n-6}
This fraction can be reduced easily by calculating GCDs between the denominator and the nominator terms. We can calculate PQ-1 after calculating the modular inverse of Q considering each modulo.
Note:
It’s true that this solution is given without a formal proof. But the idea is quite simple and correct. Actually its correctness can be proved by intuition. In real life contests you won’t have the internet to read formal proofs and papers or search for formulas for a sequence. This solution is not hard to get from scratch and worths trying.
AUTHOR’S AND TESTER’S SOLUTIONS:
AUTHOR’s solution: Will be found here
TESTER’s solution: Will be found here
EDITORIALIST’s solution: Will be found here
