

A331883


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.


0




OFFSET

1,4


COMMENTS

Only permutations whose longest increasing subsequence is at most n/2 need to be considered.


LINKS

Table of n, a(n) for n=1..9.
Wikipedia, Longest increasing subsequence problem


EXAMPLE

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.
The a(4) = 5 permutations are:
[2,1,4,3],
[2,4,1,3],
[3,1,4,2],
[3,4,1,2],
[4,3,2,1].


CROSSREFS

Cf. A047874, A047887, A167995.
Sequence in context: A003583 A033115 A033123 * A047770 A047757 A047755
Adjacent sequences: A331880 A331881 A331882 * A331884 A331885 A331886


KEYWORD

nonn,more


AUTHOR

Ildar Gainullin, Jan 30 2020


STATUS

approved



