A bijective enumeration of labeled trees with given indegree sequence

Abstract

For a labeled tree on the vertex set $\{1,2,\dots ,n\}$, the local direction of each edge $(ij)$ is from $i$ to $j$ if $i<j$. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence $\lambda =1^{e_1}{2}^{e_2}\dots$ of a tree on the vertex set $\{1,2,\dots ,n\}$ is a partition of $n-1$. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a $q$-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.

16 pages, 6 figures; Changed title and content

Cited by in corpus (2)

• A recursive algorithm for trees and forests
• Labeled trees, maps, and an algebraic identity