1
$\begingroup$

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 enter image description here 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 enter image description here

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.

$\endgroup$
1
  • 1
    $\begingroup$ What do you mean by parent and child here? Is root the only parent? or first levels are parents for second levels? $\endgroup$
    – Math Lover
    Oct 12, 2020 at 8:00

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Once the subset is chosen, the order is uniquely determined by that constraint. I recommend trying it on small examples, such as a six-node tree with two length-2 paths and one length-1 path out of the root node, for which $\frac12\big( {5\atop2,2,1} \big) = 15$; you should be able to enumerate all labelings and all set-partitions by hand and see the bijection. $\endgroup$ Oct 12, 2020 at 8:23
1
$\begingroup$

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!}$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .