Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA decomposition of ballot permutations, pattern avoidance and Gessel walks
174
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A permutation whose any prefix has no more descents than ascents is called a ballot permutation. In this paper, we present a decomposition of ballot permutations that enables us to construct a bijection between ballot permutations and odd order permutations, which proves a set-valued extension of a conjecture due to Spiro using the statistic of peak values. This bijection also preserves the neighbors of the largest letter in permutations and thus resolves a refinement of Spiro s conjecture proposed by Wang and Zhang. Our decomposition can be extended to well-labelled positive paths, a class of generalized ballot permutations arising from polytope theory, that were enumerated by Bernardi, Duplantier and Nadeau. We will also investigate the enumerative aspect of ballot permutations avoiding a single pattern of length 3 and establish a connection between 213-avoiding ballot permutations and Gessel walks.
rate research
Read More
We introduce a new boundedness condition for affine permutations, motivated by the fruitful concept of periodic boundary conditions in statistical physics. We study pattern avoidance in bounded affine permutations. In particular, we show that if $tau$ is one of the finite increasing oscillations, then every $tau$-avoiding affine permutation satisfies the boundedness condition. We also explore the enumeration of pattern-avoiding affine permutations that can be decomposed into blocks, using analytic methods to relate their exact and asymptotic enumeration to that of the underlying ordinary permutations. Finally, we perform exact and asymptotic enumeration of the set of all bounded affine permutations of size $n$. A companion paper will focus on avoidance of monotone decreasing patterns in bounded affine permutations.
A ballot permutation is a permutation {pi} such that in any prefix of {pi} the descent number is not more than the ascent number. In this article, we obtained a formula in close form for the multivariate generating function of {A(n,d,j)}, which denote the number of permutations of length n with d descents and j as the first letter. Besides, by a series of calculations with generatingfunctionology, we confirm a recent conjecture of Wang and Zhang for ballot permutations.
A ballot permutation is a permutation $pi$ such that in any prefix of $pi$ the descent number is not more than the ascent number. By using a reversal concatenation map, we give a formula for the joint distribution (pk, des) of the peak and descent statistics over ballot permutations, and connect this distribution and the joint distribution (pk, dp, des) of the peak, depth, and descent statistics over ordinary permutations in terms of generating functions. As corollaries, we obtain several formulas for the bivariate generating function for (i) the peak statistic over ballot permutations,(ii) the descent statistic over ballot permutations, and (iii) the depth statistic over ordinary permutations. In particular, we confirm Spiros conjecture which finds the equidistribution of the descent statistic for ballot permutations and an analogue of the descent statistic for odd order permutations.
Given a set of permutations Pi, let S_n(Pi) denote the set of permutations in the symmetric group S_n that avoid every element of Pi in the sense of pattern avoidance. Given a subset S of {1,...,n-1}, let F_S be the fundamental quasisymmetric function indexed by S. Our object of study is the generating function Q_n(Pi) = sum F_{Des sigma} where the sum is over all sigma in S_n(Pi) and Des sigma is the descent set of sigma. We characterize those Pi contained in S_3 such that Q_n(Pi) is symmetric or Schur nonnegative for all n. In the process, we show how each of the resulting Pi can be obtained from a theorem or conjecture involving more general sets of patterns. In particular, we prove results concerning symmetries, shuffles, and Knuth classes, as well as pointing out a relationship with the arc permutations of Elizalde and Roichman. Various conjectures and questions are mentioned throughout.
Jelinek, Mansour, and Shattuck studied Wilf-equivalence among pairs of patterns of the form ${sigma,tau}$ where $sigma$ is a set partition of size $3$ with at least two blocks. They obtained an upper bound for the number of Wilf-equivalence classes for such pairs. We show that their upper bound is the exact number of equivalence classes, thus solving a problem posed by them.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
