On trees and noncrossing partitions

被引：11
作者：
Klazar, M [1 ]
机构：
[1] Charles Univ, Dept Appl Math, CR-11800 Praha 1, Czech Republic
来源：
DISCRETE APPLIED MATHEMATICS | 1998年 / 82卷 / 1-3期
关键词：
noncrossing partition; enumeration; tree; bijection;
D O I：
10.1016/S0166-218X(97)00118-2
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We give a simple and natural proof of (an extension of) the identity P(k, l, n) = P-2(k - 1, l - 1, n - 1). The number P(k, l, n) counts noncrossing partitions of {1,2,..., l} into n parts such that no part contains two numbers x and y, 0 < y - x < k. The lower index 2 indicates partitions with no part of size three or more. We use the identity to give quick proofs of the closed formulae for P(k, l, n) when k is 1, 2, or 3. (C) 1998 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：263 / 269
页数：7
相关论文
共 50 条
[21]   Noncrossing partitions with fixed points having specific properties [J].
Huang, Yufei ;
Liu, Bolian .
ARS COMBINATORIA, 2015, 118 :51-61
[22]   Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups Introduction [J].
Armstrong, Drew .
MEMOIRS OF THE AMERICAN MATHEMATICAL SOCIETY, 2009, 202 (949) :1-+
[23]   Gray codes for noncrossing and nonnesting partitions of classical types [J].
Conflitti, Alessandro ;
Mamede, Ricardo .
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2017, 27 (05) :455-475
[24]   Bicoloured ordered trees, non-nesting partitions and non-crossing partitions [J].
Liu, Chunlin ;
Li, Baodi .
ARS COMBINATORIA, 2016, 124 :401-408
[25]   Oriented flip graphs of polygonal subdivisions and noncrossing tree partitions [J].
Garver, Alexander ;
McConville, Thomas .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2018, 158 :126-175
[26]   Bijections between noncrossing and nonnesting partitions for classical reflection groups [J].
Fink, Alex ;
Iriarte Giraldo, Benjamin .
PORTUGALIAE MATHEMATICA, 2010, 67 (03) :369-401
[27]   A BIJECTION BETWEEN NONCROSSING AND NONNESTING PARTITIONS OF TYPES A, B AND C [J].
Mamede, Ricardo .
CONTRIBUTIONS TO DISCRETE MATHEMATICS, 2011, 6 (02) :70-90
[28]   Bijections between bicoloured ordered trees and non-crossing partitions [J].
Liu, Chunlin ;
Wang, Zhenghua ;
Li, Baodi .
ARS COMBINATORIA, 2014, 117 :155-162
[29]   BOUNDARY PARTITIONS IN TREES AND DIMERS [J].
Kenyon, Richard W. ;
Wilson, David B. .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2011, 363 (03) :1325-1364
[30]   Partitions of Vertices and Facets in Trees and Stacked Simplicial Complexes [J].
Floystad, Gunnar .
GRAPHS AND COMBINATORICS, 2024, 40 (04)
12345