Counting labelled trees with given indegree sequence
Counting labelled trees with given indegree sequence
复制标题
计算具有给定入度序列的标记树
DOI：
10.1016/j.jcta.2009.03.020
复制
发表时间：
2007-12
影响因子：
1.1
通讯作者：
Du, Rosena R. X.
中科院分区：
文献类型：
--
作者：
Yin, Jingbin;Du, Rosena R. X.
对于顶点集[n]上的标号树：={1，2，…，n}，定义每个边ij的方向为i→j，如果i&j，则T的赋值序列可被认为是一个划分λ⊢n−1.具有给定赋标序列的树的计数产生于计算射影空间中曲线的割面.最近，Ethan Cotterill猜想了[n]上索引序列对应于划分λ的树的个数的公式。本文给出了Cotterill猜想的两种证明：一种是基于归纳的“半组合”证明，另一种是双射证明。
For a labelled tree on 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 λ⊢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 λ. In this paper we give two proofs of Cotterill's conjecture: one is “semi-combinatorial” based on induction, the other is a bijective proof.
DOI：
10.1057/jors.1977.45
发表时间：
1978-03
期刊：
--
影响因子：
--
作者：
E. Lloyd;J. Bondy;U. Murty
通讯作者：
E. Lloyd;J. Bondy;U. Murty
DOI：
--
发表时间：
2007-06
期刊：
--
影响因子：
--
作者：
Ethan Cotterill
通讯作者：
Ethan Cotterill