On pattern-avoiding partitions

Details On pattern-avoiding partitions On pattern-avoiding partitions

2007-03-29

arxiv.org/abs/math/0703898v1

Mathematics

Combinatorics

53 pages; 5 tables; 3 figures

Scientific paper

A \emph{set partition} of the set $[n]=\{1,...c,n\}$ is a collection of disjoint blocks $B_1,B_2,...c, B_d$ whose union is $[n]$. We choose the ordering of the blocks so that they satisfy $\min B_1<\min B_2<...b<\min B_d$. We represent such a set partition by a \emph{canonical sequence} $\pi_1,\pi_2,...c,\pi_n$, with $\pi_i=j$ if $i\in 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 $\sigma'$ are \emph{equivalent}, if there is a size-preserving bijection between $\sigma$-avoiding and $\sigma'$-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.

Affiliated with

Also associated with

No associations

Rating

On pattern-avoiding partitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On pattern-avoiding partitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On pattern-avoiding partitions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-711286