2025/01/12 by Pittel, Boris
#05C05 #60C05 #92510 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2501.06905
Counting permutations of [n] by the number of records, i.e. left-to-right maxima, is a classic problem in combinatorial enumeration. In the first volume of ``The Art of Computer Programming", Donald Knuth demonstrated its relevance for analysis of average case complexity of a basic algorithm for determining a maximum in a linear list of numbers. It is well known that the expected, and likely, number of those records in a \it uniformly\/ random permutation is asymptotic to log n. Cyril Banderier, Rene Beier, and Kurt Mehlhorn studied the case of a non-uniform random permutation, which is obtained from a generic permutation of [n] by selecting its elements one after another independently with probability p, and permuting the selected elements uniformly at random. They proved that En(p), the largest expected number of the maxima, is between const√(n/p) and O(√((n/p)log n)) if p is fixed. For p≫ 1/n and simultaneously 1-p≥ const n-1/2log n, we prove that En(p) is exactly of order (1-p)√(n/p).