Number of ways to label a kind of tree in a certain way

Question

In my combinatorics class, I have just met the following problem

Suppose we have a rooted tree (tree where one node is special as the root) with $n$ nodes. Further, we suppose that besides the root, the tree has no branching nodes) so we consider the following representative image the blackened node is the root. Suppose we are given one of these trees, how can we count the number of different ways to label this tree (up to isomorphism of rooted trees with labels) with the $n$ letters $\{1,2,...,n\}$ such that a parent's label is always less than that of a child, so the following two lableings are allowed and actually count as the same

This problem has me stumped. I do not see a way, given one of these special rooted trees, to actually count the number of these special labelings. Is there a way, given one of these special rooted trees, to quickly write down the number of the different allowed labelings? I thank all helpers.

Answer 1

This is the same as the number of ways to partition an $(n-1)$-element set into subsets whose sizes are the lengths of the different paths away from the root. For example, in the middle Allowed example, the number of such labelings is the number of partitions of $\{2,\dots,9\}$ into four subsets with sizes $3,2,2,1$ (and the two $2$-element subsets are not distinguished from each other). This is almost the multinomial coefficient $\big( {8\atop3,2,2,1} \big) = \frac{8!}{3!2!2!1!}$, except that there needs to be an extra factor ($\frac12$ here) to account for the fact that different subsets of the same size aren't distinguished.

Answer 2

The restrictions on the tree itself force a specific structure: from the root there branch out paths of different lengths. Obviously, the root must be labelled $1$. Now let the lengths of the paths branching out from the root (excluding the root itself) be $l_1>l_2>\dots>l_k\ge1$, where each path length occurs $m_1,m_2,\dots,m_k$ times. Clearly $\sum_il_im_i=n-1$.

It is also clear that labels must increase going from root to terminal vertex. To a branch of length $l$ we associate $l$ chips of a distinct colour. Then we write the numbers from $2$ to $n$ on those chips; up to branch swapping, this uniquely determines which numbers go onto which chips.

Therefore, the number of admissible labellings before accounting for multiple branches of the same length is given by a multinomial coefficient: $$\frac{(n-1)!}{\prod_il_i!^{m_i}}$$ Because swapping branches does not make a new labelling, we must divide by $m_i!$ for each $i$, yielding the final answer as $$\frac{(n-1)!}{\prod_il_i!^{m_i}m_i!}$$