A321275 Sum over all permutations of [n] of the product of the lengths of longest increasing subsequence and longest decreasing subsequence.

1, 4, 22, 132, 890, 6812, 58422, 555900, 5819658, 66554180, 825839718, 11054124886, 158795559000, 2437248222710, 39809464449676, 689538524084168, 12625142440334342, 243656361772961292, 4943801229819987022, 105212500452414418118, 2343513475564027153128

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..70

Wikipedia, Longest increasing subsequence

Maple

h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
    l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
f:= l-> h(l)^2*l[1]*nops(l):
g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
     g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
a:= n-> g(n$2, []):
seq(a(n), n=1..23);

Crossrefs

Cf. A003316, A321273, A321274, A321276, A321277, A321278.

Sequence in context: A356283 A292838 A193620 * A274745 A197657 A183280

Adjacent sequences: A321272 A321273 A321274 * A321276 A321277 A321278

Keyword

nonn

Author

Alois P. Heinz, Nov 01 2018

Status

approved