Involutions Restricted by 3412, Continued Fractions, and Chebyshev Polynomials

Eric Egge, Toufik Mansour

Published 2004-01-18Version 1

We study generating functions for the number of involutions, even involutions, and odd involutions in $S_n$ subject to two restrictions. One restriction is that the involution avoid 3412 or contain 3412 exactly once. The other restriction is that the involution avoid another pattern $\tau$ or contain $\tau$ exactly once. In many cases we express these generating functions in terms of Chebyshev polynomials of the second kind.