How many longest increasing subsequences are there?

Phil Krabbe, Hendrik Schawe, Alexander K. Hartmann

We study the entropy $S$ of longest increasing subsequences (LIS), i.e., the logarithm of the number of distinct LIS. We consider two ensembles of sequences, namely random permutat…