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

Author

Alois P. Heinz, Nov 01 2018

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..70
• Wikipedia, Longest increasing subsequence

Crossrefs

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

Programs

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);