login
Table T(n,k) counts the involutions of n with longest increasing contiguous subsequence of length k.
1

%I #18 Sep 08 2016 10:19:55

%S 1,1,1,1,2,1,1,6,2,1,1,14,8,2,1,1,37,27,8,2,1,1,96,94,30,8,2,1,1,270,

%T 338,114,30,8,2,1,1,777,1237,446,118,30,8,2,1,1,2370,4684,1809,473,

%U 118,30,8,2,1,1,7450,18142,7502,1964,478,118,30,8,2,1,1,24485,72524,32093,8414,1998,478,118,30,8,2,1

%N Table T(n,k) counts the involutions of n with longest increasing contiguous subsequence of length k.

%C Reverse of rows converges to 1,2,8,30,118,478,2004,8666,..

%e T(4,2) = 6 because the 6 involutions with longest increasing contiguous subsequence lengths equal to 2 are: 1324, 1432, 2143, 3214, 3412, 4231.

%e Table starts:

%e 1;

%e 1, 1;

%e 1, 2, 1;

%e 1, 6, 2, 1;

%e 1, 14, 8, 2, 1;

%e 1, 37, 27, 8, 2, 1;

%e 1, 96, 94, 30, 8, 2, 1;

%e 1, 270, 338, 114, 30, 8, 2, 1;

%t (* first do *)

%t Needs["Combinatorica`"]

%t (* then *)

%t maxISS[perm_List] := Max[0, (Max @@ (Length[#1]*Sign[First[#1]] & ) /@ Split[Sign[Rest[#1] - Drop[#1, -1]]] & )[perm]];classMaxISS[par_?PartitionQ]:=Count[ maxISS/@( TableauxToPermutation[FirstLexicographicTableau[par], #]&/@Tableaux[par] ) ,#]&/@(-1+Range[ Tr[par] ]);

%t Table[Apply[Plus,classMaxISS/@Partitions[n]],{n,2,6}];

%Y Cf. A008304; row sums are A000085; A047884 removes the contiguity requirement.

%K nonn,tabl

%O 1,5

%A _Wouter Meeussen_, Dec 20 2010

%E Definition corrected by _Wouter Meeussen_, Dec 22 2010