Enumerating 1324-avoiders with few inversions (Q6925669)

Let Av\(_{n}^{k}(\tau)\) be the set of all permutations of length \(n\) with exactly \(k\) inversions avoiding \(\tau\) and av\(_{n}^{k}(\tau)=|\mathrm{Av}_{n}^{k}(\tau)|\). In this paper, the authors enumerate the numbers av\(_{n}^{k}(1324)\) of 1324-avoiding \(n\)-permutations with exactly \(k\) inversions for all \(k\) and \(n\geq (k + 7)/2\). The result depends on a structural characterization of such permutations in terms of a new notion of almost-decomposability. It is proven that all permutations in Av\(_{n}^{k}(1324)\) are either decomposable or almost decomposable whenever \(n\geq (k+7)/2\). The authors construct an injection Av\(_{n}^{k}(1324)\rightarrow\mathrm{Av}_{n+1}^{k}(1324)\) and the enumeration of av\(_{n}^{k}(1324)-\mathrm{av}_{n+1}^{k}(1324)\) is performed based on this injection. In particular, their enumeration verifies half of a conjecture of \textit{A. Claesson} et al. [J. Comb. Theory, Ser. A 119, No. 8, 1680--1691 (2012; Zbl 1246.05002)], according to which av\(_{n}^{k}(1324)\leq\mathrm{av}_{n+1}^{k}(1324)\) for all \(n\) and \(k\). Proving also the other half would improve the best known upper bound for the exponential growth rate of the number of 1324-avoiders from 13.5 to approximately 13.002. Further directions and conjectures conclude the paper.