Continued Fractions and Generalized Patterns

Babson and Steingrimsson (2000, Séminaire Lotharingien de Combinatoire, B44b, 18) introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. ;r(n) be the number of 1 - 3 - 2-avoiding permutations on n letters that contain exactly r occurrences of τ, where τ is a generalized pattern on k letters. Let Fτ;r(x) and Fτ(x, y) be the generating functions defined by Fτ;r(x) = ∑ n ≥ 0fτ;r(n)xnand Fτ(x, y) = ∑ r ≥ 0Fτ;r(x)yr. We find an explicit expression for Fτ(x, y) in the form of a continued fraction for τ given as a generalized pattern: τ = 12 - 3 -⋯-k, τ = 21 - 3 -⋯-k, τ = 123⋯k, or τ = k⋯321. In particular, 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.