Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials

Several authors have examined connections among 132-avoiding permutations, continued fractions, and Chebyshev polynomials of the second kind. In this paper we find analogues for some of these results for permutations ππ avoiding 132 and 1□231□23 (there is no occurrence πi<πj<πj+1πi<πj<πj+1 such that 1⩽i⩽j-21⩽i⩽j-2) and provide a combinatorial interpretation for such permutations in terms of lattice paths. Using tools developed to prove these analogues, we give enumerations and generating functions for permutations which avoid both 132 and 1□231□23, and certain additional patterns. We also give generating functions for permutations avoiding 132 and 1□231□23 and containing certain additional patterns exactly once. In all cases we express these generating functions in terms of Chebyshev polynomials of the second kind.