Counting Labelled Trees with Given Indegree Sequence

Abstract

For a labelled tree on the vertex set $[n]:=\{1,2,...,n\}$, define the direction of each edge $ij$ to be $i\to j$ if $i<j$. The indegree sequence of $T$ can be considered as a partition $\lambda ⊢n-1$. The enumeration of trees with a given indegree sequence arises in counting secant planes of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on $[n]$ with indegree sequence corresponding to a partition $\lambda$. In this paper we give two proofs of Cotterill's conjecture: one is `semi-combinatorial" based on induction, the other is a bijective proof.

10 pages