Generalized triangulations and diagonal-free subsets of stack polyrominoes

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:112

Article

Jonsson, J

关键词: enumeration;    polygon;    triangulation;    associahedron;    Catalan number;    Hankel determinant;   

DOI  :  10.1016/j.jcta.2005.01.009

来源: Elsevier

【 摘 要 】

For n >= 3, let Omega(n) be the set of line segments between vertices in a convex n-gon. For j >= 1, a j-crossing is a set of j distinct and mutually intersecting line segments from Q,, such that all 2j endpoints are distinct. For k >= 1, let Delta(n,k) be the simplicial complex of subsets of Omega(n) not containing any (k + 1)-crossing. For example, Delta(n.1) has one maximal set for each triangulation of the n-gon. Dress, Koolen, and Moulton were able to prove that all maximal sets in Delta(n,k) have the same number k(2n - 2k - 1) of line segments. We demonstrate that the number of such maximal sets is counted by a k x k determinant of Catalan numbers. By the work of Desainte-Catherine and Viennot, this determinant is known to count quite a few other objects including fans of non-crossing Dyck paths. We generalize our result to a larger class of simplicial complexes including some of the complexes appearing in the work of Herzog and Trung, on determinantal ideals. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free