Institut Camille Jordan, Université Claude Bernard Lyon 1, France.

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^{e1}2^{e2} … 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 \(a_\lambda = \dfrac{(n-1)!^2}{(n-k)! e_1! (1!)^{e_1} e_2! (2!)^{e_2} \ldots}\) 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.

Tags: 신희성