#####
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 *L*_{i}(π) to be the length of the longest subsequence of the form *i*(*i*+1)...*j*, and we let
*L*(π) := max_{i}*L*_{i}(π).
In this paper we estimate the expected values
of *L*^{1}(π) 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**[*L*^{1}(π)] ~ *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: