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: