A bijective enumeration of labeled trees with given indegree sequence

DOI10.1016/J.JCTA.2010.07.001zbMATH Open1225.05083arXiv0805.0067OpenAlexW2950703920WikidataQ114162745 ScholiaQ114162745MaRDI QIDQ616443FDOQ616443

Authors: Heesung Shin, Jiang Zeng 

Publication date: 7 January 2011

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A trinomial analogue of Bailey's lemma and \(N=2\) superconformal invariance
• Geometry of curves with exceptional secant planes: Linear series along the general curve
• Title not available (Why is that?)
• Counting labelled trees with given indegree sequence
• Factorizations of some weighted spanning tree enumerators
• Spanning trees and function classes
• Hall--Littlewood functions and the A\(_2\) Rogers--Ramanujan identities

Cited In (13)

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

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)