Natural Sorting Over Permutation Spaces
R. M. Baer, P. Brock · Mathematics of Computation · 1968
Introduction.In this paper we continue the study, begun in [1], of some combinatorial problems related to monotonicities that occur in certain spaces of finite sequences.These spaces are equipped with standard probability measures, so that one may study the distribution of monotonicities in such spaces and, in particular, the expected lengths of maximal monotonie subsequences.These, in turn, are upper bounds on the expected lengths of monotonie subsequences obtained by applying some selection process over the space of sequences.The problem which we have called natural sorting is concerned with the maximization of these expected