Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three

We consider the problem of enumerating the permutations containing exactly <f>k</f> occurrences of a pattern of length 3. This enumeration has received a lot of interest recently, and there are a lot of known results. This paper presents an alternative approach to the problem, which yields a proof for a formula which so far only was conjectured (by Noonan and Zeilberger). This approach is based on bijections from permutations to certain lattice paths with “jumps,” which were first considered by Krattenthaler. [Copyright &y& Elsevier]