A Generating Tree for Permutations Avoiding the Pattern 122+3

In this paper we study the family of permutations avoiding the pattern 122+3 (trivially equivalent to those avoiding 1 23 4), which extend the popular 123-avoiding permutations. In particular we provide an algorithmic description of a generating tree for these permutations, that is a way to build every object of a given size n + 1 in a unique way by performing local modifications on an object of size n. Our algorithm leads to a direct bijection between 1 23 4-avoiding permutations and valley-marked Dyck paths. It extends a known bijection between 123-avoiding permutations and Dyck paths, and makes explicit the connection between these objects that was earlier obtained by Callan through a series of non-trivial bijective steps. In particular our construction is simple enough to allow for efficient exhaustive generation.