Applying the cluster method to count occurrences of generalized permutation patterns

Abstract

We apply ideas from the cluster method to q-count the permutations of a multiset according to the number of occurrences of certain generalized patterns, as defined by Babson and Steingrímsson. In particular, we consider those patterns with three letters and one internal dash, as well as permutation statistics composed of counting the number of occurrences of multisets of such patterns. Counting is done via recurrences which simplify in the case of permutations. A collection of Maple procedures implementing these recurrences accompanies the article.

Keywords:

• permutation patterns
• exact enumeration
• generating functions
• q-difference equations

AMS Subject Classification::

• 05A05
• 05A15

Acknowledgements

The author would like to thank his advisor, Doron Zeilberger, for his recommendation to pursue this approach to counting generalized patterns. He would also like to thank the referee and editors for their diligence and aid in preparation of this article, in particular the referee's direction towards Steingrímsson's upcoming survey article on generalized permutation patterns [14].