Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials |
| |
Authors: | Qing-Hu Hou |
| |
Institution: | a Center for Combinatorics, LPMC, Nankai University, Tianjin 300071, PR China b Department of Mathematics, University of Haifa, 31905 Haifa, Israel |
| |
Abstract: | 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□23 (there is no occurrence πi<πj<πj+1 such that 1?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□23, and certain additional patterns. We also give generating functions for permutations avoiding 132 and 1□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. |
| |
Keywords: | Restricted permutation Pattern-avoiding permutation Forbidden subsequence Continued fraction Chebyshev polynomial |
本文献已被 ScienceDirect 等数据库收录! |
|