A bijective enumeration of labeled trees with given indegree sequence

DOI10.1016/J.JCTA.2010.07.001MaRDI QIDQ616443zbMATH OpenOpenAlexWikidataFDO

Authors Heesung Shin, Jiang Zeng

Publication date 7 January 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.0067

zbMATH Keywords

bijections\(q\)-binomial coefficientslabeled trees\(q\)-Chu-Vandermondeindegree sequencePrüfer-like code

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30)

Abstract: For a labeled tree on the vertex set $set1,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 $set1,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.

Recommendations

• Counting labelled trees with given indegree sequence
• Labeled trees, functions, and an algebraic identity
• scientific article; zbMATH DE number 4070934
• A new bijection on rooted forests
• scientific article; zbMATH DE number 1792594

Cites work

• scientific article; zbMATH DE number 4191636 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A trinomial analogue of Bailey's lemma and \(N=2\) superconformal invariance
• Counting labelled trees with given indegree sequence
• Factorizations of some weighted spanning tree enumerators
• Geometry of curves with exceptional secant planes: Linear series along the general curve
• Hall--Littlewood functions and the A\(_2\) Rogers--Ramanujan identities
• Spanning trees and function classes

Cited in

(13)

• Counting labelled trees with given indegree sequence
• A combinatorial approach for discrete car parking on random labelled trees
• Enumeration of binary trees compatible with a perfect phylogeny
• Locally oriented noncrossing trees
• A bijective enumeration of tiered trees
• A bijective proof of the Shor recurrence
• Effective divisors on \({\overline{\mathcal{M}}}_g\) associated to curves with exceptional secant planes
• A bijection from ordered trees to binary trees that sends the pruning order to the Strahler number
• A generalized enumeration of labeled trees and reverse Prüfer algorithm
• Bijections for a class of labeled plane trees
• scientific article; zbMATH DE number 1792594 (Why is no real title available?)
• A recursive algorithm for trees and forests
• Labeled trees, functions, and an algebraic identity

This page was built for publication: A bijective enumeration of labeled trees with given indegree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616443)