<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%% 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[final]{FPSAC2022}
%% 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{lipsum}

\usepackage{amssymb,amsfonts,amscd,amsthm}
\usepackage[all,arc]{xy}
\usepackage{enumerate, bbm}
\usepackage{mathrsfs}
\usepackage{tikz}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{color}%colors
\usepackage{graphicx}
\usepackage{enumitem} %Allows resuming enumeration and numbering by section
\graphicspath{ {TexImages/} }

%--------Theorem Environments--------
%theoremstyle{plain} --- default
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem{quest}[thm]{Question}
\newtheorem{prob}[thm]{Problem}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{obs}[thm]{Observation}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{exmp}[thm]{Example}

\theoremstyle{definition}
\newtheorem{defn}{Definition}

\hypersetup{
	colorlinks,
	citecolor=blue,
	filecolor=blue,
	linkcolor=blue,
	urlcolor=blue,
	linktocpage
}

\setenumerate[1]{label=\thesection.\arabic*.} %These two make your enumerated lists start with the section number
\setenumerate[2]{label*=\arabic*.} %Makes subparts labeled by numbers instead of letters.
\setlist[enumerate]{itemsep=2ex, topsep=2ex} %spaces out enumerate/itemize better
\setlist[itemize]{itemsep=2ex, topsep=2ex}

%Abbreviations
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Cn}{\mathbb{C}^n}
\newcommand{\E}{\mathbb{E}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\gam}{\gamma}
\newcommand{\Gam}{\Gamma}
\newcommand{\sig}{\sigma}
\newcommand{\ep}{\epsilon}
\newcommand{\lam}{\lambda}
\newcommand{\Lam}{\Lambda}
\newcommand{\om}{\omega}
\newcommand{\Om}{\Omega}
\newcommand{\kap}{\kappa}
\newcommand{\del}{\delta}
\newcommand{\Del}{\Delta}
\newcommand{\pa}{\partial}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\renewcommand{\l}{\left}
\renewcommand{\r}{\right}
\newcommand{\ot}{\leftarrow}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\quart}{\frac{1}{4}}
\renewcommand{\1}{\mathbbm{1}}
\newcommand{\sm}{\setminus}
\newcommand{\sub}{\subseteq}

%Commands Taking Input
\renewcommand{\c}[1]{\mathcal{#1}}
\renewcommand{\b}[1]{\mathbf{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\B}[1]{\mathbb{#1}}
\newcommand{\ol}[1]{\overline{#1}}
\newcommand{\tr}[1]{\textrm{#1}}
\newcommand{\rec}[1]{\frac{1}{#1}}
\newcommand{\f}[2]{\frac{#1}{#2}}
\newcommand{\floor}[1]{\l\lfloor #1\r\rfloor}
\newcommand{\ceil}[1]{\l\lceil #1\r\rceil}
\newcommand{\il}[1]{\item \label{#1}}
\newcommand{\xto}[1]{\xrightarrow{#1}}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\Graph}[2]{\includegraphics[width=#2\textwidth]{#1}}%For argument just put name of picture that is in file called 'TexImages'
\newcommand{\counter}[2]{\setcounter{#1}{#2-1}} % \counter{section}{0}
\newcommand{\mr}[1]{\mathrm{#1}}
\newcommand{\Eul}{\genfrac{\langle}{\rangle}{0pt}{}}
\newcommand{\tu}[1]{\textup{(#1)}}

%Notes to Self
\newcommand{\TD}{\textbf{\textcolor{red}{TODO}}}
\newcommand{\Hint}[1]{(\textbf{Hint: }\textcolor{white}{#1})}
\newcommand{\SP}[1]{\textbf{\textcolor{orange}{#1}}}
\newcommand{\SH}{\textbf{\textcolor{orange}{SHALLOW}}}
\newcommand{\SD}{\textbf{\textcolor{orange}{SHALLOW TODO}}}
\newcommand{\REF}{\textbf{\textcolor{orange}{REF}}}
\renewcommand{\SS}[1]{\textcolor{red}{#1}}
\newcommand{\BD}[1]{\textcolor{purple}{Comment by Bishal: #1}}
\newcommand{\YH}[1]{\textcolor{blue}{Comment by Yifeng: #1}}
\newcommand{\AC}[1]{\textcolor{green}{Comment by Alexander: #1}}


\newcommand{\blue}[1]{\textcolor{blue}{#1}}

%Text symbols
\newcommand{\sgn}{\mr{sgn}}
\newcommand{\ex}{\mr{ex}}
\newcommand{\im}{\mr{im}}
\newcommand{\Tr}{\mr{Tr}}
\newcommand{\supp}{\mr{supp}}
\newcommand{\Var}{\mr{Var}}
\newcommand{\sat}{\mr{sat}}

\renewcommand{\S}{\mathfrak{S}}
\newcommand{\rand}[1]{\boldsymbol{#1}}
%If you delete your custom commands, note that the following will seem not to give errors but still need to be dealt with: \l, \r, \c, \b, \1

%From here, Bishal's newcommand
\newcommand{\perm}{\mathfrak{S}_{m,n}}
\newcommand{\permmn}[2]{\mathfrak{S}_{#1,#2}}
\newcommand{\explpi}{\mathcal{L}_{m,n}^{1}}
\newcommand{\explpimn}[2]{\mathcal{P}_{#1,#2}}
\newcommand{\lm}{\mathcal{L}_{m}^{1}}
\newcommand{\lmval}[1]{\mathcal{P}_{#1}}
\renewcommand{\l}{\mathcal{P}_2}
\newcommand{\hm}{h_m(n)}
\newcommand{\h}{h_2(n)}
\newcommand{\wc}{\mathcal{N}(n,m)}
\newcommand{\wcval}[2]{\mathcal{N}(#1,#2)}
\newcommand{\rootsy}{{\alpha^{(m)}_1(y),\ldots,\alpha^{(m)}_m(y)}}
\newcommand{\rootsyval}[1]{{\alpha^{(m)}_1(#1),\ldots,\alpha^{(m)}_m(#1)}}
\newcommand{\roots}{\alpha_1,\ldots,\alpha_m}

\newcommand{\denpolym}{d^{(m)}(x,y)}
\renewcommand{\l}{\left}




%% define your title in the usual way
\title{Continuously Increasing Subsequences of Random Multiset Permutations}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~Clfiton, B.~Deb, Y.~Huang, S.~Spiro, and S.~Yoo]{Alexander Clifton\thanks{\href{mailto:aclift2@emory.edu}{aclift2@emory.edu}. The author is supported in part by a George W. Woodruff Fellowship and NSF Grant DMS-1945200.}\addressmark{1}, Bishal Deb\thanks{\href{mailto:bishal.deb.19@ucl.ac.uk}{bishal.deb.19@ucl.ac.uk}.}\addressmark{2}, Yifeng Huang\thanks{\href{mailto:huangyf@umich.edu}{huangyf@umich.edu}.}\addressmark{3}, Sam Spiro\thanks{\href{mailto:sspiro@ucsd.edu}{sspiro@ucsd.edu}. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1650112.}\addressmark{4}, \and Semin Yoo\thanks{\href{mailto:syoo19@kias.re.kr}{syoo19@kias.re.kr}. The author is supported by the KIAS Individual Grant (CG082701) at the Korea Institute for Advanced Study.}\addressmark{5}}


%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Dept.\ of Mathematics, Emory University, Atlanta, GA, USA \\ \addressmark{2}Dept.\ of Mathematics,  University College London, London, UK\\ \addressmark{3}Dept.\ of Mathematics, University of Michigan, Ann Arbor, MI, USA\\ \addressmark{4}Dept.\ of Mathematics, University of California San Diego, San Diego, CA, USA \\ \addressmark{5}School of Computational Sciences, Korea Institute for Advanced Study, Seoul, South Korea  }

%% put the date of submission here
\received{Nov. 8, 2021}

%% leave this blank until submitting a revised version
\revised{Mar. 31, 2021}

%% 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{For a word $\pi$ and integer $i$, we define $L^i(\pi)$ to be the length of the longest subsequence of the form $i(i+1)\cdots j$, and we let $L(\pi):=\max_i L^i(\pi)$.   In this paper we estimate the expected values of $L^1(\pi)$ and $L(\pi)$ when $\pi$ is chosen uniformly at random from all words which use each of the first $n$ positive integers exactly $m$ times.  We show that $\mathbb{E}[L^1(\pi)]\sim m$ if $n$ is sufficiently larger in terms of $m$ as $m$ tends towards infinity,  confirming a conjecture of Diaconis, Graham, He, and Spiro.  We also show that $\mathbb{E}[L(\pi)]$ is asymptotic to the inverse gamma function $\Gamma^{-1}(n)$ if $n$ is sufficiently large in terms of $m$ as $m$ tends towards infinity.}

%% 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{multiset permutations, increasing subsequences, generating functions, zeroes of polynomials, probability}

%% 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, ie. [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{sample.bib}
\addbibresource{references.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}
	\subsection{Main Results}
	
	Given integers $m$ and $n$, let $\S_{m,n}$ denote the set of words $\pi$ which use each integer in $[n]:=\{1,2,\ldots,n\}$ exactly $m$ times, and we will refer to $\pi\in \S_{m,n}$ as a \textit{multiset permutation}.  For example, $\pi=211323\in \S_{2,3}$.  For $\pi\in \S_{m,n}$ and $i$ an integer, we define $L^i_{m,n}(\pi)$ to be the length of the longest subsequence of $\pi$ of the form $i(i+1)(i+2)\cdots j$, which we call an \textit{$i$-continuously increasing subsequence}.  We say that a subsequence is a \textit{continuously increasing subsequence} if it is an $i$-continuously increasing subsequence for some $i$, and we define $L_{m,n}(\pi)=\max_i L^i_{m,n}(\pi)$ to be the length of a longest continuously increasing subsequence of $\pi$.  For example, if $\pi=2341524315$ then $L_{2,5}(\pi)=L^2_{2,5}(\pi)=4$ due to the subsequence $2345$, and $L^1_{2,5}(\pi)=3$ due to the subsequence $123$.
	

	
	The focus of this paper is to study $L^1_{m,n}(\pi)$ and $L_{m,n}(\pi)$ when $\pi$  is chosen uniformly at random from $\S_{m,n}$.  We focus on the regime where $n$ is much larger than $m$, as in the regime where $m$ is much larger than $n$,  $L^i_{m,n}(\pi)$ is very likely to be its maximum possible value $n-i+1$ for all $i$.
	
	We first consider $\E[L^1_{m,n}(\pi)]$.  This quantity was briefly studied by Diaconis, Graham, He, and Spiro~\cite{DGHS21} due to its relationship with a certain card game that we describe later in this paper.  They proved $\E[L^1_{m,n}(\pi)]\le m+Cm^{3/4}\log m$ for some absolute constant $C$ provided $n$ is sufficiently large in terms of $m$.
	It was conjectured in \cite{DGHS21} that this upper bound for $\E[L^1_{m,n}(\pi)]$ is asymptotically tight for $n$ sufficiently large in terms of $m$.  We verify this conjecture in a strong form, obtaining an exact formula for $\lim_{n\to \infty} \E[L^1_{m,n}(\pi)]$ for any fixed $m$ and precise estimates of this value as $m$ tends towards infinity.
	
	\begin{thm}\label{thm:C1}
	~
	\begin{itemize}
	    \item[\tu{a}] For any integer $m\ge 1$, let $\al_1,\ldots,\al_m$ be the zeroes of $E_m(x):=\sum_{k=0}^m \f{x^k}{k!}$.  If $\pi\in \S_{m,n}$ is chosen uniformly at random, then
       \begin{equation}\label{expeq}
    \lm:=\lim_{n\to \infty} \E[L_{m,n}^1(\pi)]=-1-\sum \al_i^{-1} e^{-\al_i}.
    \end{equation}
    \item[\tu{b}] There exists an absolute constant $\be&gt;0$ such that
		\[\l|\mathcal{L}_m^1-\l(m+1-\rec{m+2}\r)\r|\le O(e^{-\beta m}).\]
	\end{itemize}
	

	\end{thm}
	For example, when $m=1$ we have $E_1(x)=1+x$ and $\al_1=-1$, implying $\mathcal{L}_1^1=-1+e$, which can also be proven by elementary means.  For $m=2$ we have $E_2(x)=1+x+x^2/2$ and $\al_1=-1-i,\al_2=-1+i$.  From this Theorem~\ref{thm:C1}(a) gives the following closed form expression for $\c{L}_2^1$.
\begin{cor} 
\[
\mathcal{L}_{2}^{1}=e\left(\cos(1)+\sin(1)\right)-1.
\]
\end{cor}

	Our next result gives precise bounds for the length of a longest continuously increasing subsequence in a random permutation of $\S_{m,n}$.  We recall that the gamma function $\Gam(x)$ is a function which, in particular, gives a bijection from $x\ge 1$ to $y\ge 1$ and which satisfies $\Gam(n)=(n-1)!$ for non-negative integers $n$.  
	\begin{thm}\label{thm:C}
		If $n$ is sufficiently large in terms of $m$, then
		\[\E[L_{m,n}(\pi)]=\Gam^{-1}(n)+\Theta\l(1+\f{\log m}{\log(\Gam^{-1}(n))} \Gam^{-1}(n)\r),\]
		where $\Gam^{-1}(n)$ is the inverse of the gamma function when restricted to $x\ge 1$.
	\end{thm}
	Note when $m=1$ the error term of Theorem~\ref{thm:C} is $\Theta(1)$, but for $m\ge 2$ it is $\Theta(\f{\log m}{\log \Gam^{-1}(n)}\Gam^{-1}(n))$, which is fairly close to the main term of $\Gam^{-1}(n)$.  Thus the behavior of $\E[L_{m,n}(\pi)]$ changes somewhat dramatically as soon as one starts to consider multiset permutations as opposed to just permutations.  

	\subsection{History and Related Work}
	
	Determining $L^i_{m,n}(\pi)$ and $L_{m,n}(\pi)$ can be viewed as variants of the well-studied problem of determining the length of the longest increasing subsequence in a random permutation of length $n$, and we denote this quantity by $\widetilde{L}_n$.  It was shown by Logan and Shepp \cite{LS77} and Vershick and Kerov \cite{VK77} that $\E[\widetilde{L}_n]\sim 2\sqrt{n}$, answering a famous problem of Ulam. Later Baik, Deift, and Johansson \cite{BDJ99} showed that the limiting distribution of $\widetilde{L}_n$ is the Tracy--Widom distribution. Some work with the analogous problem for multiset permutations has been considered recently by Almeanazel and Johnson \cite{AMJ20}.  Much more can be said about this topic, and we refer the reader to the excellent book by Romik \cite{Rom} for more information.
	
	
	The initial motivation for studying $L^1(\pi)$ was due to its relationship to a card guessing experiment introduced by Diaconis and Graham~\cite{DG81}.  To start the experiment, one shuffles a deck of $mn$ cards which consists of $n$ distinct card types each appearing with multiplicity $m$. In each round, a subject iteratively guesses what the top card of the deck is according to some strategy $G$.  After each guess, the subject is told whether their guess was correct or not, the top card is discarded, and then the experiment continues with the next card.  This experiment is known as the \textit{partial feedback model}.  For more on the history of the partial feedback model we refer the reader to \cite{DGS21}.
	%The study of this and other card guessing feedback models originated from problems in clinical trials \cite{BH57, Efr71}, casino games \cite{Als12, EL05}, and ESP detection experiments \cite{Dia78}; see \cite{DGS21} for more information on feedback models.
	
	If $G$ is a strategy for the subject in the partial feedback model and $\pi\in \S_{m,n}$, we let $P(G,\pi)$ denote the number of correct guesses made by the subject if they follow strategy $G$ and the deck is shuffled according to $\pi$. We say that $G$ is an \textit{optimal strategy} if $\E[P(G,\pi)]=\max_{G'} \E[P(G',\pi)]$, where $G'$ ranges over all strategies and $\pi\in \S_{m,n}$ is chosen uniformly at random.   Optimal strategies are unknown in general, and even if they were known they would likely be too complex for a human subject to implement in practice.  As such there is interest in coming up with (simple) strategies $G$ such that $\E[P(G,\pi)]$ is relatively large.
	
	One strategy is the \textit{trivial strategy} which guesses card type 1 every single round, guaranteeing a score of exactly $m$ at the end of the experiment.  A slightly better strategy is the \textit{safe strategy} $G_{safe}$ which guesses card type 1 every round until all $m$ are guessed correctly, then 2's until all $m$ are guessed correctly, and so on.  It can be deduced from arguments given by Diaconis, Graham, and Spiro~\cite{DGS21} that $\E[P(G_{safe},\pi)]$ is $m+1-\rec{m+1}$ plus an exponential error term, so the safe strategy does just a little better than the trivial strategy.  
	
	Another natural strategy is the \textit{shifting strategy} $G_{shift}$, defined by guessing 1 until you are correct, then 2 until you are correct, and so on; with the strategy being defined arbitrarily in the (very rare) event that one correctly guesses a copy of each card type.  It is not difficult to see that $P(G_{shift},\pi)\ge L^1_{m,n}(\pi)$, with equality holding provided the player does not correctly guess $n$.  Thus Theorem~\ref{thm:C1}(b) shows that the expected number of correct guesses under the shifting strategy is close to $m+1-\rec{m+2}$, which is slightly better than the trivial strategy, and very slightly better than the safe strategy.
	
\subsection{Preliminaries}
	We let $[n]:=\{1,2,\ldots,n\}$ and let $[m]^n$ be the set of tuples of length $n$ with entries in $[m]$.  Whenever we write, for example, $\Pr[L_{m,n}(\pi)\ge k]$, we will assume $\pi$ is chosen uniformly at random from $\S_{m,n}$ unless stated otherwise.
	
	Throughout this paper we use several basic results from probability theory.  One such result is that if $X$ is a non-negative integer-valued random variable, then
	\[\E[X]=\sum_{k=1}^{\infty}\Pr[X\ge k].\]
	A crucial observation that we use throughout the text is the following.
	\begin{obs}\label{obs1}
	    For $n\le k$, if $\pi\in \S_{m,k}$ and $\tau\in \S_{m,n}$ are drawn uniformly at random, then
	    \[\Pr[L^1_{m,k}(\pi)\ge n]=\Pr[L^1_{m,n}(\tau)=n].\]
	\end{obs}
	\begin{proof}
	    For $\pi\in \S_{m,n}$, let $\phi(\pi)\in \S_{m,k}$ be the word obtained by deleting every letter from $\pi$ which is larger than $k$.  Note that $L^1_{m,n}(\pi)\ge k$ if and only if $L^1_{m,k}(\phi(\pi))=k$.  Moreover, it is not difficult to see that $\phi(\pi)$ is distributed uniformly at random in $\S_{m,k}$ provided $\pi$ is distributed uniformly at random in $\S_{m,n}$, proving the result.
	\end{proof}
	
	\section{Proof of Theorem~\ref{thm:C1}}
	
	

We say that a word $\pi\in \perm$ has a \textit{complete increasing subsequence} if $L^1_{m,n}(\pi) = n$. Let $\hm$ be the number of words $\pi\in\perm$ which have a complete increasing subsequence. Horton and Kurn \cite[Corollary (c)]{HK81} give the following formula for $\hm$. 
\begin{thm}[\cite{HK81}]\label{HK} The number of words $\pi\in\perm$ which have a complete increasing subsequence, $\hm$, is given by
\[
\hm = \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m} \dfrac{(mn)!}{l!}\dfrac{(-1)^{l-n}}{\prod_{j=1}^m(m-j)!^{i_j}},
\]
where \[l=\sum_{j=1}^{m}j i_j,\] 
$\wc$ is the set of weak compositions of $n$ into $m$ parts, \textit{i.e.},
\[
\wc \coloneqq \left\lbrace (i_1,\ldots,i_m)\in \mathbb{Z}_{\geq{0}}^m  \middle|  \sum_{j=1}^m i_j = n\right\rbrace,\]
and \[\binom{n}{i_1,\ldots,i_m} = \dfrac{n!}{\prod_{j=1}^m i_j!}\] is a multinomial coefficient. 
\label{thm.hmformula}
\end{thm}
Notice that $\lm$, defined in Equation~\eqref{expeq}, can be expressed in terms of $h_{m}(n)$ as follows: 
\begin{equation}
\mathcal{L}_{m}^{1}=\lim_{k\to \infty} \E[L_{m,k}^1(\pi)]= \lim_{k\to \infty} \sum_{n=1}^{k}\mathrm{Pr}[L^{1}_{m,k}(\pi)\geq n] = \lim_{k\to \infty} \sum_{n=1}^{k} \dfrac{\hm}{|\perm|}=\sum_{n=1}^{\infty} \dfrac{\hm}{|\perm|},
\label{eq.lmseries}
\end{equation}
where the third equality is due to Observation \ref{obs1}. Note that $|\perm| = (mn)!/(m!)^n$. Thus, as a consequence of Theorem~\ref{HK}, we have
\begin{subequations}
\begin{equation}
\dfrac{\hm}{|\perm|} = (-m!)^n \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m}\dfrac{(-1)^l}{l!} \dfrac{1}{\prod_{j=1}^m(m-j)!^{i_j}},
\label{eq.summandexpand1}
\end{equation}
\begin{equation}
\hspace{2.5em}= (-m!)^n \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m}\dfrac{1}{l!}\prod_{j=1}^m \left(\dfrac{(-1)^j}{(m-j)!}\right)^{i_j}.
\label{eq.summandexpand2}
\end{equation}
\end{subequations}

Intuitively, if the $1/l!$ were removed from the right-hand-side expression in \eqref{eq.summandexpand2}, then by using the multinomial theorem we could write this expression as an $n^{\text{th}}$ power, turning \eqref{eq.lmseries} into a geometric series. The next few paragraphs formalise this idea.

We begin by replacing $(-1)^l$ by $x^l$ in the right-hand-side of \eqref{eq.summandexpand1} to obtain the polynomial
\begin{align*}
    p_{m,n}(x)\coloneqq&amp; (-m!)^n \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m} \dfrac{x^l}{l!}\dfrac{1}{\prod_{j=1}^m(m-j)!^{i_j}}\\ 
    =&amp; (-m!)^n \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m}\dfrac{1}{l!}\prod_{j=1}^m \left(\dfrac{x^j}{(m-j)!}\right)^{i_j}.
\end{align*}
Thus,
\[
p_{m,n}(-1)= \dfrac{\hm}{|\perm|}.
\]

Next, we define an operator in order to remove the $l!$ from the denominator. Let $R$ be a commutative ring containing $\mathbb{Q}$ and let $\Phi \colon R[x]\to R[x]$ be an $R$-linear map defined on the monomials by 
\[
\Phi(x^n) = \dfrac{x^n}{n!}.
\]
We can extend $\Phi$ to an $R$-linear map on $R[[x]]\to R[[x]]$, which we also refer to as $\Phi$ by abuse of notation. Throughout this article, $R$ is either $\mathbb{C}$ or $\mathbb{C}[[y]]$ for an indeterminate $y$, and we shall refer to this $R$-linear map as $\Phi$ in both cases. Notice that $\Phi$ is invertible for any such ring $R$.  A key property that we use about $\Phi$ is
\begin{equation}\Phi\l(\rec{1-ax}\r)=\Phi\l(\sum_{i=0}^\infty (ax)^i\r)=\sum_{i=0}^\infty \f{(ax)^i}{i!}=e^{ax}.\label{eq:simplefraction}\end{equation}

Consider the polynomial
\begin{subequations}
\begin{equation*}
q_{m,n}(x)\coloneqq \Phi^{-1}\left(p_{m,n}(x)\right) = (-m!)^n \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m} \dfrac{x^l}{\prod_{j=1}^m(m-j)!^{i_j}}
\end{equation*}
\begin{equation*}
= (-m!)^n \sum_{(i_1,\ldots,i_m)\in\wc} \binom{n}{i_1,\ldots,i_m}\prod_{j=1}^m \left(\dfrac{x^j}{(m-j)!}\right)^{i_j}.
\end{equation*}
\end{subequations}
Notice that,
\[
q_{m,n}(x) =  \left(-m!\sum_{j=1}^m \dfrac{x^j}{(m-j)!}\right)^n=(q_{m,1}(x))^n.
\]


Let $P_{m}(x,y)$ and $Q_{m}(x,y)$ be the ordinary generating functions of $p_{m,n}(x)$ and $q_{m,n}(x)$ respectively, \textit{i.e.}
\begin{subequations}
\begin{equation*}
P_{m}(x,y) \coloneqq \sum_{n=0}^{\infty} p_{m,n}(x) y^n,
\end{equation*}
\begin{equation*}
Q_{m}(x,y) \coloneqq \sum_{n=0}^{\infty} q_{m,n}(x) y^n = \Phi^{-1}\left(P_{m}(x,y) \right).
\end{equation*}
\end{subequations}

Putting everything together, we see that
\begin{equation}\label{Cm1}
\lm=P_{m}(-1,1)-1.
\end{equation}
and thus it suffices to find a nice closed form expression for $P_{m}(x,y)$.  Note that
\[
q_{m,1}(x)= -m!x^m E_{m-1}(1/x),
\]
\sloppy where we recall the polynomial $E_{m-1}(x)$ is defined in Theorem~\ref{thm:C1} by $E_{m-1}(x)=\sum_{k=0}^{m-1} x^k/k!$.   As $q_{m,n}(x) = \left(q_{m,1}(x)\right)^n $, we have
\begin{equation}\label{eq:Q}
Q_{m}(x,y) = \dfrac{1}{1-yq_{m,1}(x)} =\dfrac{1}{1+m!x^my E_{m-1}(1/x)}.
\end{equation}
Hence,
\[
P_{m}(x,y) =  \Phi\left(Q_{m}(x,y)\right) = \Phi\left(\dfrac{1}{1+m!x^my E_{m-1}(1/x)}\right),
\]
and thus
\[
P_{m}(x,1) = \Phi\left(\dfrac{1}{1+m!x^m E_{m-1}(1/x)}\right)=\Phi\left(\dfrac{1}{m!x^m E_{m}(1/x)}\right).
\]

We now prove the main result of this subsection.

\begin{prop}\label{zeroes} Let $\roots$ be the zeroes of the polynomial $E_m(x)$. The formal power series $P_{m}(x,1)$ satisfies
\begin{equation*}
P_{m}(x,1) = -\sum_{i=1}^m \alpha_i^{-1}e^{\alpha_{i}x }.
\end{equation*}
\end{prop}

\begin{proof} Let $g(x) \coloneqq m!x^m E_m(1/x)$. Since $\alpha_1^{-1},\ldots, \alpha_m^{-1}$ are the zeroes of $g(x)$, we have
\begin{equation*}
g(x) =m! (x-\alpha_1^{-1})\cdots (x-\alpha_m^{-1}).
\end{equation*}

Notice that $E_m(x)$ has no repeated zeroes. This is true because, if $\alpha$ is a repeated zero of $E_m(x)$, it is also a zero of its derivative $E_{m}'(x) = E_{m-1}(x)$. But then $\alpha$ has to be a zero of $E_m(x)-E_{m-1}(x) = x^m/m!$, which is only possible if $\alpha=0$, a contradiction as $0$ is not a zero of $E_m(x)$.

Thus  $\roots$ are pairwise distinct, and hence the zeroes of $g(x)$ being $\alpha_1^{-1},\ldots, \alpha_m^{-1}$ are also pairwise distinct. This, together with \eqref{eq:Q}, implies that $Q_{m}(x,1)$ has the partial fraction decomposition
\begin{equation*}
Q_{m}(x,1) = \dfrac{1}{g(x)} = \sum_{i=1}^m \dfrac{1}{g'\left(\alpha_i^{-1}\right)}\cdot \dfrac{1}{x-\alpha_i^{-1}}.
\end{equation*}

The derivative of $g$ is
\[
\begin{split}
g'(x) = &amp; m!\left( \dfrac{m x^m E_m(1/x)}{x} - \dfrac{x^mE_m'(1/x)}{x^2} \right) \\
= &amp; m!\left( \dfrac{m x^m E_m(1/x)}{x} - \dfrac{x^m(E_m(1/x) - x^{-m}/m!)}{x^2} \right).
\end{split}
\]

Hence for any $i$,
\begin{equation*}
g'\left(\alpha_i^{-1}\right) = \alpha_i^{2},
\end{equation*}
which gives
\begin{equation*}
P_{m}(x,1) = \Phi\left(Q_{m}(x,1)\right) = -\sum_{i=1}^m  \Phi\left(\dfrac{1}{\alpha_i(1-\alpha_i x)}\right) = -\sum_{i=1}^m \alpha_i^{-1}e^{\alpha_{i}x },
\end{equation*}
where this last step used \eqref{eq:simplefraction}.
\end{proof}
This proposition together with \eqref{Cm1} gives Theorem \ref{thm:C1}(a).  To prove Theorem \ref{thm:C1}(b), it now suffices to show that \[\displaystyle\sum_{i=1}^m \alpha_i^{-1}e^{-\alpha_i}=-m-2+\frac{1}{m+2}+O(e^{-\beta m})\] for some positive constant $\beta$. To do this, we follow techniques similar to those used by Conrey and Ghosh \cite{conrey1988zeros} to compute $\displaystyle\sum_{i=1}^m e^{-\alpha_i}$. The strategy is to fix some $0&lt;\gamma&lt;1-\log{2}$ and to partition the $\alpha_i$'s into two sets based on whether or not $Re(\alpha_i)\leq{\gamma m}$. For further details on how to bound $\displaystyle\sum \alpha_i^{-1}e^{-\alpha_i}$ for each of these sets, we refer the reader to the full version of our paper~\cite{Cliftonetallong21}.



\section{Proof of Theorem~\ref{thm:C}}

Here we present a sketch of the proof of Theorem~\ref{thm:C}.  The complete details can be found in the full version of the paper~\cite{Cliftonetallong21}.

The upper bound of Theorem~\ref{thm:C} follows from a standard first moment argument, so we focus on proving the lower bound.  The main tool we require is a lower bound on the probability that $\pi \in \S_{m,n}$ has a complete increasing subsequence, \textit{i.e.}\ a subsequence of the form $12\cdots n$.  When $m=1$ this occurs with probability $1/n!$ exactly.  We prove a stronger bound for $m\ge 2$.

\begin{prop}\label{prop:lowerCont}
		For $n$ sufficiently large in terms of $m\ge 2$, we have
		\[\Pr[L_{m,n}(\pi)=n]\ge \f{(m/1.03)^n}{2n\cdot n!}.\]
\end{prop} Proposition~\ref{prop:lowerCont} is proved by using an argument inspired by coding theory and some careful analysis.  This allows us to prove our main result.

\begin{proof}[Sketch of Proof of Theorem~\ref{thm:C}]
		The upper bound follows from a standard first moment argument.  To prove the lower bound, fix an integer $k$.  For $0\le j&lt; \floor{n/k}$, let $A_j(\pi)$ be the event that $\pi$ contains the subsequence $(jk+1)(jk+2)\cdots((j+1)k)$.  \begin{claim}
		We have the following:
		\begin{itemize}
			\item[\tu{a}] If any $A_j(\pi)$ event occurs, then $L_{m,n}(\pi)\ge k$.
			\item[\tu{b}] The $A_j(\pi)$ events are mutually independent.
			\item[\tu{c}] For all $j$, we have $\Pr[A_j(\pi)]=\Pr[L_{m,k}(\sig)=k]$ where $\sig\in \S_{m,k}$ is chosen uniformly at random.  
		\end{itemize}
		\end{claim}
		\begin{proof}
		    Part (a) is clear, and (b) follows from the fact that the events $A_j(\pi)$ involve the relative ordering of disjoint sets of letters.   For (c), one can consider the map which sends $\pi\in \S_{m,n}$ to $\sig \in \S_{m,k}$ by deleting every letter in $\pi$ except for $(jk+1),\ldots,((j+1)k)$ and then relabeling $jk+i$ to $i$.  It is not difficult to see that $A_j(\pi)$ occurs if and only if $L_{m,k}(\sig)=k$ occurs, and that $\pi$ being chosen uniformly at random implies $\sig$ is chosen uniformly at random.
		\end{proof}
		Let $p_k=\Pr[L_{m,k}(\sig)=k]$.  The claim above implies that for all $k$ we have
		{\small \begin{equation}\Pr[L_{m,n}(\pi)\ge k]\ge \Pr\l[\bigcup A_j(\pi)\r]=1-\Pr\l[\bigcap A_j^c(\pi)\r]=1-(1-p_k)^{\floor{n/k}}.\label{eq:expLower}\end{equation}}%
		Because $\E[L_{m,n}(\pi)]=\sum \Pr[L_{m,n}(\pi)\ge k]$, inequality \eqref{eq:expLower} shows that we can bound this expectation from below by by bounding $p_k$ from below.  This can be done by utilizing Proposition~\ref{prop:lowerCont}, and from this one can show that the desired bound holds after performing a careful analysis.
	\end{proof}

\iffalse 
	\subsection{The Lower Bound}
	For $x,y\in [m]^n$, we define their \textit{Hamming distance} $d_H(x,y):=|\{i\in[n]: x_i\ne y_i\}|$.  Our key lemma for proving the lower bound of Theorem~\ref{thm:C} is the following:
	\begin{lem}\label{lem:inclusionExclusion}
		Let $T\sub [m]^n$ be such that any distinct $x,y\in T$ have $d_H(x,y)\ge \del$ for some integer $\del$.  Then
		\[\Pr[L_{m,n}(\pi)=n]\ge \f{|T|}{n!}\l(1-\f{|T|}{\del!}\r).\]
	\end{lem}
	
	\begin{proof}
		For $\tau\in \S_{m,n}^*$, let  $L^*_{m,n}(\tau)$ denote the length of the longest subsequence of $\tau$ of type $i(i+1)\cdots j$. By Observation~\ref{obs2}, it suffices to prove this lower bound for $\Pr[L_{m,n}^*(\tau)=n]$ where $\tau\in \S_{m,n}^*$ is chosen uniformly at random.  For $x\in [m]^n$, let $A_x(\tau)$ be the event that $\tau$ contains a subsequence of type $(12\cdots n,x)$.  Observe that
		 \begin{align}\Pr[L_{m,n}^*(\tau)=n]&amp;=\Pr[\bigcup_{x\in [m]^n}A_x(\tau)]\ge \Pr[\bigcup_{x\in T}A_x(\tau)]\nonumber\\&amp;\ge \sum_{x\in T}\Pr[A_x(\tau)]-\sum_{x,y\in T,\ x\ne y}\Pr[A_x(\tau)\cap A_y(\tau)],\label{eq:contLower}\end{align}
		where the last inequality used the Bonferroni inequality (which is essentially a weakening of the principle of inclusion-exclusion); see, \textit{e.g.},~\cite{spencer2014asymptopia} for further details on this inequality.  To bound \eqref{eq:contLower}, we use the following: \begin{claim}
		If $x,y\in T$ with $x\ne y$, then $\Pr[A_x(\tau)]=1/n!$ and \[\Pr[A_x(\tau)\cap A_y(\tau)]\le \f{1}{\del!n!}.\]
		\end{claim}
		\begin{proof}
		    Observe that $A_x(\tau)$ occurs if and only if $1_{x_1},\ldots,n_{x_n}$ occur in the correct relative order in $\tau$, so $\Pr[A_x(\tau)]=1/n!$.  Let $S=\{i_1&lt;i_2&lt;\cdots&lt;i_\del\}$ be any set of $\del$ indices $i$ such that $y_i\ne x_i$, and note that such a set exists by assumption of $T$.  Let $A_y^S(\tau)$ be the event that $(i_1)_{y_{i_1}}\cdots (i_\del)_{y_{i_\del}}$ is a subsequence of $\tau$.  Observe that $\Pr[A_y^S(\tau)]=1/\del!$ and that this event is independent of $A_x(\tau)$ since these two events concern disjoint sets of letters.  Because $A_y(\tau)$ implies $A_y^S(\tau)$, we have
		    \[\Pr[A_x(\tau)\cap A_y(\tau)]\le \Pr[A_x(\tau)\cap A_y^S(\tau)]=\rec{\del! n!},\]
		    proving the result.
		\end{proof}
		Plugging the results of this claim into \eqref{eq:contLower} and using that the second sum of  \eqref{eq:contLower} has at most $|T|^2$ terms gives the desired result.
	\end{proof}
	
	The problem of finding $T\sub [m]^n$ such that $d_H(x,y)\ge \del$ with $|T|$ and $\del$ both large is the central problem of coding theory.   In particular, a basic greedy argument from coding theory gives the following:
	\begin{lem}\label{lem:badPairs}
		For any $m\ge 2$ and $1\le \del\le n/2$, there exists $T\sub [m]^n$ such that any two distinct $x,y\in T$ have $d_H(x,y)\ge \del$  and such that \[|T|\ge \f{m^n}{\del {\binom{n}{\del}} (m-1)^\del}.\]
	\end{lem}
	\begin{proof}
	    Let $T\sub [m]^n$ be a set such that $d_H(x,y)\ge \del$ for distinct $x,y\in T$ and such that $|T|$ is as large as possible.  Let $B(x)=\{y\in [m]^n:d_H(x,y)&lt;\del\}$, and note that for all $x$, \[|B(x)|= \sum_{d=0}^{\del -1} {\binom{n}{d}}(m-1)^d\le \del {\binom{n}{d}}(m-1)^\del,\]
	    with this last step using ${\binom{n}{d}}\le {\binom{n}{\del}}$ for $d&lt;\del\le n/2$.   By the maximality of $|T|$, we must have $[m]^n=\bigcup_{x\in T} B(x)$, and thus
	    \[m^n=|\bigcup_{x\in T} B(x)|\le |T|\cdot \del {\binom{n}{\del}}(m-1)^\del,\]
	    giving the desired bound on $|T|$.
	\end{proof}
	Combining  Lemmas~\ref{lem:inclusionExclusion} and \ref{lem:badPairs} gives the following:
	\begin{prop}\label{prop:lowerCont}
		For $n$ sufficiently large in terms of $m\ge 2$, we have
		\[\Pr[L_{m,n}(\pi)=n]\ge \f{(m/1.03)^n}{2n\cdot n!}.\]
	\end{prop}
	\begin{proof}
		We start with the following fact.
		\begin{claim}
		For all $\ep&gt;0$, there exists a constant $0&lt;c_\ep\le 1$ such that if $\del\le c_\ep n$, then ${\binom{n}{\del}}\le (1+\ep)^n$.
		\end{claim}
		\begin{proof}
		    In \cite{cover1999elements} it is noted that ${\binom{n}{\del}}\le 2^{H(\del/n) n}$ for all $n,\del$, where $H(p):=-p\log_2(p)-(1-p)\log_2(1-p)$ is the binary entropy function.  Because $H(p)$ tends to 0 as $p$ tends to 0, there exists a constant $c$ such that $2^{H(c)}\le 1+\ep$, and the result follows by taking $c_\ep=c$.
		\end{proof}
		Let $\del=\f{2\log m}{\log n} n$, and assume $n$ is sufficiently large in terms of $m$ so that $\del\le c_{.01}n$, \textit{i.e.}\ so that ${\binom{n}{\del}}\le (1.01)^n$.  We also choose $n$ sufficiently large so that $\del\le \f{\log 1.01}{\log m}n$, or equivalently so that $m^\del\le (1.01)^n$. Let $T$ be a set as in Lemma~\ref{lem:badPairs}, and by our assumptions above we find
		\[|T|\ge \f{(m/1.03)^n}{n}.\]
		Possibly by deleting elements from $T$ we can assume that $|T|$ is exactly the quantity stated above\footnote{Strictly speaking we should take $|T|$ to be the floor of this value to guarantee that it is an integer.  This would change our ultimate bound by at most a factor of 2, and this factor of 2 can easily be recovered by sharpening our analysis in various places.}, so by Lemma~\ref{lem:inclusionExclusion} it suffices to show $|T|/\del!\le \half$.  Using the inequality $\del!\ge (\del/e)^\del$ and that $n$ is sufficiently large, we have 
		\[\del!\ge \exp\l[\del\cdot (\log(\del)-1)\r]\ge \exp\l[\f{2\log m}{\log n}n\cdot (\log(n)-\log(\log(n))-1)\r]\ge \exp\l[\log(m) n\r]=m^n.\]
		Thus $|T|/\del!\le (1.03)^{-n}/n\le \half$, proving the result.
	\end{proof}
	%\SS{With regards to dependencies: this proof roughly works for $n\ge m^{\log m}$.}
	
	With this we can now prove Theorem~\ref{thm:C}.
	\begin{proof}[Proof of Theorem~\ref{thm:C}]
		The upper bound follows from Proposition~\ref{prop:prefix}.  To prove the lower bound, fix an integer $k$.  For $0\le j&lt; \floor{n/k}$, let $A_j(\pi)$ be the event that $\pi$ contains the subsequence $(jk+1)(jk+2)\cdots((j+1)k)$.  \begin{claim}
		We have the following:
		\begin{itemize}
			\item[\tu{a}] If any $A_j(\pi)$ event occurs, then $L_{m,n}(\pi)\ge k$,
			\item[\tu{b}] The $A_j(\pi)$ events are mutually independent, and
			\item[\tu{c}] For all $j$, we have $\Pr[A_j(\pi)]=\Pr[L_{m,k}(\sig)=k]$ where $\sig\in \S_{m,k}$ is chosen uniformly at random.  
		\end{itemize}
		\end{claim}
		\begin{proof}
		    Part (a) is clear, and (b) follows from the fact that the $A_j(\pi)$ events involve the relative ordering of disjoint sets of letters.   For (c), one can consider the map which sends $\pi\in \S_{m,n}$ to $\sig \in \S_{m,k}$ by deleting every letter in $\pi$ except for $(jk+1),\ldots,((j+1)k)$ and then relabeling $jk+i$ to $i$.  It is not difficult to see that $A_j(\pi)$ occurs if and only if $L_{m,k}(\sig)=k$ occurs, and that $\pi$ being chosen uniformly at random implies $\sig$ is chosen uniformly at random.
		\end{proof}
		Let $p_k=\Pr[L_{m,k}(\sig)=k]$ and let $t$ be the integer such that $t!\le n&lt;(t+1)!$.  The claim above implies that for all $k$ we have
		{\small \begin{equation}\Pr[L_{m,n}(\pi)\ge k]\ge \Pr\l[\bigcup A_j(\pi)\r]=1-\Pr\l[\bigcap A_j^c(\pi)\r]=1-(1-p_k)^{\floor{n/k}}\ge 1- \exp\l(-\f{ t!p_k}{2k}\r),\label{eq:expLower}\end{equation}}%
		with this last step using $\floor{n/k}\ge n/2k$ for $k\le n$, that $1-p_k\le e^{-p_k}$, and that $n\ge t!$.
		
		It is easy to see by definition that $p_k\ge 1/k!$ for all $m,k$; and for $n$ sufficiently large, we have $-e^{-t/2}\ge -t^{-1}$.  For such $n$, by \eqref{eq:expLower} we have for all $k\le t-2$ that
		\begin{equation}\Pr[L_{m,n}(\pi)\ge k]\ge 1- \exp\l(-\f{t!}{2k\cdot k!}\r) \ge 1-\exp\l(-\f{t}{2}\r)\ge 1-t^{-1}.\label{eq:small}\end{equation}
		Summing this bound over all $k\le t-2$ for $m=1$ gives 
		\[\E[L_{1,n}(\pi)]\ge \sum_{k\le t-2} \Pr[L_{1,n}(\pi)\ge k]\ge t-3.\]
		This gives the desired lower bound of $\Gam^{-1}(n)+\Om(1)$ for $m=1$ since $t\ge \Gam^{-1}(n)-2$.
		
		We now consider $m\ge 2$.  By Proposition~\ref{prop:lowerCont} we have for $k$ sufficiently large in terms of $m$ that $p_k\ge \f{(m/1.03)^k}{2k\cdot k!}$.  Let $n$ be large enough in terms of $m$ so that this bound holds for $k\ge t$.  Also let $n$ be large enough so that $\f{\log m}{\log t}\le 1$.  By Lemma~\ref{lem:asy}, if $t\le k\le t+\f{\log m}{100\log t}t\le 1.01t$, then $k!\le t! (1.1)^k m^{t/100}$.  Thus by \eqref{eq:expLower} we have
		\begin{align*}\Pr[L_{m,n}(\pi)\ge k]&amp;\ge 1-\exp\l(-\f{(m/1.03)^k}{4k^2 (1.1)^k m^{t/100}}\r)\ge 1-\exp\l(-\f{m^{.99t}}{4k^2\cdot (1.14)^{1.01t}}\r)\\&amp;\ge 1-\exp\l(-\f{(1.7)^t}{8t^2}\r),\end{align*}
		where this last step used $m\ge 2$.  This quantity is at least $1/2$ for $n$ (and hence $t$) sufficiently large.  Using this together with \eqref{eq:small} for $k\le t-2$ gives, for $n$ sufficiently large in terms of $m$,
		 \[\E[L_{m,n}(\pi)]\ge t-3+\sum_{t\le k\le t+\f{\log m}{100\log t}t} \Pr[L_{m,n}(\pi)\ge k] \ge t-3+\l(\f{\log m}{100\log t}t\r)\cdot \half,\]
		 proving the desired result.
	\end{proof}
	%\SS{I think taking $k\le t+(1-100/\log m)\f{\log m}{\log t}t$ would let us prove an asymptotic lower bound of $t+(\log m/\log t)t+\Om(1+t/\log t)$, which I suppose is not as meaningful if we think of $m$ as fixed.  In any case the result becomes uglier unless we can get the same error term as the other guy, which requires looking at $k\le t+(1-100/t)(\log m/\log t)t$ and this in turn requires better bounds on the 1.03 type bounds.}
	
	%\SS{In terms of dependencies: we need $t\ge m$ which basically means $n\ge e^m$.  More substantially we need $k\ge m^{\log m}$ when $k\ge t$, and this means we roughly need $n\ge e^{m^{\log m}}$.  Note that this is the worst dependency we have, so the entire proof goes through as long as this dependency holds.}
	\fi 
	\section{Concluding Remarks}
	In this paper we solved a conjecture of Diaconis, Graham, He, and Spiro~\cite{DGHS21} by asymptotically determining $\E[L^1_{m,n}(\pi)]$ provided $n$ is sufficiently large in terms of $m$.  Using similar ideas, it is possible to compute the asymptotic limit of the $r^{\text{th}}$ moment $\E[L^1_{m,n}(\pi)^r]$ for any fixed $r$.  Based off of computational evidence for these higher moments, we conjecture the following:
	
	
	%Computational evidence suggests that $L^1_{m,n}(\pi)$ converges to a normal distribution as $m$ tends to infinity provided $n$ is sufficiently large in terms of $m$.  One approach to proving this would be to show the following.
	\begin{conj}\label{conj:strong}
	For all $r\ge 1$, if $n$ is sufficiently large in terms of $m$, then
	\[\E[(L^1_{m,n}(\pi)-\mu)^r]=c_r m^{\floor{r/2}} +O(m^{\floor{r/2}-1}),\]
	where $\mu=\E[L^1_{m,n}(\pi)]$ and
	\[c_r=\begin{cases} \dfrac{r!}{2^{r/2}(r/2)!} &amp; r\tr{ even},\\
	\dfrac{r!}{3\cdot 2^{(r-1)/2}((r-3)/2)!} &amp; r\tr{ odd}.\end{cases}\]
	\end{conj}
	One can show that the standard deviation $\sig$ of $L^1_{m,n}(\pi)$ is asymptotic to $m^{1/2}$.  Thus, this conjecture would imply that the standardized moments $(\f{L^1_{m,n}(\pi)-\mu}{\sig})^r$ converge to 0 for $r$ odd and to $\f{r!}{2^{r/2}(r/2)!}$ for $r$ even.  These are exactly the moments of a standard normal distribution, and actually this fact would imply that $(L_{m,n}^1(\pi)-\mu)/\sig$ converges in distribution to a standardized normal distribution, see for example \cite[Corollary 21.8]{frieze2016introduction}.
	
	Perhaps a first step towards proving Conjecture~\ref{conj:strong} would be to get a better understanding of the (non-centralized) moments $\E[L_{m,n}^1(\pi)^r]$, and to this end we conjecture the following:
	\begin{conj}
	For all $r\ge 1$, if $n$ is sufficiently large in terms of $m$, then \[\E[L^1_{m,n}(\pi)^r]=m^r+{\binom{r+1}{2}} m^{r-1}+O(m^{r-2}).\]
	\end{conj}
	We can prove that the $r^{\text{th}}$ moment is asymptotic to $m^r$, but we do not know how to determine the coefficient of $m^{r-1}$.  We were unable to observe any pattern for the coefficients of lower order terms.
	
	
	In this paper, we considered continuously increasing subsequences in multiset permutations, and it is natural to consider other types of subsequences in multiset permutations.  Perhaps the most natural to consider is the following:
	\begin{quest}\label{quest:longestInc}
	For $\pi\in \S_{m,n}$, let $\widetilde{L}_{m,n}(\pi)$ denote the length of a longest increasing subsequence in $\pi$.  What is $\E[\widetilde{L}_{m,n}(\pi)]$ asymptotic to when $m$ is fixed?
	\end{quest}
	When $m=1$ it is well known that $\E[\widetilde{L}_{1,n}(\pi)]\sim 2\sqrt{n}$ (see~\cite{Rom}), so Question~\ref{quest:longestInc} is a natural generalization of this classical problem.  See also recent work of Almeanazel and Johnson \cite{AMJ20} for some results concerning the distribution of $\widetilde{L}_{m,n}(\pi)$.



\acknowledgements{We thank S. Venkitesh for fruitful conversations and Persi Diaconis for comments regarding an earlier draft.  We thank the Graduate Student Combinatorics Conference 2021 for hosting an open problem session, at which the fourth author presented the problem which inspired this work.}

%% 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}
</pre></body></html>