Continued fractions and generalized patterns

Abstract

In [BS] Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Let $f_{\tau ;r}(n)$ be the number of $1\mn3\mn2$-avoiding permutations on $n$ letters that contain exactly $r$ occurrences of $\tau$, where $\tau$ a generalized pattern on $k$ letters. Let $F_{\tau ;r}(x)$ and $F_{\tau }(x,y)$ be the generating functions defined by $F_{\tau ;r}(x)={\sum }_{n\ge 0}{f}_{\tau ;r}(n)x^n$ and $F_{\tau }(x,y)={\sum }_{r\ge 0}{F}_{\tau ;r}(x)y^r$. We find an explicit expression for $F_{\tau }(x,y)$ in the form of a continued fraction for where $\tau$ given as a generalized pattern; $τ=12\mn3\mn...\mn k$, $τ=21\mn3\mn...\mn k$, $\tau =\mathrm{123...}k$, or $\tau =k...321$. In particularly, we find $F_{\tau }(x,y)$ for any $\tau$ generalized pattern of length 3. This allows us to express $F_{\tau ;r}(x)$ via Chebyshev polynomials of the second kind, and continued fractions.

16 pages