login
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).
4
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
A. Godbole, Publications (lists some related sequences)
Manfred Scheucher, C Code
CROSSREFS
Sequence in context: A341929 A185758 A052448 * A369108 A127610 A085228
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