Permutations and Pairs of Dyck Paths

We define a map between the symmetric group and the set of pairs of Dyck paths of semilength . We show that the map is injective when restricted to the set of 1234-avoiding permutations and characterize the image of this map. 1. Introduction We say that a permutation contains a pattern if contains a subsequence that is order-isomorphic to . Otherwise, we say that avoids . Given a pattern , denote by the set of permutations in avoiding . The sets of permutations that avoid a single pattern have been completely determined in last decades. More precisely, it has been shown [1] that, for every , the cardinality of the set equals the th Catalan number, which is also the number of Dyck paths of semilength (see [2] for an exhaustive survey). Many bijections between , , and the set of Dyck paths of semilength have been described (see [3] for a fully detailed overview). The case of patterns of length appears much more complicated, due both to the fact that the patterns are not equidistributed on , and the difficulty of describing bijections between , , and some set of combinatorial objects. In this paper we study the case . An explicit formula for the cardinality of has been computed by I. Gessel (see [2, 4]). We present a bijection between and a set of pairs of Dyck paths of semilength . More specifically, we define a map from to the set of pairs of Dyck paths, prove that every element in the image of corresponds to a single element in , and characterize the set of all pairs that belong to the image of the map . 2. Dyck Paths A Dyck path of semilength is a lattice path starting at , ending at , and never going below the -axis, consisting of up steps and down steps . A return of a Dyck path is a down step ending on the -axis. A Dyck path is irreducible if it has only one return. An irreducible component of a Dyck path is a maximal irreducible Dyck subpath of . A Dyck path is specified by the lengths of its ascents (viz., maximal sequences of consecutive up steps) and by the lengths of its descents (maximal sequences of consecutive down steps), read from left to right. Set and . If is the semilength of , we have of course , hence the Dyck path is uniquely determined by the two sequences and . The pair is called the ascent-descent code of the Dyck path . Obviously, a pair , where and , is the ascent-descent code of some Dyck path of semilength if and only if (i) ; (ii) ; (iii) ; (iv) for every . It is easy to check that the returns of a Dyck path are in one-to-one correspondence with the indices such that . Hence, a Dyck path is irreducible whenever we have for