Enumerating 1324-avoiders with few inversions
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.
- 1324-avoiding permutations revisited
- A combinatorial proof of the log-concavity of a famous sequence counting permutations
- A new record for \(1324\)-avoiding permutations
- A new upper bound for 1324-avoiding permutations
- A simple proof for the exponential upper bound for some tenacious patterns
- A structural characterisation of \(\mathrm{Av}(1324)\) and new bounds on its growth rate
- Combinatorics of permutations
- Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Forbidden subsequences
- scientific article; zbMATH DE number 5831716 (Why is no real title available?)
- On \(1324\)-avoiding permutations
- On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Patterns in permutations and words.
- Permutation classes
- Permutations avoiding 1324 and patterns in Łukasiewicz paths
- Permutations avoiding certain patterns: The case of length 4 and some generalizations
- Symmetric functions and P-recursiveness
- The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
- Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
- Wilf-equivalence for singleton classes
This page was built for publication: Enumerating 1324-avoiders with few inversions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6925669)
