On pattern-avoiding partitions

zbMATH Open1179.05014arXivmath/0703898MaRDI QIDQ1010749FDOQ1010749

Authors: Vít Jelínek, Toufik Mansour 

Publication date: 7 April 2009

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

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.

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

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

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

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)

Cited In (40)

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

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)