Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn $underline{12}0$-avoiding inversion and ascent sequences
135
0
0.0
(
0
)
Added by
Shishuo Fu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Recently, Yan and the first named author investigated systematically the enumeration of inversion or ascent sequences avoiding vincular patterns of length $3$, where two of the three letters are required to be adjacent. They established many connections with familiar combinatorial families and proposed several interesting conjectures. The objective of this paper is to address two of their conjectures concerning the enumeration of $underline{12}0$-avoiding inversion or ascent sequences.
rate research
Read More
As shown by Bousquet-Melou--Claesson--Dukes--Kitaev (2010), ascent sequences can be used to encode $({bf2+2})$-free posets. It is known that ascent sequences are enumerated by the Fishburn numbers, which appear as the coefficients of the formal power series $$sum_{m=1}^{infty}prod_{i=1}^m (1-(1-t)^i).$$ In this paper, we present a novel way to recursively decompose ascent sequences, which leads to: (i) a calculation of the Euler--Stirling distribution on ascent sequences, including the numbers of ascents ($asc$), repeated entries $(rep)$, zeros ($zero$) and maximal entries ($max$). In particular, this confirms and extends Dukes and Parviainens conjecture on the equidistribution of $zero$ and $max$. (ii) a far-reaching generalization of the generating function formula for $(asc,zero)$ due to Jelinek. This is accomplished via a bijective proof of the quadruple equidistribution of $(asc,rep,zero,max)$ and $(rep,asc,rmin,zero)$, where $rmin$ denotes the right-to-left minima statistic of ascent sequences. (iii) an extension of a conjecture posed by Levande, which asserts that the pair $(asc,zero)$ on ascent sequences has the same distribution as the pair $(rep,max)$ on $({bf2-1})$-avoiding inversion sequences. This is achieved via a decomposition of $({bf2-1})$-avoiding inversion sequences parallel to that of ascent sequences. This work is motivated by a double Eulerian equidistribution of Foata (1977) and a tempting bi-symmetry conjecture, which asserts that the quadruples $(asc,rep,zero,max)$ and $(rep,asc,max,zero)$ are equidistributed on ascent sequences.
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.
This addendum contains results about the inversion number and major index polynomials for permutations avoiding 321 which did not fit well into the original paper. In particular, we consider symmetry, unimodality, behavior modulo 2, and signed enumeration.
Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$. The inversion number of $D$, denoted by ${rm inv}(D)$, is the minimum number of
Given a set of integers with no three in arithmetic progression, we construct a Stanley sequence by adding integers greedily so that no arithmetic progression is formed. This paper offers two main contributions to the theory of Stanley sequences. First, we characterize well-structured Stanley sequences as solutions to constraints in modular arithmetic, defining the modular Stanley sequences. Second, we introduce the basic Stanley sequences, where elements arise as the sums of subsets of a basis sequence, which in the simplest case is the powers of 3. Applications of our results include the construction of Stanley sequences with arbitrarily large gaps between terms, answering a weak version of a problem by ErdH{o}s et al. Finally, we generalize many results about Stanley sequences to $p$-free sequences, where $p$ is any odd prime.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
