Impulse parameter and a new equivalence between 123- and 132-avoiding permutations
Impulse parameter and a new equivalence between 123- and 132-avoiding permutations
In this paper, we enumerate permutations π=π1π2⋯πnaccording to the number of indices i such that πi−1<ℓ≤π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.