# A bijective enumeration of labeled trees with given indegree sequence

Heesung Shin and Jiang Zeng

Arxiv ID: 0805.0067•Last updated: 3/22/2022

For a labeled tree on the vertex set $\set{1,2,\ldots,n}$, the local
direction of each edge $(i\,j)$ 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} \ldots$ of a tree on the
vertex set $\set{1,2,\ldots,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\"ufer-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.

#### PaperStudio AI Chat

I'm your research assistant! Ask me anything about this paper.