KAIST Discrete Math Seminar

For a labeled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij as i to j if i<j. The indegree sequence λ=1^e₁2^e₂ … is then a partition of n-1. Let a_λ be the number of trees on [n] with indegree sequence λ. In a recent paper (arXiv:0706.2049v2) Cotterill stumbled across the following remarkable formulas  where k = Σ_i e_i. In this talk, we first construct a bijection from (unrooted) trees to rooted trees which preserves the indegree sequence. As a consequence, we obtain a bijective proof of the formula. This is a joint work with Jiang Zeng.