The Ulam-Hammersley problem for multiset permutations

Lucas Gerin

We obtain the asymptotic behaviour of the longest increasing/non-decreasing subsequences in a random uniform multiset permutation in which each element in {1,...,n} occurs k times,…