cp's OEIS Frontend

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

%I A321273 #24 Oct 31 2021 07:47:33
%S A321273 1,4,14,70,396,2628,20270,175392,1686374,17920528,208454628,
%T A321273 2629931688,35774761662,522351495684,8149929922408,135284126840592,
%U A321273 2380119357533974,44243729657494640,866599471539160876,17839886344238238784,385065445154671172880,8695565142604747421416
%N A321273 Sum over all permutations of [n] of the maximum of the lengths of increasing or decreasing subsequences.
%H A321273 Alois P. Heinz, <a href="/A321273/b321273.txt">Table of n, a(n) for n = 1..60</a>
%H A321273 Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>
%F A321273 A321274(n) < A003316(n) < a(n) for n > 1.
%p A321273 h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
%p A321273     l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
%p A321273 f:= l-> h(l)^2*max(l[1], nops(l)):
%p A321273 g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
%p A321273      g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
%p A321273 a:= n-> g(n$2, []):
%p A321273 seq(a(n), n=1..23);
%t A321273 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]];
%t A321273 f[l_] := h[l]^2 Max[l[[1]], Length[l]];
%t A321273 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]]];
%t A321273 a[n_] := g[n, n, {}];
%t A321273 Table[a[n], {n, 1, 23}] (* _Jean-François Alcover_, Oct 31 2021, after _Alois P. Heinz_ *)
%Y A321273 Cf. A003316, A321274, A321275, A321276, A321277, A321278.
%K A321273 nonn
%O A321273 1,2
%A A321273 _Alois P. Heinz_, Nov 01 2018