% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{132}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{mathtools, bm}

\usepackage{tabularray}
\UseTblrLibrary{booktabs}

\usepackage{tikz}
\tikzstyle{dot}=[draw, shape=circle, fill=black, inner sep=0pt, minimum size=3pt]

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\DeclareMathOperator{\Av}{Av}
\DeclareMathOperator{\av}{av}
\DeclareMathOperator{\comp}{comp}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\rc}{rc}

\newcommand{\delete}{\smallsetminus}
\newcommand{\gridcolor}{blue!60!black!25}
\newcommand{\pt}{\small\(\bm\times\)}
\newcommand{\upt}{\(\bm\times\)}

%% define your title in the usual way
\title{Enumerating 1324-avoiders with few inversions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{
  Svante Linusson\thanks{\href{mailto:linusson@kth.se}{linusson@kth.se}}\addressmark{1}
  \and Emil Verkama\thanks{\href{mailto:verkama@kth.se}{verkama@kth.se}}\addressmark{1}
}{
  Svante Linusson
  and Emil Verkama
}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden}

%% put the date of submission here
\received{November 13, 2024}

%% leave this blank until submitting a revised version
\revised{April 1, 2025}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\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 \(\mathrm{av}_n^k(1324)\), the number of \(1324\)-avoiding \(n\)-permutations with exactly \(k\) inversions, for all \(k\) and \(n \geq (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 \(\mathrm{av}_n^k(1324) \leq \mathrm{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\).}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{1324, enumeration, inversions, pattern avoidance, permutations}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{fpsac_bib.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction}

A permutation \(\pi \in \mathfrak S_n\) \emph{contains} a \emph{pattern} \(\tau \in \mathfrak S_m\) if there exist indices \(i_1 < \ldots < i_m\) such that \(\pi(i_a) < \pi(i_b)\) if and only if \(\tau(a) < \tau(b)\) for all \(a,b \in [m]\). Otherwise, \(\pi\) \emph{avoids} \(\tau\). An \emph{inversion} in \(\pi\) is a pair of indices \((i,j)\) such that \(i < j\) and \(\pi_i > \pi_j\). We denote by \(\Av_n(\tau)\) the set of all permutations of length \(n\) avoiding \(\tau\), and by \(\Av_n^k(\tau) \subseteq \Av_n(\tau)\) those with exactly \(k\) inversions. Furthermore, we set \(\av_n(\tau) = |{\Av_n(\tau)}|\) and \(\av_n^k(\tau) = |{\Av_n^k(\tau)}|\). Two patterns \(\sigma\) and \(\tau\) are called \emph{Wilf equivalent} if \(\av_n(\sigma) = \av_n(\tau)\) for all \(n\).

\subsection{Avoiding 1324}

Patterns of length four or lower are generally well understood, except for a single case: the pattern \(1324\). The numbers \(\av_n(1324)\) have been determined computationally up to \(n = 50\) (sequence \href{https://oeis.org/A061552}{A061552} in the OEIS \cite{oeis}), but in general not even the asymptotics are well-understood. The \emph{Stanley--Wilf limit}
\begin{equation*}
  L(\tau) = \lim_{n \to \infty} \av_n(\tau)^{1 / n}
\end{equation*} 
exists for all patterns \(\tau\) due to the Marcus--Tardos theorem \cite{arratia_stanley-wilf_1999,marcus_excluded_2004}, but when \(\tau = 1324\), only loose bounds are know. Table \ref{tab:bounds} shows the timeline of the evolution of these bounds; currently they are \(10.27 < L(1324) < 13.5\) \cite{bevan_structural_2020}. Conway, Guttmann and Zinn-Justin have convincingly estimated that \(L(1324) \approx 11.600 \pm 0.003\) \cite{conway_1324-avoiding_2018}.

\begin{table}[htb]
  \centering
  \begin{tabular}{lll} \toprule
    & Lower & Upper \\ \midrule
    2004. Bóna \cite{bona_simple_2004} & & 288 \\
    2005. Bóna \cite{bona_limit_2005} & 9 & \\
    2006. Albert et al. \cite{albert_stanley-wilf_2006} & 9.47 & \\
    2012. Claesson, Jelínek and Steingrímsson \cite{claesson_upper_2012} & & 16 \\
    2014. Bóna \cite{bona_new_2014} & & 13.93 \\
    2015. Bóna \cite{bona_new_2015} & & 13.74 \\
    2015. Bevan \cite{bevan_permutations_2015} & 9.81 \\
    2020. Bevan et al. \cite{bevan_structural_2020} & 10.27 & 13.5 \\ \bottomrule
  \end{tabular}
  \caption{Best known upper and lower bounds for \(L(1324)\) throughout history.}
  \label{tab:bounds}
\end{table}

One possible avenue towards improvement is suggested by a conjecture of Claesson, Jelínek and Steingrímsson.

\begin{conjecture}[{\cite[Conjecture 13]{claesson_upper_2012}}] \label{conj:1324anders}
  For all nonnegative integers \(n\) and \(k\), 
  \begin{equation*}
    \av_n^k(1324) \leq \av_{n+1}^k(1324).
  \end{equation*}
\end{conjecture}

As was demonstrated in \cite{claesson_upper_2012}, the conjecture implies a new upper bound \(L(1324) \leq \exp\big(\pi \sqrt{2/3}\big) < 13.002\), using the fact that \(\av_n^k(1324)\) is constant when the number \(k\) of inversions is fixed and \(n \geq k+2\). Our main result proves half of the conjecture.

\begin{theorem} \label{thm:1324}
  For all nonnegative integers \(k\) and \(n \geq \frac{k+7}{2}\),
  \begin{equation*}
    \av_n^k(1324) = [x^k] \left(P(x)^2 - \frac{R_n(x)}{1-x}\right),
  \end{equation*}
  where
  \begin{equation*}
    R_n(x) = 2(2+x) x^{n-1} P(x)^2,
  \end{equation*}
  and \(P(x)\) is the generating function for the partition numbers. In particular,
  \begin{equation*}
    \av_{n+1}^k(1324) - \av_n^k(1324) = [x^k] R_n(x) \geq 0,
  \end{equation*}
  and this difference has a combinatorial interpretation.
\end{theorem}

The proof relies on a new notion of \emph{almost decomposable} permutations, and is available in its entirety in our preprint \cite{linusson_1324_2024}. The following subsection motivates this by defining \emph{decomposable} permutations, and explains the constants \(\av_{k+2}^k(1324)\).

\subsection{Direct sums and decomposability}

For two permutations \(\sigma \in \mathfrak S_n\) and \(\tau \in \mathfrak S_m\), we define the \emph{direct sum} \(\sigma \oplus \tau \in \mathfrak S_{n+m}\) by
\begin{equation*}
  (\sigma \oplus \tau)(i) = \begin{cases}
    \sigma(i) & \text{if } i \leq n, \\
    n + \tau(i-n) & \text{if } i > n.
  \end{cases}
\end{equation*}
For example, \(231 \oplus 21\) is obtained in the following way.
\begin{center}
  \begin{tikzpicture}[scale=0.4]
    \clip (0.5,-1.7) rectangle (6,3.5);
    \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (3.5,3.5);
    \foreach \x\y in {1/2,2/3,3/1}
    {
      \node at (\x,\y-0.004) {\pt};
      \node at (\x,-0.3) {\(\y\)};
    }
    \node at (4.85,2) {\(\oplus\)};
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.4]
    \clip (0.5,-2.2) rectangle (5,2.5);

    \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (2.5,2.5);
    \foreach \x\y in {1/2,2/1}
    {
      \node at (\x,\y-0.004) {\pt};
      \node at (\x,-0.3) {\(\y\)};
    }
    \node at (3.85,1.5) {\(=\)};
  \end{tikzpicture}
  \begin{tikzpicture}[scale=0.4]
    \clip (0.5,-0.7) rectangle (5.5,5.5);
    \fill[blue!15] (0.5,0.5) rectangle (3.5,3.5);
    \fill[blue!15] (3.5,3.5) rectangle (5.5,5.5);

    \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (5.5,5.5);
    \foreach \x\y in {1/2,2/3,3/1,4/5,5/4}
    {
      \node at (\x,\y-0.004) {\pt};
      \node at (\x,-0.3) {\(\y\)};
    }
  \end{tikzpicture}
\end{center}

If a permutation \(\pi\) is the direct sum of two nonempty permutations, we call \(\pi\) \emph{decomposable}, and otherwise \emph{indecomposable}. We can write \(\pi\) uniquely as a direct sum
\begin{equation*}
  \pi = \pi^{(1)} \oplus \pi^{(2)} \oplus \ldots \oplus \pi^{(c)},
\end{equation*}
where each \emph{component} \(\pi^{(i)}\) is indecomposable (and nonempty). The formula (see \cite[Lemma 8]{claesson_upper_2012})
\begin{equation*}
  \comp(\pi) + \inv(\pi) \geq |\pi|,
\end{equation*}
where \(\comp(\pi)\), \(\inv(\pi)\) and \(|\pi|\) denote the number of components, the number of inversions and the length of \(\pi\), respectively, indicates that a permutation with few inversions should have many components. In particular, if \(\inv(\pi) \leq |\pi| - 2\), then \(\comp(\pi) \geq |\pi| - \inv(\pi) \geq 2\). It is easy to see that a decomposable permutation \(\pi\) avoids \(1324\) if and only if it is of the form
\begin{equation} \label{eq:1324 form}
  \pi = \pi^{(1)} \oplus 1 \oplus 1 \oplus \ldots \oplus 1 \oplus \pi^{(2)},
\end{equation}
where \(\pi^{(1)}\) avoids \(132\) and \(\pi^{(2)}\) avoids \(213\). The \emph{inversion table} \(b_1 b_2 \ldots b_n\) of a \(132\)-avoider of length \(n\), defined by \(b_i = |\{j > i : \pi_j < \pi_i\}|\), is weakly decreasing and therefore -- with the exclusion of trailing \(0\)'s -- an integer partition of \(\inv(\pi)\). It follows that
\begin{equation*}
  \av_n^k(132) = \av_n^k(213) = p(k) 
\end{equation*}
for all \(n \geq k+1\), where \(p(k)\) is the \(k\)th partition number. Hence, \eqref{eq:1324 form} gives
\begin{equation*}
  \av_n^k(1324) = [x^k] P(x)^2,
\end{equation*}
where \(P(x) = \sum_{k \geq 0} p(k) x^k\) and \(n \geq k + 2\) \cite[Proposition 15]{claesson_upper_2012}.

\subsection{Interpreting the main result}

Observe that due to the preceding discussion, \Cref{conj:1324anders} trivially holds (with equality) for all \(n \geq k+2\). Our main result, \Cref{thm:1324}, improves this to \(n \geq \frac{k + 7}{2}\), and therefore essentially proves half of the conjecture, along with providing an enumeration for those values of \(\av_n^k(1324)\). The strategy is to find an injection \(\Av_n^k(1324) \to \Av_{n+1}^k(1324)\) and analyze it in order to enumerate the permutations not contained in its image. The injection relies on \emph{almost decomposability}, which is related to normal decomposability, so it is not surprising that the partition numbers show up.

It is useful to keep in mind Table \ref{tab:1324 diagram}, in which the entry on row \(n\) and column \(k\) equals \(\av_n^k(1324)\). \Cref{conj:1324anders} is equivalent to the statement that each column of the diagram is weakly increasing as \(n\) increases. The blue cells indicate the constant parts of each column; the sequence \(1,2,5,10,20,\ldots\) comes from the generating function \(P(x)^2\). The red cells contain the new numbers enumerated by \Cref{thm:1324}. Specifically, the sequence of numbers in the blue and red cells on row \(n\) is given by the first \(2n-6\) coefficients of the generating function \(P(x)^2 - R_n(x)/(1 - x)\).

\begin{table}[htb]
  \centering
  \begin{tblr}{
    hline{2} = {1-14}{black},
    vline{2} = {1-13}{black},
    rows = {mode=math, rowsep=1pt},
    cell{-}{-} = {c},
    cell{3}{2} = {bg=blue!40},
    cell{4}{2-3} = {bg=blue!40},
    cell{5}{2-4} = {bg=blue!40},
    cell{6}{2-5} = {bg=blue!40},
    cell{7}{2-6} = {bg=blue!40},
    cell{8}{2-7} = {bg=blue!40},
    cell{9}{2-8} = {bg=blue!40},
    cell{10}{2-9} = {bg=blue!40},
    cell{11}{2-10} = {bg=blue!40},
    cell{12}{2-11} = {bg=blue!40},
    cell{13}{2-12} = {bg=blue!40},
    cell{7}{7} = {bg=red!40},
    cell{8}{8-9} = {bg=red!40},
    cell{9}{9-11} = {bg=red!40},
    cell{10}{10-13} = {bg=red!40},
    cell{11}{11-14} = {bg=red!40},
    cell{12}{12-14} = {bg=red!40},
    cell{13}{13-14} = {bg=red!40},
  }
    n \backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
    1 & 1 \\
    2 & 1 & 1 \\
    3 & 1 & 2 & 2 & 1 \\
    4 & 1 & 2 & 5 & 6 & 5 & 3 & 1 \\
    5 & 1 & 2 & 5 & 10 & 16 & 20 & 20 & 15 & 9 & 4 & 1 \\
    6 & 1 & 2 & 5 & 10 & 20 & 32 & 51 & 67 & 79 & 80 & 68 & 49 & 29 & \ldots \\
    7 & 1 & 2 & 5 & 10 & 20 & 36 & 61 & 96 & 148 & 208 & 268 & 321 & 351 & \ldots \\
    8 & 1 & 2 & 5 & 10 & 20 & 36 & 65 & 106 & 171 & 262 & 397 & 568 & 784 & \ldots \\
    9 & 1 & 2 & 5 & 10 & 20 & 36 & 65 & 110 & 181 & 286 & 443 & 664 & 985 & \ldots \\
    10 & 1 & 2 & 5 & 10 & 20 & 36 & 65 & 110 & 185 & 296 & 467 & 714 & 1077 & \ldots \\
    11 & 1 & 2 & 5 & 10 & 20 & 36 & 65 & 110 & 185 & 300 & 477 & 738 & 1127 & \ldots \\
    12 & 1 & 2 & 5 & 10 & 20 & 36 & 65 & 110 & 185 & 300 & 481 & 748 & 1151 & \ldots
  \end{tblr}
  \caption{The numbers \(\av_n^k(1324)\).}
  \label{tab:1324 diagram}
\end{table}

The differences \(\av_{n+1}^k(1324) - \av_n^k(1324)\) are displayed in Table \ref{tab:1324 difference diagram}. The blue \(0\)'s come from the constant part of each column, and the numbers in the red cells are given by \(R_n(x)\). The diagram also shows that \(n \geq \frac{k+7}{2}\) is the best possible bound for our method: if \(n < \frac{k+7}{2}\) (and \(k \geq 7\)), then \(\av_{n+1}^k(1324) - \av_n^k(1324)\) no longer equals \([x^k] R_n(x)\). An expanded version of Table \ref{tab:1324 diagram} is available at \url{https://akc.is/inv-mono/} courtesy of Anders Claesson.

\begin{table}[htb]
  \centering
  \begin{tblr}{
    hline{2} = {1-15}{},
    vline{2} = {1-13}{},
    rows = {mode=math, rowsep=1pt},
    cell{-}{-} = {c},
    cell{3}{2} = {bg=blue!40},
    cell{4}{2-3} = {bg=blue!40},
    cell{5}{2-4} = {bg=blue!40},
    cell{6}{2-5} = {bg=blue!40},
    cell{7}{2-6} = {bg=blue!40},
    cell{8}{2-7} = {bg=blue!40},
    cell{9}{2-8} = {bg=blue!40},
    cell{10}{2-9} = {bg=blue!40},
    cell{11}{2-10} = {bg=blue!40},
    cell{12}{2-11} = {bg=blue!40},
    cell{13}{2-12} = {bg=blue!40},
    cell{7}{7} = {bg=red!40},
    cell{8}{8-9} = {bg=red!40},
    cell{9}{9-11} = {bg=red!40},
    cell{10}{10-13} = {bg=red!40},
    cell{11}{11-15} = {bg=red!40},
    cell{12}{12-15} = {bg=red!40},
    cell{13}{13-15} = {bg=red!40},
  }
    n \backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
    1 & 0 & 1 \\
    2 & 0 & 1 & 2 & 1 \\
    3 & 0 & 0 & 3 & 5 & 5 & 3 & 1 \\
    4 & 0 & 0 & 0 & 4 & 11 & 17 & 19 & 15 & 9 & 4 & 1 \\
    5 & 0 & 0 & 0 & 0 & 4 & 12 & 31 & 52 & 70 & 76 & 67 & 49 & 29 & 14 &\ldots \\
    6 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 29 & 69 & 128 & 200 & 272 & 322 & 333 & \ldots \\
    7 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 23 & 54 & 129 & 247 & 433 & 672 & \ldots \\
    8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 24 & 46 & 96 & 201 & 397 & \ldots \\
    9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 24 & 50 & 92 & 166 & \ldots \\
    10 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 24 & 50 & 100 & \ldots \\
    11 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 24 & 50 & \ldots \\
    12 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 10 & 24 & \ldots
  \end{tblr}
  \caption{The numbers \(\av_{n+1}^k(1324) - \av_n^k(1324)\).}
  \label{tab:1324 difference diagram}
\end{table}

\section{Almost decomposable permutations} \label{sec:almost decomposable}

We will often utilize the \emph{plots} \(\left\{(i, \pi_i) : i \in [n] \right\}\) (in cartesian coordinates) of permutations \(\pi \in \mathfrak S_n\). Inverting \(\pi\) corresponds with reflecting its plot across the line \(y = x\), and the \emph{reverse-complement} \(\rc(\pi)_i = n + 1 - \pi_{n + 1 - i}\) rotates the plot by \(180\) degrees. Both \(\pi^{-1}\) and \(\rc(\pi)\) preserve \(1324\)-avoidance and the number of inversions of \(\pi\), so these are useful operations for us.

We also use the \emph{Rothe diagram} of \(\pi\), which is obtained from the plot of \(\pi\) by drawing lines to north and east from each point \((i, \pi_i)\), and marking the empty coordinate points -- these points are the inversions of \(\pi\). The following figure shows an example.

\begin{center}
  \begin{tikzpicture}[scale=0.38]
    \node at (-4.4,5) {\(245169783 \quad =\)};

    \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (9.5,9.5);
    
    \foreach \x\y in {1/2,2/4,3/5,4/1,5/6,6/9,7/7,8/8,9/3}
    {
      \node at (\x,\y-0.004) {\pt};
      \draw[thick]
        (\x,\y) -- (\x,9.5)
        (\x,\y) -- (9.5,\y);
    }
    \foreach \x\y in {1/1,2/1,2/3,3/1,3/3,5/3,6/3,6/7,6/8,7/3,8/3}
      \node[dot, blue!40, minimum size=6pt] at (\x,\y) {};
  \end{tikzpicture}
\end{center}

\begin{definition}
  For \(\pi \in \mathfrak S_n\) and \(i \in [n]\), we denote by \(\pi \delete \pi_i\) the unique permutation in \(\mathfrak S_{n-1}\) that is order-isomorphic to \(\pi_1 \ldots \pi_{i-1} \pi_{i+1} \ldots \pi_n\). We say that \(\pi \delete \pi_i\) is obtained by \emph{deleting} entry \(\pi_i\) from \(\pi\).
\end{definition}

\begin{definition}\label{def:almost decomp}
  A permutation \(\pi \in \mathfrak S_n\) is called \emph{almost decomposable} if it is indecomposable, but at least one of \(\pi \delete 1\), \(\pi \delete n\), \(\pi \delete \pi_1\), \(\pi \delete \pi_n\) is decomposable.
\end{definition}

For example, consider the indecomposable permutation \(\pi = 245169783\). Since \(\pi \delete 1 = 13458672 = 1 \oplus 2347561\) is decomposable, \(\pi\) is almost decomposable. Notice that \(\pi \delete 3 = 23415867 = 2341 \oplus 1 \oplus 312\) is also decomposable.
  
Almost-decomposability means that deleting one of the points from the `boundary' of the plot of the permutation makes it decomposable. Here are the plots of \(\pi \delete 1\) and \(\pi \delete 3\).

\begin{center}
\begin{tikzpicture}[scale=0.38]
  \fill[blue!15] (0.5,1.5) rectangle (1.5,2.5);
  \fill[blue!15] (1.5,2.5) rectangle (9.5,9.5);

  \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (9.5,9.5);

  \foreach \x\y in {1/2,2/4,3/5,5/6,6/9,7/7,8/8,9/3}
    \node at (\x,\y-0.004) {\pt};

  \node [red] at (4,1-0.004) {\pt};
  \node at (5,-0.5) {\(\pi \delete 1\)};
\end{tikzpicture} \hspace{5mm}
\begin{tikzpicture}[scale=0.38]
  \fill[blue!15] (0.5,0.5) rectangle (4.5,5.5);
  \fill[blue!15] (4.5,5.5) rectangle (5.5,6.5);
  \fill[blue!15] (5.5,6.5) rectangle (8.5,9.5);

  \draw [step=1, thick, color=\gridcolor] (0.5,0.5) grid (9.5,9.5);

  \foreach \x\y in {1/2,2/4,3/5,4/1,5/6,6/9,7/7,8/8}
    \node at (\x,\y-0.004) {\pt};

  \node [red] at (9,3-0.004) {\pt};
  \node at (5,-0.5) {\(\pi \delete 3\)};
\end{tikzpicture}
\end{center}

An important detail in \Cref{sec:injection}, where the injection \(\Av_n^k(1324) \to \Av_{n+1}^k(1324)\) is constructed, is that e.g.\ \emph{both} \(\pi \delete 1\) and \(\pi \delete n\) can be decomposable when \(\pi\) is almost decomposable. However, not all combinations are possible, and this is critical.

\begin{proposition} \label{prop:forbidden removable point combinations}
  Let \(\pi \in \mathfrak S_n\) be indecomposable. If \(\pi \delete 1\) is decomposable then \(\pi \delete \pi_1\) is indecomposable, and similarly if \(\pi \delete n\) is decomposable then \(\pi \delete \pi_n\) is indecomposable.
\end{proposition}

The following result is our strucural characterization of \(\Av_n^k(1324)\) for \(k \leq 2n - 7\). Its proof relies on an intricate case-by-case analysis, the details of which are available in \cite{linusson_1324_2024}.

\begin{theorem} \label{thm:removepoint}
  Each indecomposable permutation in \(\Av_n^k(1324)\), where \(k \leq 2n - 7\), is almost decomposable.
\end{theorem}

The bound \(k \leq 2n - 7\) is tight, since e.g.\ 
\begin{equation*}
  \pi = [3, 6, 1, 2,\ \ 7,\ldots, n,\ \ 4, 5]
\end{equation*}
is \(1324\)-avoiding with \(2n-6\) inversions, and neither decomposable nor almost decomposable. Here is the plot of the first such permutation, \(\pi = 3612745\).

\begin{center} \noindent
  \begin{tikzpicture}[scale=0.38]
    \node at (-3.9,4) {\(3612745 \quad = \)};
    \draw [step=1, thick, \gridcolor] (0.5,0.5) grid (7.5,7.5);
    \foreach \x\y in {1/3,2/6,3/1,4/2,5/7,6/4,7/5}
      \node at (\x,\y-0.004) {\pt};
    \foreach \x\y in {1/1,1/2,2/1,2/2,2/4,2/5,5/4,5/5}
      \node[dot, blue!40, minimum size=6pt] at (\x,\y) {};
  \end{tikzpicture}
\end{center}

Interestingly, the same permutation \(\pi\) has been used before to exemplify that two \(1324\)-avoiding permutations can have the same \emph{profile}: \(\pi\) and \(\pi^{-1}\) have the same left-to-right minima and right-to-left maxima in the same positions \cite{bona_permutations_1997}.

\section{The injection} \label{sec:injection}

Denote by \(\mathcal D_n^k\) and \(\mathcal A_n^k\) the sets of decomposable and almost decomposable permutations in \(\Av_n^k(1324)\), respectively. In this section we will construct injections
\begin{equation*}
  g : \mathcal D_n^k \longrightarrow \Av_{n+1}^k(1324) \qquad \text{and} \qquad
  f : \mathcal A_n^k \longrightarrow \Av_{n+1}^k(1324),
\end{equation*}
with disjoint images, for \emph{all} \(n\) and \(k\). If \(k \leq 2n - 7\) then all permutations in \(\Av_n^k(1324)\) are decomposable or almost decomposable by \Cref{thm:removepoint}, so our mappings combine to an injection
\begin{equation*}
  \Av_n^k(1324) \longrightarrow \Av_{n+1}^k(1324).
\end{equation*}
In particular, this verifies \Cref{conj:1324anders} for all \(k \leq 2n-7\). 

First of all, any \(\pi \in \mathcal D_n^k\) can be written in the form
\begin{equation*}
  \pi = \pi^{(1)} \oplus {\underbrace{\vphantom{i_i}1 \oplus \ldots \oplus 1}_{m \text{ times}}} \oplus \pi^{(2)}
\end{equation*}
for some \(m \geq 0\) by \eqref{eq:1324 form}. This allows us to set
\begin{equation*}
  g(\pi) = \pi^{(1)} \oplus {\underbrace{\vphantom{i_i}1 \oplus \ldots \oplus 1}_{m+1 \text{ times}}} \oplus \pi^{(2)} \in \mathcal D_{n+1}^k.
\end{equation*}
The image \(g(\mathcal D_n^k)\) is exactly the set of all permutations in \(\Av_{n+1}^k(1324)\) with at least three components, and \(g\) is clearly injective. Note that when \(n \geq k + 2\), \(g\) is a bijection.

We will define \(f\) in a similar way. Let \(\pi \in \mathcal A_n^k\).
\begin{enumerate}
  \item If \(\pi \delete \pi_1\) is decomposable, let \(f(\pi)\) be the permutation with \(f(\pi)_1 = \pi_1\) and \(f(\pi) \delete \pi_1 = g(\pi \delete \pi_1)\). \label{inj:delete pi1}
  \item If \(\pi \delete 1\) is decomposable, let \(f(\pi) = f(\pi^{-1})^{-1}\). \label{inj:delete 1}
  \item Otherwise, let \(f(\pi) = ({\rc} \circ f \circ {\rc})(\pi)\), where \(\rc(\pi)\) is the reverse-complement. \label{inj:delete other}
\end{enumerate}

\begin{remark} \label{rmk:f properties}
  The mapping \(f\) preserves \(1324\)-avoidance and the number of inversions. Moreover, the permutations in its image have at most two components.
\end{remark}

\begin{example}
  Consider the permutation \(\pi = 35126874 \in \Av_8^8(1324)\). Here are the plots of \(\pi\) and \(\rc(\pi)\).
  \begin{center}
    \begin{tikzpicture}[scale=0.38]
      \clip (0.5,-1) rectangle (8.5,8.5);
      \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (8.5,8.5);

      \foreach \x\y in {1/3,2/5,3/1,4/2,5/6,6/8,7/7,8/4}
        \node at (\x,\y-0.004) {\pt};
      
      \node at (4.5,-0.5) {\(\pi\)};
    \end{tikzpicture}
    \hspace{5mm}
    \begin{tikzpicture}[scale=0.38]
      \clip (0.5,-1) rectangle (8.5,8.5);
      \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (8.5,8.5);

      \foreach \x\y in {1/5,2/2,3/1,4/3,5/7,6/8,7/4,8/6}
        \node at (\x,\y-0.004) {\pt}; 
      
      \node at (4.5,-0.5) {\(\rc(\pi)\)};
    \end{tikzpicture}
  \end{center}
  We can see that \(\pi \delete 1\) and \(\pi \delete \pi_1\) are both indecomposable, whereas \(\pi \delete \pi_n\) is decomposable. Therefore \(\rc(\pi) \delete \rc(\pi)_1\) is decomposable. The following figure shows the permutations \(\rc(\pi) \delete \rc(\pi)_1\), \(g(\rc(\pi) \delete \rc(\pi_1))\) and \((f \circ {\rc})(\pi)\). 
  \begin{center}
    \begin{tikzpicture}[scale=0.38]
      \fill[blue!15] (0.5,0.5) rectangle (3.5,3.5);
      \fill[blue!15] (3.5,3.5) rectangle (7.5,7.5);

      \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (7.5,7.5);

      \foreach \x\y in {1/2,2/1,3/3,4/6,5/7,6/4,7/5}
        \node at (\x,\y-0.004) {\pt}; 
      
      \node at (4,-1.5) {\(\rc(\pi) \delete \rc(\pi)_1\)};
    \end{tikzpicture}
    \hspace{5mm}
    \begin{tikzpicture}[scale=0.38]
      \fill[blue!15] (0.5,0.5) rectangle (3.5,3.5);
      \fill[blue!15] (3.5,3.5) rectangle (4.5,4.5);
      \fill[blue!15] (4.5,4.5) rectangle (8.5,8.5);

      \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (8.5,8.5);

      \foreach \x\y in {1/2,2/1,3/3,4/4,5/7,6/8,7/5,8/6}
        \node at (\x,\y-0.004) {\pt}; 

      \node at (4.5,-1) {\(g(\rc(\pi) \delete \rc(\pi)_1)\)};
    \end{tikzpicture}
    \hspace{5mm}
    \begin{tikzpicture}[scale=0.38]
      \fill[blue!15] (1.5,0.5) rectangle (4.5,3.5);
      \fill[blue!15] (4.5,3.5) rectangle (5.5,4.5);
      \fill[blue!15] (5.5,5.5) rectangle (9.5,9.5);

      \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (9.5,9.5);

      \foreach \x\y in {1/5,2/2,3/1,4/3,5/4,6/8,7/9,8/6,9/7}
        \node at (\x,\y-0.004) {\pt}; 

      \node at (5,-0.5) {\((f \circ {\rc})(\pi)\)};
    \end{tikzpicture}
  \end{center}
  Finally, we get the following.
  \begin{center}
    \begin{tikzpicture}[scale=0.38]
      \node at (-10,5) {\(f(\pi) = ({\rc} \circ f \circ {\rc})(\pi) = 341267985 \quad = \)};

      \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (9.5,9.5);

      \foreach \x\y in {1/3,2/4,3/1,4/2,5/6,6/7,7/9,8/8,9/5}
        \node at (\x,\y-0.004) {\pt};
    \end{tikzpicture}
  \end{center}
\end{example}
\begin{theorem} \label{thm:injective}
  The function \(f: \mathcal A_n^k \to \Av_{n+1}^k(1324)\) is injective for all \(n\) and \(k\). Furthermore, \(\av_n^k(1324) \leq \av_{n+1}^k(1324)\) whenever \(k \leq 2n-7\).
\end{theorem}

This is not obvious; a complete proof is available in \cite{linusson_1324_2024}.

\section{Enumerating the difference} \label{sec:difference}

The goal of this section is to describe the set of permutations 
\begin{equation*}
  \mathcal R_{n+1}^k \coloneqq \Av_{n+1}^k(1324) \setminus \big(g(\mathcal D_n^k) \cup f(\mathcal A_n^k)\big)
\end{equation*}
for all \(k \leq 2n - 7\). We will assume that \(k \leq 2n - 7\) throughout.

\(\mathcal R_{n+1}^k\) consists of the following collections; for details, see \cite{linusson_1324_2024}.

\begin{enumerate}[label=(\alph*)]
  \item \label{diffclasses: corner} Permutations \(\sigma \in \Av_{n+1}^k(1324)\) with \(\sigma_1 = n+1\) or \(\sigma_{n+1} = 1\). They are enumerated by \([x^k]\big(2 x^n P(x)^2 \big)\).
  \item \label{diffclasses: 2-n+1} Permutations \(\sigma \in \Av_{n+1}^k(1324)\) with \(\sigma_2 = n+1\) or \(\sigma_{n+1} = 2\). These permutations are enumerated by \([x^k]\big(2 x^{n-1} P(x)^2 \big).\)
  \item \label{diffclasses: 2 comp} Permutations \(\sigma \in \Av_{n+1}^k(1324)\) such that \(\sigma \delete 1\), \(\sigma \delete \sigma_1\), \(\sigma \delete (n+1)\) and \(\sigma \delete \sigma_{n+1}\) all have at most two components. However, one can show no such permutations exist.
  \item \label{diffclasses: last} Let \(h\) denote the natural extension of the left-inverse of \(f\) to all permutations \(\sigma \in \Av_{n+1}^k(1324)\) such that \(\comp(\sigma) \leq 2\), \(\sigma_1 \neq n+1\), \(\sigma_{n+1} \neq 1\) and
  \begin{equation*}
    \max\{\comp(\sigma \delete i) : i = 1, n+1, \sigma_1, \sigma_{n+1} \} \geq 3.
  \end{equation*}
  This last part of \(\mathcal R_{n+1}^k\) consists exactly of the permutations \(\sigma \in \Av_{n+1}^k(1324)\) with \(\sigma_1,\sigma_2 \neq n+1\) and \(\sigma_{n+1} \neq 1,2\), such that \(f(h(\sigma)) \neq \sigma\). One can prove that (up to symmetry), all of these permutations have the structure described in \Cref{fig:last part of difference}, leading to the enumeration \([x^k]\big(2 x^{n-1} P(x)^2\big).\)
\end{enumerate}

\begin{figure}[!ht]
  \begin{minipage}{0.38\textwidth}\hfill
    \begin{tikzpicture}[scale=0.9]
      \draw[fill=blue!40] (1,1) rectangle (3,3);
      \draw[fill=blue!40] (4,5) rectangle (6,7);

      \fill[red!40] (0.5,3) rectangle (6.5,4);

      \draw (0.5,1) rectangle (6.5,7);
      
      \foreach \y in {3,3.5,4,5}
        \draw (0.5,\y) -- (6.5,\y);

      \foreach \d in {-0.1,0,0.1}
        \node[dot, minimum size=1pt] at (3.5+\d,4.5+\d) {};
      \foreach \x\y in {3.2/4.2,3.8/4.8}
        \node at (\x,\y-0.004) {\scriptsize\upt};
      \foreach \x\y in {0.75/3.25,6.25/3.75}
        \node at (\x,\y-0.004) {\pt};

      \node at (2,2) {\(\tau^{(1)}\)};
      \node at (5,6) {\(\tau^{(2)}\)};

      \node at (0.8,6.7) {\(\sigma\)};
    \end{tikzpicture}
  \end{minipage}
  \begin{minipage}[t]{0.6\textwidth}
    \caption{A permutation \(\sigma\) satisfying the assumptions of \ref{diffclasses: last}. Note that \(\tau \coloneqq \sigma \delete \{\sigma_1, \sigma_{n+1}\}\) is decomposable, and that \(\sigma_1\) is placed just above the first component of \(\tau\), with \(\sigma_{n+1}\) one step higher. It is easy to check that \(f(h(\sigma)) \neq \sigma\).}
    \label{fig:last part of difference}
  \end{minipage}
\end{figure}

The collections described above are disjoint and their union is \(\mathcal R_{n+1}^k\), so we get
\begin{equation*}
   \av_{n+1}^k(1324) - \av_n^k(1324) = |\mathcal R_{n+1}^k| = [x^k] \big(2(2+x) x^{n-1} P(x)^2\big).
\end{equation*}
This proves \Cref{thm:1324}.

\section{Further directions and conjectures} \label{sec:discussion}

This section contains discussion of three topics: extending our method; repeated differences of the numbers \(\av_n^k(1324)\); and the unimodality of the sequences
\begin{equation*}
  \av_n^0(1324), \ \ \av_n^1(1324), \ \ \ldots, \ \ \av_n^{\binom n 2}(1324).
\end{equation*}

\paragraph{Extending almost-decomposability.} A natural idea is to delete more than one point from the boundary of the plot of a permutation to make it decomposable. For example, one could imagine handling our earlier counterexample \(\pi = 3612745\) by deleting entries \(1\) and \(2\). However, some permutations with as few as \(2n-5\) inversions behave poorly in this respect. One example is
\begin{equation*}
    \pi = [3, 4, \ldots, n-4, n-2, 1, n, 2, n-1, n-3].
\end{equation*}
Consider the case of \(n = 7\); it is not clear which points should be deleted to make \(\pi\) decomposable.
\begin{center}
  \begin{tikzpicture}[scale=0.38]
    \draw[step=1, thick, \gridcolor] (0.5,0.5) grid (7.5,7.5);
    \foreach \x\y in {1/3,2/5,3/1,4/7,5/2,6/6,7/4}
      \node at (\x,\y-0.004) {\pt};
    \foreach \x\y in {1/1,1/2,2/1,2/2,2/4,4/2,4/4,4/6,6/4}
      \node[dot, blue!40, minimum size=6pt] at (\x,\y) {};
    \node at (-4.2,4) {\(3517264 \quad = \)};
  \end{tikzpicture}
\end{center}

\begin{question}
  Is there a generalization of almost-decomposability by which the upper bound \(2n-7\) could be improved?
\end{question}

\begin{question}
  Does almost-decomposability have other uses?
\end{question}


\paragraph{Repeated differences.} We want to understand the numbers $\av_n^k(1324)$ also for $k>2n-7$.  Studying the numbers when $k\le 3n-15$ we have found a tantalising pattern. We here extend the study of differences from \Cref{thm:1324} to repeated differences. In what follows we will write $\av_n^k$ for $\av_n^k(1324)$. Let %For a fixed $r\ge 0$, the following always seems to be constant for $n\ge 10+r$:
\begin{equation}\label{eq:3diff}
  \begin{aligned}
    b_{r,n} &\coloneqq \big(\av_{n+3}^{2n+r-3}-\av_{n+2}^{2n+r-3}\big)-
    \big(\av_{n+2}^{2n+r-4}-\av_{n+1}^{2n+r-4}\big) \\
    &\quad -\big(\big(\av_{n+2}^{2n+r-5}-\av_{n+1}^{2n+r-5}\big)-
    \big(\av_{n+1}^{2n+r-6}-\av_{n}^{2n+r-6}\big)\big).
  \end{aligned}
\end{equation}
For example, by inspecting Table \ref{tab:1324 difference diagram},
\begin{equation*}
    b_{0,8}={\underbrace{\vphantom{j_{j_j}}\big(\av_{11}^{13} - \av_{10}^{13}\big)}_{= 100}} 
    - {\underbrace{\vphantom{j_{j_j}}\big(\av_{10}^{12} - \av_9^{12}\big)}_{= 92}}
    - \big({\underbrace{\vphantom{j_{j_j}}\big(\av_{10}^{11} - \av_9^{11}\big)}_{=50}} 
    - {\underbrace{\vphantom{j_{j_j}}\big(\av_9^{10} - \av_8^{10}\big)}_{=46}}
    \big) = 4.
\end{equation*}
Anders Claesson has kindly provided us with data of $\av_n^k$ for $k,n\le 45$, and it appears that for a fixed \(r \geq 0\), \(b_{r,n}\) is constant for all \(n \geq 10 + r\). Up to \(r = 9\), these constants are
\begin{equation*}
  4,8,14,28,52,88,150,244,390,612.
\end{equation*}


\begin{conjecture}\label{conj:3diff} 
  The numbers $b_{r,n}$ are equal for a fixed $r$ with $n\ge 10+r $ (call them $b_r$) and they satisfy
  \begin{equation*}
      \sum_{r \geq 0} b_rx^r = \frac{2(1+x)(2-x^2)}{1-x}P(x)^2,
  \end{equation*}
  where $P(x)$ is again the generating function for the partition numbers.
\end{conjecture}
 
\begin{remark} 
  To guess the formula in \Cref{conj:3diff} one really only needs four numbers $b_0,b_1,b_2,b_3$ since the numerator is a degree 3 polynomial, but it is true for all 10 numbers we have.
\end{remark}
 
\begin{remark} 
  If \Cref{conj:3diff} is proven we could still not determine the numbers $\av_n^k$ for all $k\le 3n-15$ since we also would need starting values when $n=10+r$ of $\big(\av_{n+2}^{2n+r-5}-\av_{n+1}^{2n+r-5}\big) - \big(\av_{n+1}^{2n+r-6}-\av_{n}^{2n+r-6}\big)$. That sequence starts 
  \begin{equation*}
    12, 24, 41, 120, 274, 553, 1098, 2055.
  \end{equation*}
\end{remark}


\paragraph{Improved bounds and unimodality.} Let \(c \leq 1\) be a constant such that the maximal value of each sequence \(\big(\av_n^k(1324)\big)_k\) occurs with \(k \leq c \cdot \binom n2\), and assume that \Cref{conj:1324anders} is true. Then, using the same technique as in \cite[Theorem 17]{claesson_upper_2012}, we find that
\begin{equation*}
  L(1324) \leq \exp \big(\pi \sqrt{2c / 3} \big).
\end{equation*}
Incidentally, \(c = 21/23 \approx 0.913\) gives \(L(1324) \leq 11.6004\), which is in the range of the estimation from \cite{conway_1324-avoiding_2018}. Such a large improvement is unrealistic with the current approach. Indeed, large \(1324\)-avoiders generally have many inversions \cite{madras_random_2010}. Note that \(c > 0.813\), since \(c = 0.813\) gives \(L(1324) \leq 10.263\), contradicting the known lower bound \(10.27\).

\begin{question}
    Is there a constant \(c < 1\) such that the maximal value of each sequence \(\big(\av_n^k(1324)\big)_k\) occurs with \(k \leq c \cdot \binom n2\)?
\end{question}

This line of thinking leads to another natural question: is \(\av_n^k(1324)\) unimodal in \(k\)? It is well-known (see \cite{bona_combinatorial_2004} for a nice proof) that \(\big(s_n^k\big)_k\) is log-concave, where \(s_n^k\) denotes the number of all permutations (not required to avoid any pattern) of length \(n\) with \(k\) inversions. As far as we know, there are no similar nontrivial results for the pattern avoiding case. The sequences \((\av_n^k(1324)\big)_k\) are unimodal in the data we have, but we have not found a proof. Of special interest would be the positions of the `tops' of the unimodal sequences, due to the discussion above.

\begin{conjecture}
  The sequence \(\left(\av_n^k(1324)\right)_{k=0}^{\binom n2}\) is unimodal for each \(n\).
\end{conjecture}

\acknowledgements{We are grateful to Anders Claesson and Bjarki Ágúst Guðmundsson, who provided us with data for the numbers \(\av_n^k(1324),\) for \( k,n\le 45\) (see \url{https://akc.is/inv-mono/}). Anders Claesson furthermore correctly guessed the generating function \(R_n(x) = 2(2 + x)x^{n-1} P(x)^2\) for the differences \(\av_{n+1}^k(1324) - \av_n^k(1324)\).

Both authors were funded by the Swedish Research Council, VR, grant 2022-03875.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}