A pattern in a permutation π is a sub-permutation of π, and this paper deals mainly with length three patterns. In 2012 B´ona showed the rather surprising fact that the cumulative number of occurrences of the patterns 231 and 213 are the same on the set of permutations avoiding 132, even though the pattern based statistics 231 and 213 do not have the same distribution on this set. Here we show that if it is required for the symbols playing the role of 1 and 3 in the occurrences of 231 and 213 to be adjacent, then the obtained statistics are equidistributed on the set of 132-avoiding permutations. Actually, expressed in terms of vincular patterns, we prove bijectively the following more general results: the statistics based on the patterns 2 3 1, 2 1 3 and 2 1 3, together with other statistics, have the same joint distribution on Sn(132) of length n permutations avoiding 132, and so do the patterns 2 3 1 and 3 1 2; and up to trivial transformations, these statistics are the only based on lengththree proper (not classical nor consecutive) vincular patterns which are equidistributed on a set of permutations avoiding a classical length-three pattern.
In [
Vincular patterns, introduced by Babson and Steingr´ımsson [
In this paper we show that, on the set of 132-avoiding permutations, the vincular pattern based statistics 231, 213 and 213 are equidistributed, and so are 231 and 312; and numerical evidence shows that, up to trivial transformations, these patterns are the only length-three proper (not classical nor consecutive) vincular patterns equidistributed on a set of permutations avoiding a classical length-three pattern.
It is worth to mention that, on the set of unrestricted permutations, the statistics 231 and 312 are trivially equidistributed, and so are 231 and 213 (which is all but obvious on 132-avoiding permutations), and this last distribution is different from that of 213.
More precisely, in this paper we show bijectively the equidistribution on 132avoiding permutations of the tuples of statistics – (231, 213, rlmin, rlmax) and (213, 231, rlmax, rlmin), – (231, des) and (213, des), – (213, des, 12 ) and (213, des, 12 ), – (231, 312, des) and (312, 231, des), where rlmax, rlmin and des are respectively, the number of right-to-left maxima, right-to-left minima and descents. The corresponding bijections (the last of them being straightforward) are presented in Section 3. 2
A permutation of length n is a bijection from the set {1, 2, . . . , n} to itself and we write permutations in one-line notation, that is, as words π = π1π2 . . . πn, where πi is the image of i under π. We let Sn denote the set of permutations of length n. 2.1
Permutation patterns Let σ ∈ Sk and π = π1π2 . . . πn ∈ Sn, k ≤ n, be two permutations. One says that σ occurs as a (classical) pattern in π if there is a sequence 1 ≤ i1 < i2 < · · · < ik ≤ n such that πi1 πi2 · · · πik is order-isomorphic with σ. For example, 231 occurs as a pattern in 13452, and the three occurrences of it are 342, 352 and 452.
Vincular patterns were introduced in [
We denote by Sn(σ) the set of permutations in Sn avoiding the pattern σ. 2.2
Statistics A statistic on a set of permutations is simply a function from the set to N. A classical example of statistic on Sn is the descent number
des π = card {i : 1 ≤ i < n, πi > πi+1}, for example des 45312 = 2.
In a permutation π = π1π2 . . . πn, πi is a right-to-left maximum if πi > πj for all j > i; and the number of right-to-left maxima of π is denoted by rlmax π. Similarly, πi is a right-to-left minimum if πi < πj for all j > i; and the number of right-to-left minima of π is denoted by rlmin π. Both, rlmax and rlmin are statistics on Sn.
For a set of permutations S, two statistics ST and ST′ have the same distribution (or are equidistributed) on S if, for any k,
card{π ∈ S : ST π = k} = card{π ∈ S : ST′ π = k}, and the tuples of statistics, or multistatistics, (ST1, ST2, . . . , STp) and (ST′1, ST′2, . . . , ST′p) have the same distribution if, for any p-tuple k = (k1, k2, . . . , kp), card{π ∈ S : (ST1, ST2, . . . , STp) π = k} = card{π ∈ S : (ST′1, ST′2, . . . , ST′p) π = k}.
For a permutation π and a (vincular) patterns σ we denote by (σ) π the number of occurrences of this pattern in π, and (σ) becomes a permutation statistic. For example, (21) π is des π; (21) π is the inverse number of π; and (12 )π is the last value of π minus one. Similarly, for a set of (vincular) patterns {σ, τ, . . .}, we denote by (σ+τ +· · ·) π the number of occurrences of these patterns in π.
Our main results are stated in the following theorems.
Theorem 1 There is a bijection φ from Sn(132) to itself such that if π ∈ Sn(132), then
(213, 231, rlmin, rlmax) φ(π) = (231, 213, rlmax, rlmin) π.
Theorem 2 There is a bijection ψ from Sn(132) to itself such that if π ∈ Sn(132), then
(213, des) ψ(π) = (231, des) π.
Theorem 3 There is a bijection μ from Sn(132) to itself such that if π ∈ Sn(132), then
(213, des, 12 ) μ(π) = (213, des, 12 ) π.
Theorem 4 If π ∈ Sn(132), then (231, 312, des) π−1 = (312, 231, des) π.
All our bijections are constructive and based essentially on the recursive decomposition of 132-avding permutations.
α n s (1) β α (2) β s πn π= α s → φ(β) φ(α)
s =φ(π) β (3) We showed bijectively the joint equidistribution on the set Sn(132) of 132avoiding permutations of some length-three vincular patterns together with other statistics. In particular, for the sets of vincular patterns {231, 213, 213} and {231, 312}, we showed that the patterns within each set are equidistributed on Sn(132). By applying permutation symmetries, other similar results can be derived. For instance, from the equidistribution of 213 and 213 on Sn(132) (belonging to the first set, see Subsection 3.3) it follows, by applying – the reverse operation, the equidistribution of 312 and 312 on Sn(231), – the complement operation, the equidistribution of 231 and 231 on Sn(312), and – the complement and the reverse operations (in any order), the equidistribution of 132 and 132 on Sn(213).
Moreover, computer experiments show that, up to these two symmetries, the patterns in {231, 213, 213} and those in {231, 312} are the only length-three proper (not classical nor consecutive) vincular patterns which are equidistributed on a set of permutations avoiding a classical length-three pattern.