A bijective enumeration of labeled trees with given indegree sequence

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Shin, Heesung¹  Zeng, Jiang¹ 

[1] Univ Lyon 1, Univ Lyon, Inst Camille Jordan, CNRS,UMR 5208, F-69622 Villeurbanne, France

关键词: Bijections;    Labeled trees;    Indegree sequence;    Prufer-like code;    q-Binomial coefficients;    q-Chu-Vandermonde;   

DOI  :  10.1016/j.jcta.2010.07.001

来源: Elsevier

【 摘 要 】

For a labeled tree on the vertex set {1,2 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(e1)2(e2) of a tree on the vertex set {1 2 n} is a partition of n - 1 We construct a Injection 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 Prufer-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 (C) 2010 Elsevier Inc All rights reserved

【 授权许可】

Free