***** KAIST Discete Math Semianr *****

DATE: August 21, Thursday

TIME: 4PM-5PM

PLACE: E6-1, ROOM 1409

SPEAKER: Heesung Shin (신희성),  Université Claude Bernard Lyon 1, France.


TITLE: Counting labelled trees with given indegree sequence


For a labeled tree on the vertex set $[n]:=\set{1,2,\ldots,n}$, define the direction of each edge $ij$ as $i \to j$ if $i<j$.
The indegree sequence $\lambda = 1^{e_1}2^{e_2} \ldots$ is then a partition of $n-1$.
Let $a_{\lambda}$ be the number of trees on $[n]$ with indegree sequence $\lambda$.
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 = \sum_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.
    ----------------------------------------------
Informations on future talks can be found at :
http://mathsci.kaist.ac.kr/~sangil/seminar/

Please email to sangil (at) kaist.edu if you wish to receive this
announcements in the future by email.