Counting labelled trees with given indegree sequence

摘要

For a labelled tree on the vertex set [n]: = {1, 2, ..., n}, define the direction of each edge ij to be i → j if i < j. The indegree sequence of T can be considered as a partition λ ? 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 λ. In this paper we give two proofs of Cotterill's conjecture: one is "semi-combinatorial" based on induction, the other is a bijective proof.