Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Pattern Avoiding Alternating Permutations
129
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
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.
The notion of a $p$-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a $p$-Riordan word, and show how to encode $p$-Riordan graphs by $p$-Riordan words. For special important cases of Riordan graphs (the case $p=2$) and oriented Riordan graphs (the case $p=3$) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube.
We prove a generalization of a conjecture of Dokos, Dwyer, Johnson, Sagan, and Selsor giving a recursion for the inversion polynomial of 321-avoiding permutations. We also answer a question they posed about finding a recursive formulas for the major index polynomial of 321-avoiding permutations. Other properties of these polynomials are investigated as well. Our tools include Dyck and 2-Motzkin paths, polyominoes, and continued fractions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
