Continuously Increasing Subsequences of Random Multiset Permutations

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$ 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.

19 pages