Permutation statistics and multiple pattern avoidance (Q2345777): Difference between revisions

Let \({\mathcal S}_{n}\) be the set of all permutations of \([n]=\{1,2,\ldots n\}\) and \({\mathcal S}=\cup_{n=0}^{\infty}{\mathcal S}_{n}\) be all permutations. We let \({\mathcal S}_{n}(\Pi)\) denote all permutations in \({\mathcal S}_{n}\) which avoid all patterns \(\pi \in \Pi\) simultaneously. (For example, the permutation 31542 contains the pattern 132 four times but avoids the pattern 1234). Given a permutation statistic (i.e. a function \(\mathrm{st}: {\mathcal S}\to \mathbb{N}\)) the st-polynomial is given by \[ F_{n}^{\mathrm{st}}(\Pi)= F_{n}^{\mathrm{st}}(\Pi; q)=\sum_{\sigma\in {\mathcal S}_{n}(\Pi)}q^{\mathrm{st}(\sigma)}. \] Two sets of patterns \(\Pi\) and \(\Pi^{\prime}\) are said to be st-Wilf-equivalent if \(F_{n}^{\mathrm{st}}(\Pi;q)=F_{n}^{\mathrm{st}}(\Pi^{\prime};q)\) for all \(n\geq 0\). The paper under review studies multiple pattern avoidance on certain permutation statistics including the inversion number of a permutation (i.e. the number of ordered pairs \((i,j)\) such that \(i\) is before \(j\) in the usual order on \([n]\) but after it in the permutation. For example, \(\mathrm{inv}(3142)=3\) from the pairs \((1,2), (1,4), (3,4)\). In [\textit{T. Dokos} et al., Discrete Math. 312, No. 18, 2760--2775 (2012; Zbl 1248.05004)] it is conjectured that there are only essentially trivial inv-Wilf equivalences, obtained by reflections and rotations of permutation matrices. The authors disprove this conjecture by giving a formula for \(F_{n}^{\mathrm{st}}(\Pi;q)\) (for certain kinds of permutation statistics \(\mathrm{st}\) including \(\mathrm{inv}\)) in terms of the polynomials from some subblocks of the patterns in \(\Pi\).