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: