login
A321273
Sum over all permutations of [n] of the maximum of the lengths of increasing or decreasing subsequences.
7
1, 4, 14, 70, 396, 2628, 20270, 175392, 1686374, 17920528, 208454628, 2629931688, 35774761662, 522351495684, 8149929922408, 135284126840592, 2380119357533974, 44243729657494640, 866599471539160876, 17839886344238238784, 385065445154671172880, 8695565142604747421416
OFFSET
1,2
FORMULA
A321274(n) < A003316(n) < a(n) for n > 1.
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 01 2018
STATUS
approved