How many ways can we extend a partial order of a rooted tree to a total order?

120 Views Asked by At

Consider a rooted tree $\mathcal{T} = (T,\rho)$, where $T=(V,E)$.

Given $v_1,v_2 \in V$, $v_1 \preceq v_2$ iff the unique path from $\rho$ to $v_2$ contains $v_1$. We say that $v_2$ is a descendant of $v_1$.

We say that $h:V \to [|V|]:=\{1,...,|V|\}$ is a rank function for $\mathcal{T}$ if $h$ is injective and $$v_1 \preceq v_2 \implies h(v_1) \leq h(v_2).$$

I'm trying to prove the following Proposition:

Proposition. For each $v \in V$ let $\lambda_v$ be the number of elements of $V$ that are descendants of $v$, that is, $$\lambda_v=|\{u \in V: v \preceq u\}|.$$ Then, the number of rank functions for $\mathcal{T}$ is $$\frac{|V|!}{\prod_{v \in V}\lambda_v}.$$

I tried to apply induction on the number of vertices by removing one leaf, but it doesn't seem easy to count the number of ways we can extend a ranked function for this tree with the removed vertex to a rank function for the actual tree.

I appreciate any help!