%% 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]{FPSAC2023}
\articlenumber{61}
%% 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{latexsym}
\usepackage{amsfonts,soul}
\usepackage{subfigure}
\usepackage{mathtools}

\usepackage{tikz}
\usetikzlibrary{intersections,patterns,arrows,decorations.pathreplacing}
\usepackage{epic, eepic}

%\newtheorem{algorithm}[theorem]{Algorithm}

\numberwithin{equation}{section}
\numberwithin{figure}{section}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{conjecture}{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{problem}{Problem}
\newtheorem{algorithm}[theorem]{Algorithm}

\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{fact}{Fact}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% BEGIN our macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\bino#1,#2,{\binom{#1}{#2}}

\newcommand\mfact[1]{\ensuremath{!_{#1}}}
\newcommand\cd{\cdot}
\newcommand\lra{\leftrightarrow}

\newcommand\bp{\mathbf{p}}
\newcommand\bs{\mathbf{s}}
\newcommand\bw{\mathbf{w}}
\newcommand\bc{\mathbf{c}}
\newcommand\bu{\mathbf{u}}

\newcommand\oc{\mathcal{O}}
\newcommand\cls{\mathcal{S}}
\newcommand\clsn{\mathcal{S}_n}

\newcommand\syt{{\sc{syt}}}

\DeclareMathOperator{\des}{\mathrm{des}}

\newcommand\disp{\displaystyle}

\newcommand\one{\ensuremath{-}}

\newcommand\NN{\mathbb N}
\newcommand\RR{\mathbb R}
\newcommand\calP{\mathcal{P}}

\newcommand\rd[1]{\textcolor{red}{#1}}
\newcommand\blu[1]{\textcolor{redwood}{#1}}
\newcommand\grn[1]{\textcolor{green}{#1}}

\newcommand\gapv{gap vector}
\newcommand\gapvs{gap vectors}
\newcommand\distv{distance vector}
\newcommand\distvs{distance vectors}
\newcommand\occset{\ensuremath{\mathsf{occset}}}

\newcounter{nextnum}
\setcounter{nextnum}{0}
\newcommand\nxt{\addtocounter{nextnum}{1}{\arabic{nextnum}}}

\newcommand\ppp{\ensuremath{p}}

\newcommand\oeis{{\sc oeis}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% END our macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% BEGIN our settings TO BE REMOVED
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand\mps[1]{\marginpar{\raggedleft\small\sf{\textcolor{red}{#1}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% END our settings TO BE REMOVED
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

%% define your title in the usual way
\title[Patterns, Processes, Moments]{A new perspective on positivity in (consecutive) permutation patterns}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[N. Blitvi\'c, M.S. Kammoun, E. Steingr\'imsson]{Natasha Blitvi\'c\thanks{\href{n.blitvic@qmul.ac.uk}{n.blitvic@qmul.ac.uk}. Partially supported by grant EP/V048902/1 from The Engineering and Physical Sciences Research Council and RPG-2020-103 from the Leverhulme Trust.}\addressmark{1}, Mohammed Slim Kammoun\thanks{\href{medslimkammoun@gmail.com}{medslimkammoun@gmail.com}. Partially supported by grant RPG-2020-103 from the Leverhulme Trust.}\addressmark{2}, \\ \and Einar Steingr\'imsson\thanks{\href{einar@alum.mit.edu}{einar@alum.mit.edu}.
% Partially supported by a Leverhulme Research Fellowship
  }\addressmark{3}}



%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematical Sciences, Queen Mary University of London, London UK  \\ \addressmark{2}Department of Mathematics and Statistics, Lancaster University, UK, and Institut de Math\'ematiques de Toulouse, Toulouse France \\\addressmark{3}Department of Mathematics and Statistics, University of Strathclyde, Glasgow UK}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% 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{We present a point of view on consecutive permutation patterns that interprets these in terms of (1) natural generalizations of the descent set of a permutation, (2) paths of a $k$-dependent point process, (3) refined clusters in the cluster method, and, surprisingly, (4) as conjectured moments of probability measures on the real line. At the heart of this paper is a recursive enumeration formula that allows us to get a grip on the aforementioned quantities and further enables us to formulate and numerically verify the conjecture (4), which provides a new unifying perspective on moment sequences arising from the study of permutation patterns.
%The interplay between combinatorics and probability 
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{permutation patterns, descent set, point processes, moment sequences}

%% 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]{biblatex}
\addbibresource{allrefs.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}\label{sec-intro}

There are times in mathematics, when the conditions are right and a certain kind of threshold has been reached, that an idea crystalizes in plain sight. 
In the past several years, different groups of authors \cite{blit-stein-perms-moments,BEGM-stieltjes-avoiders,clisby-conway-guttmann-inoue,elvey-price-thesis,sokal-euler-springer-moment} have independently observed that several classes of integer sequences enumerating combinatorial objects, in particular permutations avoiding fixed permutation patterns, are moment sequences of positive Borel measures on the real line.

The Catalan numbers offer a canonical example. For concreteness, fix a 
permutation $\ppp\in S_3$. (Avoidance of permutation patterns of length three is well understood, in contrast to patterns of length four or greater.) We recall that for $\sigma\in S_n$ ($n\in\mathbb N$), \emph{{$\sigma$ avoids the classical permutation pattern $\ppp$}} if there are no indices $1\leq i<j<k \leq n$ such that the image of $(i,j,k)$ under $\sigma$ is order-equivalent to $\ppp$. (For example, the permutation $243165$, in the one-line notation, avoids the classical permutation pattern $\ppp=312$; in contrast, $352614$ fails to do so, containing an occurrence of $\ppp$ on indices (2,3,6), among others.) Combining the well-known enumeration result \cite{simion-schmidt} for patterns of length three with the famous integral representation of the Catalan numbers as the (even) moments of Wigner's semicircle law, we obtain that
$$
\#\{\sigma\in S_n\mid \sigma \text{ avoids } \ppp\}=\int_{-2}^2 x^{2n}\,\frac{\sqrt{4-x^2}}{2\pi}\,dx.
$$

Although no general conjecture has formally been published, it is fair to say there is 
belief among several aforementioned authors (including us), further reinforced by numerical evidence \cite{BEGM-stieltjes-avoiders,clisby-conway-guttmann-inoue,elvey-price-thesis}, that the numbers of permutations avoiding any given \emph{classical} permutation pattern give a moment sequences. If true, this conjecture would pave the way to more efficient asymptotics \cite{elvey-price-thesis} and place the study of permutation patterns within a broader probabilistic and combinatorial context \cite{blit-stein-perms-moments}. 
%\emph{But what of the consecutive patterns?}


\emph{\centering But what of the consecutive patterns?\\}


Even for consecutive patterns of length three, that is the patterns whose occurrence is predicated on the existence of a triple $(i,j,k)$ of now \emph{consecutive} indices, i.e.\ where $i=j-1=k-2$, the picture is significantly less clear. In particular, a straightforward computation of determinants (see \cite[p.\ 5486]{blit-stein-perms-moments}) shows that the sequence enumerating permutations avoiding the consecutive pattern 132 is
\underline{not} a moment sequence. This is in contrast to the consecutive pattern 123, which gives rise to moment sequences even in its distributional form, whenever the variable carrying the number of occurrences is specialized to a real number. (\cite[Corollary~4]{blit-stein-perms-moments})

%This is in contrast to the pattern 123, which gives rise to a moment sequence even in a two-parameter refined form (see \cite{blit-stein-perms-moments}).
 
 And yet, there is a general way of looking at consecutive permutation patterns that does seem to uniformly give rise to moment sequences.  {\bf Presenting this point of view}, as well as providing the {\bf enumerative formulas} that supply the numerical evidence to support this {\bf new conjecture}, are the main goals of this paper.

\subsection{A different look at consecutive permutation patterns}
In the following, we regard permutations as words $a_1a_2\ldots a_n$ on distinct integers, usually on the set $[n]:=\{1,2,\ldots,n\}$.  We recall that a \emph{descent} in a permutation is an $i$ such that $a_i>a_{i+1}$.  The \emph{descent set} of a permutation $\sigma$ is the set $\{i\,|\,a_i>a_{i+1}\}$, that is, the set of indices at which~$\sigma$ has descents.

In a seminal paper~\cite{gessel-viennot-bino-dets} Gessel and Viennot gave a formula, in terms of determinants, for the number of permutations of length $n$ with any given descent set (a special case of the celebrated Lindstr\"om-–Gessel-–Viennot Lemma). The descent set was later interpreted probabilistically by Borodin, Diaconis, and Fulman, as a sample path of a stationary one-dependent determinantal point process \cite{Borodin-Diaconis-Fulman}, providing a canonical example in a broader theory of such processes.
An obvious question that doesn't seem to have received much attention is what type of combinatorial or probabilistic structure is achievable when, instead of looking at descents,
we count permutations according to each starting point of an occurrence of a given \emph{consecutive pattern}.

In this paper we present a recursive formula for the number of permutations of length~$n$ that are \emph{covered} by an arbitrary given consecutive pattern $p$ of length $k$ with \emph{overlaps}~$m$ (which we now define), and provide explicit closed formulas for several
families of such patterns.

\begin{definition}
  We say that a consecutive pattern $p$ \emph{covers a permutation $\pi$ with overlaps~$m$} if there is a sequence of occurrences of $p$ in $\pi$ containing between them all letters of~$\pi$ and such that two successive occurrences in the sequence share exactly $m$ letters of $\pi$.  We say that the occurrences in this sequence are \emph{prescribed by the covering by $p$ with overlaps~$m$.}
\end{definition}
 As an example, the permutation $14263758$ is covered by $1324$ with overlaps 2, since  $1426$,  $2637$  and  $3758$ are all occurrences of 1324. Note that permutations covered by a pattern form a \emph{cluster}, in the sense of the cluster method of Goulden and Jackson, although the method as normally used in relation to consecutive permutation patterns (see e.g. \cite{beaton-conway-guttmann-consec-patt-av-4-5,elizalde-noy, Elizalde-Noy-2012}) does not keep track of the positions of the occurrences of a pattern.

It is important to highlight that we count permutations that have occurrences of a pattern $p$ in prescribed positions, but disregard whether $p$ might occur in more places. (In other words, we count permutations with occurrences in "at least" the prescribed positions.) This is the natural approach from the point of view of point processes. Indeed, our enumerative formula gives the \emph{correlation functions for a stationary k-dependent point process on positive integers} that encodes the occurrences of consecutive patterns occurring in uniformly distributed permutations. Of course, whether it is possible to have additional occurrences of a pattern depends on the length of the pattern $p$, the length of the overlaps and the \emph{auto-correlation} of $p$, that is, the maximum possible overlap of two occurrences of $p$ in a permutation.  In order for a pattern $p$ of length $k$ to 
possibly occur in more places in a permutation than those prescribed by overlaps $m\geq 1$, $p$ must have auto-correlation at least $(k+m)/2$.

Furthermore, our formula in \cref{thm-main-formula} requires every letter of a permutation to belong to an occurrence of the pattern and that two successive occurrences overlap in the permutation. 
However, allowing gaps between occurrences, or two occurrences being
adjacent without overlap, simply adds trivially computed multiplicative
factors to the formula (see remark following the main theorem). The formula can also be extended to count permutations with the pattern occurring in any set of positions, rather than at regular intervals.

The proof of \cref{thm-main-formula}  is based on a generalization of the `positive approach' of Baxter, Nakamura and Zeilberger~\cite{bax-nak-zeil-consec}. They keep track only of the number of occurrences of a pattern, but not their positions (which are essential here).  Also worth noting is a similar argument preceding Equation~(1) in Section~2.1 in~\cite{beaton-conway-guttmann-consec-patt-av-4-5}.  Implicit in our argument, in the special case where the overlap is $1$, is what Elizalde conjectured~\cite[p.~123]{elizalde-upc-thesis} and was proved independently by Duane and Remmel~\cite[p.~31]{duane-remmel-overlap-patts-color-perms} and by Dotsenko and Khoroshkin~\cite[Theorem~28]{dotsenko-khoroshkin-shuffle-homology-consec-patt}, that the number of permutations of a given length with a given number of occurrences with overlap 1 depends only on the first and last letter of the pattern.  To be precise, they assume the auto-correlation of the pattern is 1, which implies that this counts all occurrences of the pattern, since two occurrences can overlap in at most one letter.

In addition to our main result we give as corollaries several results for some infinite families of patterns, and in some of these cases also bijective connections to other combinatorial structures.  There are some recurring themes 
here, such as the ``stretched factorials'' 
$$
n!_k:=\prod_{0\le i<n/k}^{}(n-ik)
$$
for different $k$.
Some of these results are listed in \cref{table-contain}. Among these sequences, there is a surprising number of well-known moment sequences, including the Catalan numbers (moments of the semicircle law), Fuss-Catalan numbers (corresponding to the so-called free Bessel laws), stretched factorials (associated with Gamma distributions), and others.
The recursive formula of \cref{thm-main-formula} in turn allows to efficiently compute the Hankel determinants \cite{Hamburger} of the lesser-known sequences arising from \cref{thm-main-formula}. What we observe appears to strongly support the following conjecture:


\begin{conjecture}\label{main-conj}
  Fix a consecutive permutation pattern $p$ of length $k$. Let $a_j^{(p,m)}$ be the number of permutations of length $k+j(k-m)$ covered by $p$ with overlaps $m$ ($m\leq k$).  Then, $(a_j^{(p,m)})_{j\geq 0}$ is the moment sequence of some probability measure on the real line. \end{conjecture}

We began investigating the positivity of these sequences based on intuition from noncommutative probability that 
suggested a notion of multiplication based on the `concatenation' of patterns. The subsequent numerical evidence afforded by \cref{thm-main-formula} greatly strengthens this intuition. 
%On a more elementary combinatorial level, the above conjecture begs the question of how the various moment sequences arising in our context
%may be expressed in terms of a single unifying framework, perhaps in the vein of \cite{blit-stein-perms-moments,sokal-zeng-masterpolys}. 
Ultimately, 
\cref{main-conj} provides a consistent perspective on the positivity of 
sequences arising from the study of consecutive permutation patterns, mirroring --- in a non-obvious way --- the behaviors observed for classical permutation patterns. Namely, whereas it is the \emph{avoidance} of \emph{classical}
permutation patterns that appears to give rise to familiar sequences such as the Catalan numbers and a host of other sequences all of which are conjectured to be 
moment sequences, it is the \emph{packing} of the occurrences of \emph{consecutive} permutation patterns that gives rise to the analogous positivity phenomena. 

This is an extended abstract of a paper in preparation
%~\cite{bks-paper}, 
in which we also study the universality properties and other probabilistic aspects of the point processes defined by the positions of occurrences of a pattern in a random permutation.

\section{Main results}\label{sec-results-consec-wilf-classes}

We call a prefix (resp. suffix) of length $m$ an \emph{$m$-prefix (resp. $m$-suffix)}.  Note that a pattern covering with overlaps $m$ must have $m$-suffix \emph{order isomorphic} to its $m$-prefix, that is, the letters of the $m$-suffix must appear in the same order of size as those of the $m$-prefix.

\begin{lemma}
  The number of permutations of length $n$ covered by a pattern $p$ with overlaps~$m$ 
depends only on the $m$-prefix and $m$-suffix of $p$.
\end{lemma}
\begin{proof}\label{only-pref-suff}
  When $m\ge2k$, where $k$ is the length of $p$, the result is obvious because $p$ is then determined by its  $m$-prefix and $m$-suffix. Suppose now that  $m<2k$.   Given a permutation $\sigma$ covered by $p$ with overlaps $m$, let $A_i$ be the segment of~$\sigma$ between the $m$-prefix and $m$-suffix of the $i$-th occurrence of $p$ prescribed by the covering with overlaps $m$.  Any dependencies between the possible letters in $A_i$ and $A_{i+1}$ are determined solely by the $m$-prefix and $m$-suffix of $p$, and the ordering of the letters in each $A_i$ is uniquely determined by the segment $M$ of $p$ between its $m$-prefix and $m$-suffix.  Let $p'$  be a pattern of the same length as $p$, with the same $m$-prefix and $m$-suffix as $p$, but with $M'$ as its segment between these.  A bijection taking a permutation $\sigma$ covered by $p$ with overlaps~$m$ to a permutation $\sigma'$ covered by $p'$ with overlaps $m$ simply permutes the letters of each $A_i$ by the permutation that takes $M$ to $M'$.
\end{proof}

We now prove the main theorem of this paper, giving a recursive formula for computing the number of permutations of a given length that are covered by a given pattern with overlaps $m$.  For simplicity we assume the $m$-prefix (and thus the $m$-suffix) of the pattern in question is increasing, but this restriction will be removed by a following lemma.  We also explain, in a following remark, that the theorem and proof can easily be extended to the case where the overlaps are allowed to vary in length.

\begin{theorem}\label{thm-main-formula}
 Let $p$ be a pattern of length $K\ge2m$ with prefix $\bp=p_1p_2\ldots p_m$ and 
suffix $\bs=p_{m+1}p_{m+2}\ldots p_{2m}$, where $p_1<p_2<\cdots<p_m$ and $p_{m+1}<p_{m+2}<\cdots<p_{2m}$.

Let $\pi_i$ be the place of the $i$-th smallest letter in the concatenated word 
$\bp\bs=p_1p_2\ldots p_{2m}$, and let $\pi_0=0$ and $\pi_{2m+1}=2m+1$.

Let $\ell_0=0$, $\ell_{2m+1}=n+1$, where $n=K+j(K-m)$.

Let $p_0=0$ and $p_{2m+1}=K+1$.

Let $L=\ell_{m+1}\ell_{m+2}\ldots\ell_{2m}$.

Let $g_{j}(L)$ be the number of permutations of length $K+j(K-m)$ with $p$-overlap $m$ and  ending with $L$.

Then $g_0(\bs)=1$, $g_0(L)=0$ if $L\ne\bs$, and for $j\ge0$ we have
{\small
\begin{equation}\label{eq-master}
  g_{j+1}(L)=\mkern-12mu
  {\sum_{p_1\le\ell_1<\ell_2<\cdots<\ell_m}}\mkern-30mu
  g_j(\ell_1-(p_1-1),\ell_2-(p_2-2),\ldots,\ell_m-(p_m-m))
  \prod_{i=0}^{2m}\binom{\ell_{\pi_{i+1}}-\ell_{\pi_i}-1}{p_{\pi_{i+1}}-p_{\pi_i}-1}.  
\end{equation}
}
%
Consequently, letting $h_j$ be the number of permutations of length $n=K+j(K-m)$ covered by $p$ with overlaps $m$, we have
\begin{equation}
  \label{eq-master-sum}
h_j=\sum_Lg_j(L),  
\end{equation}
where $L$ runs over all sequences $\ell_1,\ell_2,\cdots,\ell_m$ with 
$1\le\ell_1<\ell_2<\cdots<\ell_m\le K+j(K-m)$.
\end{theorem}

\begin{proof}
  We prove this by induction on $j$, the base case, when $j=0$, being $g_0(L)=1$ if and only if $L=\bs$, since there is precisely one permutation of length $K$ with an occurrence of the pattern $p$, namely the permutation consisting of $p$ itself.
  
  In order to construct a permutation of length $K+(j+1)(K-m)$ covered by $p$
  with
overlaps~$m$ and ending with $L=\ell_{m+1}\ell_{m+2}\ldots\ell_{2m}$, let
$\oc=\oc_F\oc_M\oc_L$ be the word consisting of the last occurrence of~$p$ in
such a permutation $\sigma$, and such that both $\oc_F$ and $\oc_L$ have
length $m$.  We first analyze the possible choices of letters in $\sigma$
that constitute $\oc_M$.

Let $a<b$ be two letters in $\oc$ that belong to the union of $\oc_F$ and $\oc_L$ and such 
that no letter $c$ in $\oc_F$ or $\oc_L$ satisfies $a<c<b$.  Thus, $a=\ell_{\pi_i}$ and $b=\ell_{\pi_{i+1}}$ for some $i$, where $\pi$ is the permutation defined in the statement of the theorem.
However, there may be letters in $\oc_M$ that lie between $a$ and $b$ in size.  In fact, there must be precisely $p_{\pi_{i+1}}-p_{\pi_i}-1$ such letters in $\oc_M$, in order for $\oc$ to be an occurrence of $p$.  Moreover, these letters can be any of those that lie strictly between $\ell_{\pi_i}$ and $\ell_{\pi_{i+1}}$ in size. In addition, there may be letters in $\oc_M$ that are smaller or greater than all letters in $\oc_F$ and $\oc_L$, which is taken care of by the definitions of $\pi_0,\pi_{2m+1}$ etc. There are therefore $\prod_{i=1}^{2m}\binom{\ell_{\pi_{i+1}}-\ell_{\pi_i}-1}{p_{\pi_{i+1}}-p_{\pi_i}-1}$ possible choices for the letters in $\oc_M$.  Having thus chosen the letters to form $\oc_M$ there is only one way to order them so that they will form the part of an occurrence of $p$ that lies between the $m$-prefix and the $m$-suffix of that occurrence.

In order to complete the construction of the permutation $\sigma$ we must construct its prefix $\sigma'=\sigma_1\sigma_2\ldots\sigma_{K+j(K-m)}$, that is, $\sigma$ with $\oc_M$ and $\oc_L$ removed.  This $\sigma'$ has $p$-overlaps $m$, and must end in an increasing sequence $L:\ell_1<\ell_2<\cdots<\ell_m$. If we standardize $\sigma$ to consist of the letters $\{1,2,\ldots,K+j(K-m)\}$ then the sequence $L$ becomes $\ell_1-(p_1-1),\ell_2-(p_2-2),\ldots,\ell_m-(p_m-m)$, since there are precisely $p_i-i$ letters in $\oc_M$ and $\oc_L$ that are smaller than $\ell_i$.  By the inductive hypothesis, there are precisely $g_j(\ell_1-(p_1-1),\ell_2-(p_2-2),\ldots,\ell_m-(p_m-m))$ such $\sigma'$, which establishes
identity~(\ref{eq-master}), and equation~(\ref{eq-master-sum}) now follows readily.
\end{proof}

Thanks to the following lemma (which has a straightforward bijective proof, and can also be proved by showing the isomorphism of the corresponding \emph{cluster posets} introduced in~\cite{Elizalde-Noy-2012}), \cref{thm-main-formula} can be applied to any pattern $p$, regardless of the order of letters in its overlap prefix/suffix, since sorting the prefix and suffix, respectively, to increasing order doesn't change the number of permutations covered by the pattern in question with overlaps $m$.

\begin{lemma}\label{lem-overlap-pref-suff}
  Let $p=\bp \bw\bs$ be a pattern where $\bp=p_1p_2\ldots p_m$ and 
$\bs=s_1s_2\ldots s_m$ are order isomorphic and $\bw$ is any permutation of the remaining letters.  Let $\bp'=p'_1p'_2\ldots p'_m$ be a permutation of $p_1p_2\ldots p_m$, let $\bs'=s'_1s'_2\ldots s'_m$ be  $s_1s_2\ldots s_m$ permuted in the same way and let $p'=\bp'\bw\bs'$.  Then the number of $n$-permutations covered by $p$ with overlaps $m$ equals the number of $n$-permutations covered by $p'$ with overlaps $m$.
\end{lemma}

\begin{remark}\label{rem-arb}
  Although \cref{thm-main-formula} and its proof are stated in terms of fixed size overlaps, it is easy to see how these can be extended to the enumeration of permutations with occurrences of the pattern $p$ in arbitrary prescribed positions.  Namely, for each step in the recursion we can simply specify the length of the overlap  and adjust the length of the sequence $\ell_1,\ell_2,\ldots,\ell_m$ accordingly.   Also, if two consecutive occurrences of the pattern aren't required to overlap then we can arbitrarily choose the set of letters to form the part of the permutation up to the end of the first of these occurrences (and recursively if there are more such non-overlaps), and we can choose and order arbitrarily letters to fill positions that are not required 
to belong to an occurrence. (Recall that we count occurrences in ``at least" the prescribed positions, i.e. we allow for more occurrences than those specified.)  In such cases, where not all pairs of successive occurrences are required to overlap, this breaks the problem into smaller pieces of overlapping occurrences, to which our formula can be applied, and segments of letters in a permutation that are not required to belong to an occurrence. We then need to multiply by the appropriate multinomial coefficients, corresponding to choices of letters for each of these pieces, and the appropriate factorials for those segments that are not required to belong to an occurrence, since the letters of those segments can be ordered arbitrarily.
\end{remark}

Finally, note that the usual symmetries when enumerating consecutive permutation 
patterns --- reverse, complement and their composition --- apply here, in addition to \cref{lem-overlap-pref-suff} and the following:

\begin{lemma}\label{pref-suff-wilf}
Let $p=\bp\bw\bs$ be a pattern whose prefix $\bp$ and suffix $\bs$ have the
same length $m$.  The number of permutations of length $n$ covered by $p$ with
  overlaps $m$ equals the number of permutations of length $n$ covered by
  $p'=\bs\bw\bp$ with overlaps $m$.
\end{lemma}
\begin{proof}
Given a permutation $\sigma$ covered by $p$ with overlaps $m$, let 
$\sigma=p_1w_1s_1\ldots p_jw_js_j$, where, for each $i$, $p_iw_is_i$ and $s_iw_{i+1}p_{i+1}$ are occurrences of $p$, such that each $p_i$ and each~$s_i$ is an $m$-prefix and/or $m$-suffix of an occurrence of $p$.  Then $\sigma'=s_jw_jp_j\ldots s_1w_1p_1$ is a permutation covered by $p'$ with overlaps $m$ and this process is clearly invertible.
\end{proof}


\section{Special cases}

We now highlight some of the interesting sequences that can be obtained as specializations of \cref{thm-main-formula}.  Some of these have been obtained previously by other authors (or are easily derived from such results).

\begin{proposition}\label{prop-1-and-last}
  Let $p=p_1p_2\ldots p_k$ be a pattern of length $k$ where $p_1=1$ and let $d=k-p_k$. 
The number of permutations of length $n=k+j(k-1)$ covered by $p$ with overlaps~1 is
$$
\prod_{i=0}^j\binom{i(k-1)+d}{d}.
$$
\end{proposition}

(See also Proposition~26 in~\cite{dotsenko-khoroshkin-shuffle-homology-consec-patt} and the poset in Figure 1 in~\cite{Elizalde-Noy-2012}, with $a=1$.)


\begin{corollary}\label{coro-1-k-1}
  With $j$, $n$ and $p$ as in \cref{prop-1-and-last}, if $p_k=k-1$ then the number 
of permutations of length $n$ in question is $(n-k+1)\mfact{k-1}$.
\end{corollary}


In the special case of \cref{prop-1-and-last} where $p_k=2$ the number 
sequence obtained equals that for partitions of a set of size $[(k-1)(j+1)]$ into $j+1$ blocks of size $k-1$ each, and we present a simple bijection (for $k+1$ instead of $k$). First, it is easy to see that a permutation 
of this kind must begin with the letter 1, and that the letter in place $k+1$ 
(common to the first and second occurrence of the pattern) must be~2. A straightforward argument shows that the letters in places $ik+1$, for $0\le i\le j+1$ are the right-to-left minima of such a permutation, that is, each is smaller than all the letters to its right.  Delete the first letter, 1, and split the resulting tail of the permutation into blocks of size $k$, so that the last letter of each block is 
  smaller than any letter to its right in the permutation.  Because each block is an occurrence of the tail of the pattern $p$, each block has its letters in a prescribed
order.  Sorting each block increasingly and keeping the order of blocks (and decrementing each letter by 1) gives a standard representation of a partition of the set $[n-1]$ into $j+1$ blocks of size $k$ each.  Conversely, any such partition is transformed into a permutation of this kind by reversing the above construction. As an example for $k=3$, $j=2$ (so $n=10$) and the pattern 1342, the above bijection gives:
$$
1\;8\;10\;2\;4\;5\;3\;7\;9\;6 \;\;\lra\;\;  8\;10\;2-4\;5\;3-7\;9\;6 \;\;\lra\;\;
791\!-\!342\!-\!685  \;\;\lra\;\; 179\!-\!234\!-\!568
$$



\begin{proposition}\label{prop-3142}
Let $p$ be the pattern $1(k+1)2(k+2)\ldots k(2k)$, where $k\ge2$.  The
number of permutations of length $n=2j+2k$ covered by $p$ with overlaps $2k-2$
is the Catalan number~$C_{j+1}$. 

This also holds for the pattern $q=(k+1)1(k+2)2\ldots(2k)k$.  The same is true when $(2k+1)$ is appended to $q$, with overlaps $2k-1$, and also when 1 is prepended to $p$ and each letter of $p$ incremented by 1, with overlaps $2k-1$. 
\end{proposition}



\begin{proposition}(See~\cite[Thm. 4.2]{Elizalde-Noy-2012})\label{prop-Fuss-Catalan}
The number of permutations of length $m+j(m+1)$ covered by $134\ldots(m+2)2(m+3)(m+4)\ldots(2m+1)$ with overlaps $m$ equals  $\frac{1}{mj+1}\binom{(m+1)j}{j}$.
\end{proposition}



\begin{proposition}\label{prop-14523}
  The number of permutations of length $5+3j$ covered by 
14523 with overlaps 2 is $(2j+1)\mfact{2}$.  %The same is true for 23514.
\end{proposition}



So far, the special cases considered involve regular overlaps. As previously mentioned, \cref{thm-main-formula} straightforwardly adapts to arbitrary overlap vectors, but for some classes of patterns, we observe a further decoupling that allows us to more directly `upgrade' the results obtained for regular overlaps to arbitrary ones. In particular, let $p$ be a pattern of length $k$ with auto-correlation at least 2. Tracking only the occurrences of $p$ arising from overlaps of sizes $1$ and $2$, we can express the vector of successive overlaps in terms of runs of 1s and 2s as $$\underline{1}_{r_1},\underline{2}_{q_1},\ldots,\underline{1}_{r_a},\underline{2}_{q_a}$$ where $a, q_1, r_2,q_2,\ldots, r_a\in\mathbb N$, $r_1,q_a\in\mathbb N_0$ and $\underline{x}_n$ is the word $x,\ldots,x$ of length $n$ (or the empty word when $n=0$).


\begin{proposition}\label{prop-arbitrary}
Let $p$ be a pattern of length $k$
of the form $1\sigma k$ with auto-correlation at least 2.
Let $\underline{1}_{r_1},\underline{2}_{q_1},\ldots,\underline{1}_{r_a},\underline{2}_{q_a}$ give the successive overlaps of $p$ in a permutation, counting only the overlaps of sizes 1 and 2.  Then the number of such permutations is given by the product $$N_{q_1}\cd N_{q_2}\cd\cdots\cd N_{q_a},$$
where $N_q$ is the number of permutations covered by $p$ with $q$ regularly-spaced overlaps of size 2.  
\end{proposition}
\begin{proof}

 Given a permutation $\sigma$ of this form we claim that the letter $\ell$ of the leftmost overlap of size 1 in $\sigma$ is greater than all letters preceding $\ell$.  Now, $\ell$ is clearly greater than all the letters in the occurrence of $p$ of which $\ell$ is the last letter.  Therefore, if this occurrence overlaps in two letters with a preceding occurrence, $\ell$ is larger than both letters in that overlap.  In particular, it is larger than the last letter of that overlap, which in turn is greater than all other letters in that preceding occurrence.  An inductive argument now shows that~$\ell$ must be greater than all the letters preceding it in $\sigma$.  An analogous argument shows that $\ell$ is smaller than all letters following it in $\sigma$.

This determines which subset of letters of $\sigma$ belongs to each of the segments between successive 1-overlaps in $\sigma$.  A segment between two successive 1-overlaps is thus a permutation covered by $p$ with overlaps 2, whose number is $N_i$ where $i$ is the number of 2-overlaps in that segment.  Since the ordering of letters in such a segment is independent of the ordering in any other such the proof follows. 
\end{proof}

Therefore, for $p=1324$, for example, which can have overlaps of sizes 1 and 2 only, we obtain the full analogue of the descent set where we count permutations with occurrences of $p$ in arbitrary prescribed positions, using \cref{prop-3142}.  This corollary can also be deduced from arguments in the proof of Thm.~4.1 in~\cite{Elizalde-Noy-2012}:

\begin{corollary}
  The number of permutations $\sigma$ with occurrences of the consecutive pattern 1324 
prescribed by the overlaps $\underline{1}_{r_1},\underline{2}_{q_1},\ldots,\underline{1}_{r_a},\underline{2}_{q_a}$ equals the following product of Catalan numbers:
$$
C_{q_1+1}\cd C_{q_2+1}\cd\cdots\cd C_{q_a+1}.
$$ 
\end{corollary}

\noindent (For non-overlapping occurrences, the picture is even simpler; see \cref{rem-arb}.)

\section{Moment Sequences}

Several of the families of sequences outlined in the previous sections are moment sequences of known probability measures. Among this company, we again find the Catalan numbers (of course), as well as the following:


%\begin{proposition}\label{prop-1-k-1}
%Fix $k\in\mathbb N$. The sequence $(n-k+1)\mfact{k-1}$, for 
%$n=k,2k,\ldots$ (see \cref{coro-1-k-1}), gives moments of the Gamma distribution with shape parameter $1/k$ and scale parameter $k$.
%\end{proposition}

\begin{proposition}\label{prop-1-k-1}
Fix $k\in\mathbb N$. The sequence $(n-k+1)\mfact{k-1}$, for 
$n=k,2k,\ldots$ (see \cref{coro-1-k-1}), is the moment sequence of the probability measure on the real line with density
$\displaystyle f(x)=x^{1/k-1}e^{-x/k}k^{-1/k}(\Gamma(1/k))^{-1}.$
\end{proposition}


\begin{proposition}\label{prop-free-Bessel}
The number of permutations of length $m+j(m+1)$ covered by $134\ldots(m+2)2(m+3)(m+4)\ldots(2m+1)$ with overlaps $m$ (see \cref{prop-Fuss-Catalan}) is the moment sequence of the free multiplicative convolution of $m$ free-Poisson random variables (members of a broader family of the so-called \emph{free Bessel laws} \cite{Banica-Belinschi-Capitaine-Collins}).
\end{proposition}

While the aforementioned are fundamental laws from classical and free
probability, specializations of \cref{thm-main-formula}  also include a great number of sequences that are more difficult to characterize. Nevertheless, by allowing us to 
compute these sequences efficiently to a very high number of terms, \cref{thm-main-formula} enables us to at least numerically verify the positivity, up to a point, of the lesser-known sequences arising in this context by calculating their Hankel determinants.
The result is our \cref{main-conj} (see \cref{sec-intro}). 

Finally, note that while \cref{thm-main-formula} provides an enumeration formula for overlapping patterns, one can (more easily) derive results for the cases where patterns are not overlapping, but are still required to occur at regular intervals. Concretely, consider permutations of length $n=k+j(k-m)$ such that a fixed pattern $p$ of length $k$ occurs with overlaps $m\leq 0$, that is, at indices $1,k+1+m,2k+1+m,\ldots$. Recall that we count permutations with patterns occurring "at least" at specified positions; that is, we do not prohibit further occurrences of $p$, beyond the prescribed ones. As a result, regardless of the choice of the pattern, the number of permutations is simply 
$\frac{(k+j(k-m))!}{{k!}^{j+1}}$, 
which can be expressed as the integral
$$\int_0^\infty  y^j  (C y^\frac{m+1}{k-m}e^{ (k!y)^{\frac 1{k-m}} }) dy,$$
where $C>0$. This is clearly a moment sequence. In fact, for $m=0$, we recognize here the moments of the random variable $Y=\frac{X^k}{k!}$ with $X$ a rate-one exponential. 

We do not yet understand the apparent positivity of sequences arising from the various ways of counting permutation patterns (avoiders of classical permutation patterns, packings of consecutive permutation patterns, and perhaps other formulations still to be discovered). Yet the fundamental nature of 
the measures we observe and consistency of the numerical evidence strongly suggest that there is interesting mathematics at play.



\begin{table}[!h]
\centering
  \small
\begin{tabular}{|c|c|c|c |c|c|c|c|} 
 \hline
 pattern & overlaps 1 & overlaps 2 & overlaps 3 \\
  \hline
  \hline
  $312$ & {$(n-2)\mfact{2}$}  & &\\\hline
  \hline
 $1243$  & $(n-3)\mfact{3}$ \blu{Coro. \ref{coro-1-k-1}}  &  \one  &  \\\hline 
 $1324$  & 1 & $C_{j+1}$ \blu{Prop. \ref{prop-3142}} &    \\\hline
 $1342$   &  $\displaystyle\frac{(3j)!}{j!(3!)^j}$ & \one  &      \\\hline
 $1423$   & $(n-3)\mfact{3}$ \blu{Coro. \ref{coro-1-k-1}} & 1  &     \\\hline
 $2143$   & ~ $1, 9, 234, 12204, 1067040,\ldots
$ & 1 &    \\\hline
 $2413$    &  ~ $1, 9, 234, 12204, 1067040,\ldots$ & $C_{j+1}$, \blu{Prop. \ref{prop-3142}}  &   \\\hline
  \hline
 \hline
 $12354$  & $(n-4)\mfact{4}$ \blu{Coro. \ref{coro-1-k-1}}  & \one & \one    \\\hline
 $12435$  & 1 & 1 & \one     \\\hline
 $12453$  &$\prod_{i=0}^j\binom{4i+2}{2}$ \blu{Prop.~\ref{prop-1-and-last}} & \one  & \one     \\\hline
 $12534$  & $(n-4)\mfact{4}$  \blu{Coro. \ref{coro-1-k-1}}  & $(n-4)\mfact{3}$ & \one   \\\hline
 $13254$ & $(n-4)\mfact{4}$  \blu{Coro. \ref{coro-1-k-1}}   & \one & 1   \\\hline
 $13425$  & 1 & $\disp\frac{1}{2j+3}\binom{3j+3}{j+1}$ \blu{Prop. \ref{prop-Fuss-Catalan}}  & \one   \\\hline
 {$13452$} &$ \displaystyle\frac{(n-1)!}{(j+1)!(4!)^{j+1}}$   & \one  & \one \\\hline
 $13524$   & $(n-4)\mfact{4}$ \blu{Coro. \ref{coro-1-k-1}}  &  ~ $1, 6, 81, 1806, 57447, \ldots$
 & \one    \\\hline
 $14253$ &  \parbox{10.3em}{$\prod_{i=0}^j\binom{4i+2}{2}$\blu{Prop.~\ref{prop-1-and-last}}} &\one  ~& $C_{j+1}$ \blu{Prop. \ref{prop-3142}} \\\hline
 $14325$  & 1 & A274644 \,\,\cite{OEIS} & \one \\\hline
 $14523$  & \parbox{10.3em}{$\prod_{i=0}^j\binom{4i+2}{2}$ \blu{Prop.~\ref{prop-1-and-last}}}  & $(2j+1)\mfact{2}$ \blu{Prop. \ref{prop-14523}} & \one \\\hline
 $15234$  & $(n-4)\mfact{4}$ \blu{Coro. \ref{coro-1-k-1}} & 1 & \one \\\hline
 $15243$ &  \parbox{10.3em}{$\prod_{i=0}^j\binom{4i+2}{2}$ \blu{Prop.~\ref{prop-1-and-last}}} & \one & 1  \\\hline
 $15324$  & $(n-4)\mfact{4}$ \blu{Coro. \ref{coro-1-k-1}}  & $(n-4)\mfact{3}$  & \one   \\\hline
 $15423$  & \parbox{10.3em}{ $\prod_{i=0}^j\binom{4i+2}{2}$ \blu{Prop.~\ref{prop-1-and-last}}} & 1 & \one   \\\hline
 $21354$  &  ~ $1, 16, 816, 86528, 15661440,\ldots$  & 1 & \one    \\\hline
 $21453$  &   ~  $1, 30, 4440, 1867920,\ldots$  & 1 & \one \\\hline
 $21534$  &  ~  $1, 16, 816, 86528, 15661440,\ldots$ & \one & \one  \\\hline
 $21543$  &   ~  $1, 30, 4440, 1867920,\ldots$  & $(n-4)\mfact{3}$ & \one    \\\hline
 $23514$  &  ~ $1, 16, 816, 86528, 15661440,\ldots$& $(2j+1)\mfact{2}$ \blu{Prop. \ref{prop-14523}} & \one   \\\hline
 $24153$  &  ~  $1, 30, 4440, 1867920,\ldots$& \one & \one \\\hline
 $24513$  &  ~  $1, 30, 4440, 1867920,\ldots$  &  ~ $1, 6, 81, 1806, 57447, \ldots$& \one    \\\hline
 $25314$  &  ~ $1, 16, 816, 86528, 15661440,\ldots$ & A274644 \,\,\cite{OEIS} & \one     \\\hline
 $25413$  &  ~  $1, 30, 4440, 1867920,\ldots$& $\disp\frac{1}{2j+3}\binom{3j+3}{j+1}$ \blu{Prop. \ref{prop-Fuss-Catalan}}   & \one \\\hline

\end{tabular}
\caption{\label{table-contain} Enumerating sequences: equivalence classes of patterns of length $\leq 5$.}%
\end{table}



\vspace{-20pt}


\printbibliography



\end{document}