Mesh patterns and the expansion of permutation statistics as sums of permutation patterns

Any permutation statistic f:G → ℂ may be represented uniquely as a, possibly infinite, linear combination of (classical) permutation patterns: f = Σ_τλ_f(τ)τ. To provide explicit expansions for certain statistics, we introduce a new type of permu- tation patterns that we call mesh patterns. Intuitively, an occurrence of the mesh pattern p = (π, R) is an occurrence of the permutation pattern π with additional restrictions specified by R on the relative position of the entries of the occurrence. We show that, for any mesh pattern p = (π, R), we have λ_p(τ) = (-1)^{{pipe}τ{pipe}-{pipe}π{pipe}}p*(τ) where p* = (π,R^c) is the mesh pattern with the same underlying permutation as p but with complementary restrictions. We use this result to expand some well known permutation statistics, such as the number of left-to-right maxima, descents, excedances, fixed points, strong fixed points, and the major index. We also show that alternating permutations, André permutations of the first kind and simsun per- mutations occur naturally as permutations avoiding certain mesh patterns. Finally, we provide new natural Mahonian statistics.