Distributing integers on a tree .

Question

We have an undirected tree with N vertices and we want to distribute integer numbers starting from 1 to N such that every parent element has smaller element than it's child .The root vertex is 1 . In how many ways we can distribute the numbers ?

Example : Let's say we have 3 vertices in the tree and they are connected like this .
1 2 (1 is connected with 2).
1 3 (1 is connected with 3).
So the Ans for this will be 2 . Because we can write 2 on vertex 2 and 3 on vertex 3 or we can write 3 on vertex 2 and 2 on vertex 3 . So total number of ways is 2 .

Actually the formula is n!/(s₁s₂...s_n) . Where s_i is the the size of the subtree rooted at vertex i .

But I don't know how to prove it . Can anybody provide the proof for the same .

P.S : Let's say the tree contains 5 vertices and they are connected like this .
1 2.
1 3.
1 4.
2 5.
The no. of ways for this tree will be 5!/(5*2*1*1*1) = 12 .

Answer 1

You can prove this by induction on the size $n$ of the tree.

Notice that after writing $1$ on the root, we can divide the remaining $n-1$ labels among the root's immediate subtrees however we want. If these subtrees have sizes $k_1,\dots,k_m$, then the number of ways to do this is the multinomial coefficient $\binom{n-1}{k_1,\dots,k_m}=\frac{(n-1)!}{k_1!\cdots k_n!}$. After choosing this allocation, we have subtrees of sizes $k_1,\dots,k_m$ to label. By induction hypothesis, the number of ways to label a tree of size $k<n$ is $\frac{k!}{s_1\cdots s_r}$ (where the $s_i$ are the sizes of the subtrees of that tree, including $k$ itself), so the total number of ways to label our $n$-tree is

$$\frac{(n-1)!}{k_1!\cdots k_n!}\cdot\frac{k_1!}{s\cdots s}\cdots\frac{k_m!}{s\cdots s}=\frac{n!}{n\cdot s\cdots s}$$

where the "$s$" values in the denominator are the sizes of all our subtrees except $n$ itself.

Answer 2

This was a problem from Atcoder Programming Contest held yesterday (though actual problem needed re-rooting additionally). I actually participated in that contest, and here is my approach to this problem.

Consider a slightly different situation. We try with a random permutation of $1, 2, \dots n$ and compute probability of getting a valid one. We then multiply that probability with $n!$ since we have total $n!$ permutations.

If $a$ is a ancestor (in a tree) of $b$, we have a constraint for our permutation - that $a$ must come up before $b$.

For example, consider $a$ having $b, c, d$ in it's subtree (which order of b, c, d does not matter). Then, in our permutation, $a$ must come before $b, c, d$. Probability of being so is $\frac{1}{4}$ since all permutation of $a, b, c, d$ is equally likely and we have 6 of them sufficing $a > (b, c, d)$ (in order of permutation). This is where $ 1 / s_i$ comes up.

Then observe that for each node, this process is independent. $a$ coming up before $b$ does not change probability of $b$ coming up before $c$.