Séminaire Lotharingien de Combinatoire, 93B.132 (2025), 12 pp.

Svante Linusson and Emil Verkama

Enumerating 1324-Avoiders with Few Inversions

Abstract. The problem of determining the number of 1324-avoiding permutations of length n has received much attention. We work towards this goal by enumerating av_n^k(1324), the number of 1324-avoiding n-permutations with exactly k inversions, for all k and n ≥ (k+7)/2. This is achieved with a new structural characterization of such permutations in terms of a new notion of almost-decomposability. In particular, our enumeration verifies half of a conjecture of Claesson, Jelínek and Steingrímsson, according to which av_{n^k(1324) ≤ av_n+1^k(1324) for all n and k. Proving the full conjecture 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.

Received: November 15, 2024.
Accepted: February 15, 2025.
Final version: April 1, 2025.

The following versions are available:

PDF (793 K)
TeX version}