%I #18 Feb 12 2020 08:20:49
%S 0,1,1,5,26,132,834,6477,56242
%N The number of permutations in the symmetric group S_n in which it is possible to find two disjoint increasing subsequences each with length equal to the length of the longest increasing subsequence of the permutation.
%C Only permutations whose longest increasing subsequence is at most n/2 need to be considered.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem">Longest increasing subsequence problem</a>
%e a(3) = 1 because the only permutation whose longest increasing subsequence is 1 is [3,2,1] and this contains two disjoint increasing subsequences of length 1.
%e The a(4) = 5 permutations are:
%e [2,1,4,3],
%e [2,4,1,3],
%e [3,1,4,2],
%e [3,4,1,2],
%e [4,3,2,1].
%Y Cf. A047874, A047887, A167995.
%K nonn,more
%O 1,4
%A _Ildar Gainullin_, Jan 30 2020
|