Number of longest increasing subsequences.

Abstract

We study the entropy S of longest increasing subsequences (LISs), i.e., the logarithm of the number of distinct LISs. We consider two ensembles of sequences, namely, random permutations of integers and sequences drawn independent and identically distributed (i.i.d.) from a limited number of distinct integers. Using sophisticated algorithms, we are able to exactly count the number of LISs for each given sequence. Furthermore, we are not only measuring averages and variances for the considered ensembles of sequences, but we sample very large parts of the probability distribution p(S) with very high precision. Especially, we are able to observe the tails of extremely rare events which occur with probabilities smaller than 10^{-600}. We show that the distribution of the entropy of the LISs is approximately Gaussian with deviations in the far tails, which might vanish in the limit of long sequences. Further, we propose a large-deviation rate function which fits best to our observed data.