Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn pattern-avoiding partitions
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 $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 $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.
rate research
Read More
An alternating permutation of length $n$ is a permutation $pi=pi_1 pi_2 ... pi_n$ such that $pi_1 < pi_2 > pi_3 < pi_4 > ...$. Let $A_n$ denote set of alternating permutations of ${1,2,..., n}$, and let $A_n(sigma)$ be set of alternating permutations in $A_n$ that avoid a pattern $sigma$. Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$, $A_{2n}(2143)$ and $A_{2n+1}(2143)$, and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by Bona, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.
We introduce consecutive-pattern-avoiding stack-sorting maps $text{SC}_sigma$, which are natural generalizations of Wests stack-sorting map $s$ and natural analogues of the classical-pattern-avoiding stack-sorting maps $s_sigma$ recently introduced by Cerbai, Claesson, and Ferrari. We characterize the patterns $sigma$ such that $text{Sort}(text{SC}_sigma)$, the set of permutations that are sortable via the map $scirctext{SC}_sigma$, is a permutation class, and we enumerate the sets $text{Sort}(text{SC}_{sigma})$ for $sigmain{123,132,321}$. We also study the maps $text{SC}_sigma$ from a dynamical point of view, characterizing the periodic points of $text{SC}_sigma$ for all $sigmain S_3$ and computing $max_{piin S_n}|text{SC}_sigma^{-1}(pi)|$ for all $sigmain{132,213,231,312}$. In addition, we characterize the periodic points of the classical-pattern-avoiding stack-sorting map $s_{132}$, and we show that the maximum number of iterations of $s_{132}$ needed to send a permutation in $S_n$ to a periodic point is $n-1$. The paper ends with numerous open problems and conjectures.
A permutation $sigmainmathfrak{S}_n$ is simsun if for all $k$, the subword of $sigma$ restricted to ${1,...,k}$ does not have three consecutive decreasing elements. The permutation $sigma$ is double simsun if both $sigma$ and $sigma^{-1}$ are simsun. In this paper we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Recently, Amini investigated the equidistributions of these Mahonian statistics over sets of pattern avoiding permutations. Moreover, he posed several conjectures. In this paper, we construct a bijection from $S_n(213)$ to $S_n(231)$, which maps the statistic $(maj,stat)$ to the statistic $(stat,maj)$. This allows us to give solutions to some of Aminis conjectures.
In this note, we study the mean length of the longest increasing subsequence of a uniformly sampled involution that avoids the pattern $3412$ and another pattern.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
