Heesung Shin (신희성), Counting labelled trees with given indegree sequence

Counting labelled trees with given indegree sequence
Heesung Shin (신희성)
Institut Camille Jordan, Université Claude Bernard Lyon 1, France.
2008/08/21 Thu, 4PM-5PM

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 λ=1e12e2 … 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 ei. 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:

Comments are closed.