Paper detail

A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra

The Goulden-Jackson cluster method is a powerful tool for counting words by occurrences of prescribed subwords, and was adapted by Elizalde and Noy for counting permutations by occurrences of prescribed consecutive patterns. In this paper, we lift the cluster method for permutations 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 using the theory of shuffle-compatibility, leading to further specializations which keep track of various "inverse statistics", including the inverse descent number, inverse peak number, and inverse left peak number. This approach is then used to derive formulas for counting permutations by occurrences of two families of consecutive patterns -- monotone patterns and transpositional patterns -- refined by these statistics.