A331883 - OEIS

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, 1, 1, 5, 26, 132, 834, 6477, 56242

(list; graph; refs; listen; history; text; internal format)

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