=Paper=
{{Paper
|id=Vol-1949/AUXICTCSpaper11
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1949/AUXICTCSpaper11.pdf
|volume=Vol-1949
}}
==None==
https://ceur-ws.org/Vol-1949/AUXICTCSpaper11.pdf
The equidistribution of some vincular patterns
on 132-avoiding permutations
Vincent Vajnovszki
LE2I, Université Bourgogne Franche-Comté
Dijon, France
vvajnov@u-bourgogne.fr
Abstract. A pattern in a permutation π is a sub-permutation of π, and
this paper deals mainly with length three patterns. In 2012 Bóna 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 length-
three proper (not classical nor consecutive) vincular patterns which are
equidistributed on a set of permutations avoiding a classical length-three
pattern.
1 Introduction
In [2] Barnabei, Bonetti and Silimbani showed the equidistribution of some
length-three consecutive patterns involvement statistics on the set of permu-
tations avoiding the classical pattern 312 (or equivalently, 132), and in [4] Bóna
showed the surprising fact that the total number of occurrences of the patterns
231 and 213 is the same on the set of 132-avoiding permutations, despite the pat-
tern based statistics 231 and 213 having different distribution on this set. In [6],
Homberger, generalizing Bóna’s result, gave the total number of occurrences of
each classical length-three pattern on the set of 123-avoiding permutations, and
showed that the total number of occurrences of the pattern 231 is the same in the
set of 123- and 132-avoiding permutations, despite the pattern based statistic
231 having different distribution on these two sets.
Vincular patterns, introduced by Babson and Steingrı́msson [1], are a gener-
alization of the notion of patterns where, for example, some entries are required
to occur consecutively, and in [8] Mansour considered permutations avoiding
132 and containing various length-three vincular patterns exactly 0 or 1 times.
Motivated by these, Burnstein and Elizalde gave in [5], in a much more general
context, the total number of occurrences of any vincular pattern of length three
on 231-avoiding (or equivalently, 132-avoiding) permutations, and more recently,
Baxter [3] gave algorithmic methods to efficiently compute several statistics over
some pattern-avoiding permutations.
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 distribu-
tion is different from that of 213.
More precisely, in this paper we show bijectively the equidistribution on 132-
avoiding 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 Notations and definitions
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 [1] and they were extensively studied
since then (see Chapter 7 in [7] for a comprehensive description of results on these
patterns). Vincular patterns generalize classical patterns and they are defined
as follows:
– Any pair of two adjacent letters may now be underlined, which means that
the corresponding letters in the permutation must be adjacent. (The original
notation for vincular patterns uses dashes: the absence of a dash between
two letters of a pattern means that these letters are adjacent in the permuta-
tion.) For example, the pattern 213 occurs in the permutation 425163 four
times, namely, as the subsequences 425, 416, 216 and 516. Note that, the
subsequences 426 and 213 are not occurrences of the pattern because their
last two letters are not adjacent in the permutation.
– If a pattern begins (resp., ends) with a hook then its occurrence is required
to begin (resp., end) with the leftmost (resp., rightmost) letter in the per-
mutation. (In the original notation the role of hooks was played by square
brackets.) For example, there are two occurrences of the pattern 213 in the
permutation 425163, which are the subsequences 425 and 416.
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 distri-
bution (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 π.
3 The main results
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
α α α
s φ(β)
s πn
β →
β π= s =φ(π)
β
φ(α)
(1) (2) (3)
Fig. 1. The decomposition: (1) π = (α ⊕ 1) ⊖ β, and (2) π = α ⊖ (β ⊕ 1) of π ∈ Sn (132),
n ≥ 1; and (3) the recursive definition of φ(π).
4 Conclusions
We showed bijectively the joint equidistribution on the set Sn (132) of 132-
avoiding 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) (be-
longing 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 equidistribu-
tion 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.
References
1. E. Babson, E. Steingrı́msson, Generalized permutation patterns and a classification
of Mahonian statistics, Séminaire Lotharingien de Combinatoire (electronic), 44
(2000), art. B44b.
2. M. Barnabei, F. Bonetti, M. Silimbani, The joint distribution of consecutive pat-
terns and descents in permutations avoiding 3-1-2. European Journal of Combina-
torics, 31(5) (2010), 1360–1371.
3. A. Baxter, Refining enumeration schemes to count according to permutation statis-
tics, Electronic Journal of Combinatorics, 21(2) (2014), #P2.50.
4. M. Bóna, Surprising symmetries in objects counted by Catalan numbers, Electronic
Journal of Combinatorics, 19(1) (2012), #P62.
5. A. Burstein, S. Elizalde, Total occurrence statistics on restricted permutations,
Pure Mathathematics and Applications, 24 (2013), 103–123.
6. C. Homberger, Expected patterns in permutation classes, Electronic Journal of
Combinatorics, 19(3) (2012), #P43.
7. S. Kitaev, Patterns in permutations and words, Springer-Verlag, 2011.
8. T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of
Combinatorics, 6 (2002), 65–76.
9. V. Vajnovszki, Lehmer code transforms and Mahonian statistics on permutations,
Discrete Mathematics, 313 (2013), 581–589.
10. V. Vajnovszki, A new Euler-Mahonian constructive bijection, Discrete Applied
Mathematics, 159 (2011), 1453–1459.