Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length nn that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length kk. In several interesting cases the generating function depends only on kk and is expressed via the generating function for the Padovan numbers.