Enumerating (2 + 2)-free posets by indistinguishable elements

DOI10.4310/JOC.2011.V2.N1.A6zbMATH Open1245.06003arXiv1006.2696OpenAlexW2036440872WikidataQ60692803 ScholiaQ60692803MaRDI QIDQ635860FDOQ635860

Authors: Mark Dukes, Sergey Kitaev, Einar Steingrímsson, Jeffrey Remmel 

Publication date: 23 August 2011

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. Two elements in a poset are indistinguishable if they have the same strict up-set and the same strict down-set. Being indistinguishable defines an equivalence relation on the elements of the poset. We introduce the statistic maxindist, the maximum size of a set of indistinguishable elements. We show that, under a bijection of Bousquet-Melou et al., indistinguishable elements correspond to letters that belong to the same run in the so-called ascent sequence corresponding to the poset. We derive the generating function for the number of (2+2)-free posets with respect to both maxindist and the number of different strict down-sets of elements in the poset. Moreover, we show that (2+2)-free posets P with maxindist(P) at most k are in bijection with upper triangular matrices of nonnegative integers not exceeding k, where each row and each column contains a nonzero entry. (Here we consider isomorphic posets to be equal.) In particular, (2+2)-free posets P on n elements with maxindist(P)=1 correspond to upper triangular binary matrices where each row and column contains a nonzero entry, and whose entries sum to n. We derive a generating function counting such matrices, which confirms a conjecture of Jovovic, and we refine the generating function to count upper triangular matrices consisting of nonnegative integers not exceeding k and having a nonzero entry in each row and column. That refined generating function also enumerates (2+2)-free posets according to maxindist. Finally, we link our enumerative results to certain restricted permutations and matrices.

Full work available at URL: https://arxiv.org/abs/1006.2696

Recommendations

• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• On a conjecture about enumerating \((2+2)\)-free posets
• scientific article; zbMATH DE number 6806834
• Composition matrices, \((2+2)\)-free posets and their specializations
• (2+2)-free posets, ascent sequences and pattern avoiding permutations

zbMATH Keywords

enumerationinterval order\((2+2)\)-free posetupper triangular matrixindistinguishable elements

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07)

Cited In (28)

• Some enumerative results related to ascent sequences
• Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
• Title not available (Why is that?)
• On \(\underline{12} 0\)-avoiding inversion and ascent sequences
• Web worlds, web-colouring matrices, and web-mixing matrices
• Ascent sequences avoiding pairs of patterns
• On \(q\)-series identities related to interval orders
• A new decomposition of ascent sequences and Euler-Stirling statistics
• Fishburn trees
• Proof of a bi-symmetric septuple equidistribution on ascent sequences
• Modified ascent sequences and Bell numbers
• Title not available (Why is that?)
• Refining the bijections among ascent sequences, \((2+2)\)-free posets, integer matrices and pattern-avoiding permutations
• Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
• Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers
• Symmetric generating functions and Euler-Stirling statistics on permutations
• Bi-symmetric multiple equidistributions on ascent sequences
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Catalan pairs and Fishburn triples
• Asymptotics for the number of row-Fishburn matrices
• The combinatorics of Jeff Remmel
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• Restricted non-separable planar maps and some pattern avoiding permutations
• Hereditary semiorders and enumeration of semiorders by dimension
• Asymptotics and statistics on Fishburn matrices and their generalizations
• Transport of patterns by Burge transpose
• Partition and composition matrices
• Composition matrices, \((2+2)\)-free posets and their specializations

Uses Software

• OEIS

This page was built for publication: Enumerating \((2 + 2)\)-free posets by indistinguishable elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q635860)