Séminaire Lotharingien de Combinatoire, B48a (2002), 23 pp.

Olivier Guibert and Toufik Mansour

Restricted 132-Involutions

Abstract. We study generating functions for the number of involutions of length n avoiding (or containing exactly once) 132 and avoiding (or containing exactly once) an arbitrary permutation \tau of length k. In several interesting cases these generating functions depend only on k and can be expressed via Chebyshev polynomials of the second kind. In particular, we show that involutions of length n avoiding both 132 and 12...k are equinumerous with involutions of length n avoiding both 132 and any extended double-wedge pattern of length k. We use combinatorial methods to prove several of our results.

Received: January 16, 2002; Revised: April 30, 2002; July 14, 2002; Accepted: August 7, 2002.

The following versions are available: