Catalan words avoiding pairs of length three patterns Baril, Jean-Luc; Khalil, Carine; Vajnovszki, Vincent
Discrete mathematics and theoretical computer science,
04/2021, Letnik:
22 no. 2, Permutation..., Številka:
Special issues
Journal Article
Recenzirano
Odprti dostop
Catalan words are particular growth-restricted words counted by the eponymous
integer sequence. In this article we consider Catalan words avoiding a pair of
patterns of length 3, pursuing the recent ...initiating work of the first and last
authors and of S. Kirgizov where (among other things) the enumeration of
Catalan words avoiding a patterns of length 3 is completed. More precisely, we
explore systematically the structural properties of the sets of words under
consideration and give enumerating results by means of recursive decomposition,
constructive bijections or bivariate generating functions with respect to the
length and descent number. Some of the obtained enumerating sequences are
known, and thus the corresponding results establish new combinatorial
interpretations for them.
In 2012 Bóna showed the rather surprising fact that the cumulative number of occurrences of the classical patterns 231 and 213 is 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 ▪, ▪ and ▪, together with other statistics, have the same joint distribution on Sn(132), and so do the patterns ▪ and ▪; 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.
In 2012 Bona showed the rather surprising fact that the cumulative number of occurrences of the classical patterns 231 and 213 is 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 (31) under bar, 2 (13) under bar and (21) under bar3, together with other statistics, have the same joint distribution on S-n(132), and so do the patterns (23) under bar1 and 3 (12) under bar; 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. (C) 2017 Elsevier B.V. All rights reserved.Keywords
Combinatorics
We show how the ECO method can be applied to exhaustively generate some classes of permutations. A previous work initiating this technique and motivating our research was published in ...Ac ta Informatica, 2004, by S. Bacchelli, E. Barcucci, E. Grazzini and E. Pergola.
In 2000 Babson and Steingrímsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations ...of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006.
In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections between subexcedant sequences) which when applied to the Lehmer code yield new permutation codes which count occurrences of some vincular patterns. These code transforms can be seen as a pre-compression step of the Lehmer code because they map some redundancies into runs of 0s. Also, our proofs, unlike the previous ones, provide explicit bijections between permutations having a given value for two different Mahonian pattern-based statistics.
A length n binary word is q-decreasing, q⩾1, if every of its maximal factors of the form 0a1b satisfies a=0 or q⋅a>b. In particular, in 1-decreasing words every run of 0s is immediately followed by a ...strictly shorter run of 1s. We show constructively that these words are in bijection with binary words having no occurrences of 1q+1, and thus they are enumerated by the (q+1)-generalized Fibonacci numbers. We give some enumerative results and reveal similarities between q-decreasing words and binary words having no occurrences of 1q+1 in terms of the frequency of 1-bits. In the second part of our paper, we provide an efficient exhaustive generating algorithm for q-decreasing words in lexicographic order, for any q⩾1, show the existence of 3-Gray codes and explain how a generating algorithm for these Gray codes can be obtained. Moreover, we give the construction of a more restrictive 1-Gray code for 1-decreasing words, which in particular settles a conjecture stated recently in the context of interconnection networks by Eğecioğlu and Iršič.
Gray code order for Lyndon words Vajnovszki, Vincent
Discrete mathematics and theoretical computer science,
01/2007, Letnik:
9 no. 2, Številka:
2
Journal Article
Recenzirano
Odprti dostop
At the 4th Conference on Combinatorics on Words, Christophe Reutenauer posed the question of whether the dual reflected order yields a Gray code on the Lyndon family. In this paper we give a positive ...answer. More precisely, we present an O(1)-average-time algorithm for generating length n binary pre-necklaces, necklaces and Lyndon words in Gray code order.
Using generating functions, MacMahon proved in 1916 the remarkable fact that the major index has the same distribution as the inversion number for multiset permutations, and in 1968 Foata gave a ...constructive bijection proving MacMahon’s result. Since then, many refinements have been derived, consisting of adding new constraints or new statistics.
Here we give a new simple constructive bijection between the set of permutations with a given number of inversions and those with a given major index. We introduce a new statistic,
mix
, related to the Lehmer code, and using our new bijection we show that the bistatistic
(
mix
,
INV
)
is Euler–Mahonian. Finally, we introduce the McMahon code for permutations which is the major-index counterpart of the Lehmer code and show that the two codes are related by a simple relation.
► We give a simple bijection between permutations with a given number of inversions and a given major index. ► A new statistic,
mix
, is introduced. ► We show that the bistatistic
(
mix
,
INV
)
is Euler–Mahonian. ► We introduce a McMahon code for permutations. ► This code is simply related to the Lehmer code.
In 2000, Babson and Steingrímsson generalized the notion of permutation patterns to the so-called vincular patterns, and they showed that many Mahonian statistics can be expressed as sums of vincular ...pattern occurrence statistics. STAT is one of such Mahonian statistics discovered by them. In 2016, Kitaev and the third author introduced a words analogue of STAT and proved a joint equidistribution result involving two sextuple statistics on the whole set of words with fixed length and alphabet. Moreover, their computer experiments hinted at a finer involution on R(w), the rearrangement class of a given word w. We construct such an involution in this paper, which yields a comparable joint equidistribution between two sextuple statistics over R(w). Our involution builds on Burstein’s involution and Foata–Schützenberger’s involution that utilizes the celebrated RSK algorithm.
PDF
