Continued fractions and generalized patterns
Abstract
Description
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_{τ;r}(n)$ be the number of $1\mn3\mn2$-avoiding permutations on $n$ letters that contain exactly $r$ occurrences of $τ$, where $τ$ a generalized pattern on $k$ letters. Let $F_{τ;r}(x)$ and $F_τ(x,y)$ be the generating functions defined by $F_{τ;r}(x)=\sum_{n\geq0} f_{τ;r}(n)x^n$ and $F_τ(x,y)=\sum_{r\geq0}F_{τ;r}(x)y^r$. We find an explicit expression for $F_τ(x,y)$ in the form of a continued fraction for where $τ$ given as a generalized pattern; $τ=12\mn3\mn...\mn k$, $τ=21\mn3\mn...\mn k$, $τ=123... k$, or $τ=k... 321$. In particularly, we find $F_τ(x,y)$ for any $τ$ generalized pattern of length 3. This allows us to express $F_{τ;r}(x)$ via Chebyshev polynomials of the second kind, and continued fractions.
16 pages
16 pages