Permutation patterns and statistics

Let S n denote the symmetric group of all permutations of { 1 , 2 , … , n } and let S = ∪ n ≥ 0 S n . If Π ⊆ S is a set of permutations, then we let Av n ( Π ) be the set of permutations in S n which avoid every permutation of Π in the sense of pattern avoidance. One of the celebrated notions in pattern theory is that of Wilf-equivalence, where Π and Π ′ are Wilf equivalent if # Av n ( Π ) = # Av n ( Π ′ ) for all n ≥ 0 . In a recent paper, Sagan and Savage proposed studying a q -analogue of this concept defined as follows. Suppose st : S → { 0 , 1 , 2 , … } is a permutation statistic and consider the corresponding generating function F n st ( Π ; q ) = ∑ σ ∈ Av n ( Π ) q st σ . Call Π , Π ′ st-Wilf equivalent if F n st ( Π ; q ) = F n st ( Π ′ ; q ) for all n ≥ 0 . We present the first in-depth study of this concept for the inv and maj statistics. In particular, we determine all inv - and maj -Wilf equivalences for any Π ⊆ S 3 . This leads us to consider various q -analogues of the Catalan numbers, Fibonacci numbers, triangular numbers, and powers of two. Our proof techniques use lattice paths, integer partitions, and Foata’s second fundamental bijection. We also answer a question about Mahonian pairs raised in the Sagan–Savage article.