A321273 Sum over all permutations of [n] of the maximum of the lengths of increasing or decreasing subsequences.

1, 4, 14, 70, 396, 2628, 20270, 175392, 1686374, 17920528, 208454628, 2629931688, 35774761662, 522351495684, 8149929922408, 135284126840592, 2380119357533974, 44243729657494640, 866599471539160876, 17839886344238238784, 385065445154671172880, 8695565142604747421416

Offset: 1

Author

Alois P. Heinz, Nov 01 2018

Keywords

• nonn

Links

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

Crossrefs

Cf. A003316, A321274, A321275, 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*max(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);

Mathematica

h[l_] := Function[n, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[j > l[[k]], 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, 1, n}]][Length[l]];
f[l_] := h[l]^2 Max[l[[1]], Length[l]];
g[n_, i_, l_] := If[n == 0 || i == 1, f[Join[l, Table[1, {n}]]], g[n, i - 1, l] + g[n - i, Min[i, n - i], Append[l, i]]];
a[n_] := g[n, n, {}];
Table[a[n], {n, 1, 23}] (* Jean-François Alcover, Oct 31 2021, after Alois P. Heinz *)

Formula

A321274(n) < A003316(n) < a(n) for n > 1.