Enumeration of permutations containing a prescribed number of occurrences of a pattern of length 3
Abstract
Description
We consider the problem of enumerating the permutations containing exactly $k$ 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.
Fixed errors in equation (19) and in the paper's last equation
Fixed errors in equation (19) and in the paper's last equation