Séminaire Lotharingien de Combinatoire, 86B.4 (2022), 11 pp.
Alexander Clifton, Bishal Deb, Yifeng Huang, Sam Spiro and Semin Yoo
Continuously Increasing Subsequences of Random Multiset Permutations
Abstract.
For a word π and integer i, we define Li(π) to be the length of the longest subsequence of the form i(i+1)...j, and we let
L(π) := maxiLi(π).
In this paper we estimate the expected values
of L1(π) and L(π) when π is chosen
uniformly at random from all words which use each of the
first n positive integers exactly m times. We show
that E[L1(π)] ~ 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 E[L(π)] is asymptotic to the inverse gamma
function Γ-1(n) if n is sufficiently large in terms of m
as m tends towards infinity.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: