Longest Increasing Scattered Subsequence

The longest increasing scattered subsequence is the longest subsequence of increasing terms, where intervening nonincreasing terms may be dropped. Finding the largest scattered subsequence is a much harder problem. For example, the longest increasing scattered subsequence of the permutation is , whereas the longest contiguous subsequence is .

Any sequence of distinct integers must contain either an increasing or decreasing scattered subsequence of length (Erdős and Szekeres 1935; Skiena 1990, p. 75).

Let count the permutations of whose longest increasing scattered subsequence has length . Li (2026) proved that these counts form a strictly logarithmically concave sequence at the interior indices. More precisely,

for and , proving a conjecture of Chen (2008).