|
%I #16 Jun 09 2015 13:37:01
%S 0,0,0,2,15,122,990,9210,91013,1001285,11774254,150849588,2059781391
%N 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).
%C 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,...
%H A. Godbole, <a href="http://faculty.etsu.edu/godbolea/Publications.pdf">Publications</a> (lists some related sequences)
%H Manfred Scheucher, <a href="/A168502/a168502.c.txt">C Code</a>
%Y Cf. A167995, A167999.
%K nonn,more
%O 1,4
%A _Anant Godbole_, Brad Wild, Stephanie Goins, Nov 27 2009
%E a(9)-a(13) from _Manfred Scheucher_, Jun 08 2015
|
