On pattern-avoiding partitions

MaRDI QIDQ1010749zbMATH OpenFDO

Authors Vít Jelínek, Toufik Mansour

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703898, https://eudml.org/doc/117229, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r39.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Catalan numbersset partitionStirling numbersnon crossing partitionsnon nesting partitions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial aspects of representation theory (05E10) Combinatorial aspects of partitions of integers (05A17) Combinatorial identities, bijective combinatorics (05A19)

Abstract: A emph{set partition} of the set $[n]=1,\mathrm{...}c,n$ is a collection of disjoint blocks $B_1,B_2,\mathrm{...}c,B_d$ whose union is $[n]$. We choose the ordering of the blocks so that they satisfy $min{B}_1<min{B}_2<\mathrm{...}b<min{B}_d$. We represent such a set partition by a emph{canonical sequence} $p{i}_1,p{i}_2,\mathrm{...}c,p{i}_n$, with $p{i}_i=j$ if $iin{B}_j$. We say that a partition $pi$ emph{contains} a partition $sigma$ if the canonical sequence of $pi$ contains a subsequence that is order-isomorphic to the canonical sequence of $sigma$. Two partitions $sigma$ and $sigm{a}^{\prime }$ are emph{equivalent}, if there is a size-preserving bijection between $sigma$-avoiding and $sigm{a}^{\prime }$-avoiding partitions. We determine several infinite families of sets of equivalent patterns; for instance, we prove that there is a bijection between $k$-noncrossing and $k$-nonnesting partitions, with a notion of crossing and nesting based on the canonical sequence. We also provide new combinatorial interpretations of the Catalan numbers and the Stirling numbers. Using a systematic computer search, we verify that our results characterize all the pairs of equivalent partitions of size at most seven. We also present a correspondence between set partitions and fillings of Ferrers shapes and stack polyominoes. This correspondence allows us to apply recent results on polyomino fillings in the study of partitions, and conversely, some of our results on partitions imply new results on polyomino fillings and ordered graphs.

Recommendations

• Pattern avoidance in matchings and partitions
• On multiple pattern avoiding set partitions
• Pattern avoidance in ordered set partitions
• Pattern avoidance in set partitions.
• Pattern avoidance for set partitions à la Klazar
• Partitions and partial matchings avoiding neighbor patterns
• On pattern avoiding flattened set partitions
• Pattern avoidance in ``flattened partitions
• Pattern-avoiding set partitions and Catalan numbers
• Pattern avoiding partitions and Motzkin left factors

Cited in

(40)

• Set partitions avoid a four-letter pattern
• On pattern avoiding flattened set partitions
• Embedding dualities for set partitions and for relational structures
• Visibility in non-crossing and non-nesting partitions
• On multiple pattern avoiding set partitions
• Pattern avoidance in ordered set partitions
• Some enumerative results related to ascent sequences
• Transport of patterns by Burge transpose
• Ordered partitions avoiding a permutation pattern of length 3
• Combinatorial generation via permutation languages. VI: Binary trees
• Pattern avoiding partitions, sequence A054391, and the kernel method
• Counting ordered graphs that avoid certain subgraphs
• Restricted partitions and \(q\)-Pell numbers
• Enumeration of \((k,2)\)-noncrossing partitions
• Counting pattern-avoiding integer partitions
• Pattern-avoiding set partitions and Catalan numbers
• Schröder paths and pattern avoiding partitions
• Pattern avoidance in matchings and partitions
• Set partitions with circular successions
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Block-connected set partitions
• Pattern avoidance in ``flattened partitions
• Avoidance of partitions of a three-element set
• Left-right arrangements, set partitions and pattern avoidance
• Avoiding colored partitions of two elements in the pattern sense
• Free rises, restricted partitions, and \(q\)-Fibonacci polynomials
• Front representation of set partitions
• The sets of flattened partitions with forbidden patterns
• Pattern avoiding partitions and Motzkin left factors
• Partitions of \(n\) that avoid partitions of \(f\), and an application to the tiny-pan coin weighing problem
• Set partition patterns and the dimension index
• Set partition patterns and statistics
• An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences
• Inversion sequences avoiding a triple of patterns of 3 letters
• Fillings of skew shapes avoiding diagonal patterns
• Pattern avoidance for set partitions à la Klazar
• Avoiding colored partitions of lengths two and three
• Avoiding a pair of patterns in multisets and compositions
• Catalan numbers and pattern restricted set partitions
• Restricted growth function patterns and statistics

This page was built for publication: On pattern-avoiding partitions

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