Séminaire Lotharingien de Combinatoire, 86B.2 (2022), 12 pp.

Yan Zhuang

Refined Consecutive Pattern Enumeration Via a Generalized Cluster Method

Abstract. We present a general approach for counting permutations by occurrences of prescribed consecutive patterns together with various inverse statistics. We first lift the Goulden-Jackson cluster method for permutations - a standard tool in the study of consecutive patterns - to the Malvenuto-Reutenauer algebra. Upon applying standard homomorphisms, our result specializes to both the cluster method for permutations as well as a q-analogue which keeps track of the inversion number statistic. We construct additional homomorphisms which lead to further specializations for keeping track of inverses of shuffle-compatible descent statistics; these include the inverse descent number, inverse peak number, and inverse left peak number. To illustrate this approach, we present new formulas that count permutations by occurrences of the monotone consecutive pattern 12...m while also keeping track of these inverse statistics.

Received: November 25, 2021. Accepted: March 4, 2022. Final version: April 1, 2022.

The following versions are available: