login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 30 00:10 EDT 2020. Contains 334710 sequences. (Running on oeis4.)