Counting labelled trees with given indegree sequence

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:117

Article

Du, Rosena R. X.¹  Yin, Jingbin² 

[1] E China Normal Univ, Dept Math, Shanghai 200241, Peoples R China

[2] MIT, Dept Math, Cambridge, MA 02139 USA

关键词: Labelled tree;    Indegree sequence;    Partition;    Bijection;    Lattice;   

DOI  :  10.1016/j.jcta.2009.03.020

来源: Elsevier

【 摘 要 】

For a labelled tree oil the vertex set [n] := {1,2,..., n), define the direction of each edge ij to be i -> j if i < j. The indegree sequence Of T can be considered as a partition lambda proves n - 1. The enumeration of trees with a given indegree sequence arises in counting secant planes Of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on [n] with indegree sequence corresponding to a partition lambda. In this paper we give two proofs of Cotterill's conjecture: one is semi- combinatorial based oil induction. the other is a bijective proof. (C) 2009 Elsevier Inc. All rights reserved

【 授权许可】

Free