A168502 For each permutation of {1,2,...,n} one or more integers might not be part of any longest increasing subsequence (LIS) of that permutation. The sequence lists the number of permutations for which ceiling(n/2) is not part of any LIS. For example, if n=4, 2 is not in any LIS of the two permutations (1342) and (3421).

0, 0, 0, 2, 15, 122, 990, 9210, 91013, 1001285, 11774254, 150849588, 2059781391

Offset

1,4

Comments

The sequence lists the minimal term of members of the array n=1 {0} n=2 {0,0} n=3 {1,0,1} n=4 {6,2,2,6} n=5 {37,18,15,18,37} n=6 {257,153,122,122,153,257} n=7{1998,1338,1081,990,1081,1338,1998} n=8 {17280,12449,10298,9210,9210,10298,12449,17280}. The j-th row above lists the number of permutations on {1,2,...,j} for which 1,2,3,...,j are not part of any LIS. An alternative sequence would list the maximal terms in the rows above as 0,0,1,6,37,257,1998,17280,...

Links

Table of n, a(n) for n=1..13.

A. Godbole, Publications (lists some related sequences)

Manfred Scheucher, C Code

Crossrefs

Cf. A167995, A167999.

Sequence in context: A341929 A185758 A052448 * A369108 A127610 A085228

Adjacent sequences: A168499 A168500 A168501 * A168503 A168504 A168505

Keyword

nonn,more

Author

Anant Godbole, Brad Wild, Stephanie Goins, Nov 27 2009

Extensions

a(9)-a(13) from Manfred Scheucher, Jun 08 2015

Status

approved