Nhảy đến nội dung

Impulse parameter and a new equivalence between 123- and 132-avoiding permutations


Toufik Mansour, Mark Shattuck*

Source title: 
Discrete Mathematics, Algorithms and Applications, 10(4), 1850054 (24 pages), 2018 (Scopus)
Academic year of acceptance: 

In this paper, we enumerate permutations π=π1π2πnaccording to the number of indices i such that πi1<≤πi, where π0=0 and ℓ is a fixed positive integer. We term such an index i an -impulse since it marks an occurrence where the bargraph representation of π rises above (or to the same level as) the horizontal line y=. We find an explicit formula for the distribution as well as a formula for the total number of -impulses in all permutations of [n]. Comparable distributions are also found for the τ-avoiding permutations of [n], where τ is a pattern of length three. Two markedly different distributions emerge, one for {213,312} and another for the remaining patterns in S3. In particular, we obtain a new equidistribution result between 123- and 132-avoiding permutations. To prove our results, we make use of multiple arrays and systems of functional equations, employing the kernel method to solve the system in the case τ=123. We also provide a combinatorial proof of the aforementioned equidistribution result, which actually applies to a more general class of multi-set permutations.