cp's OEIS Frontend

A321278 One half of the sum over all permutations of [n] of the squared difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.

%I A321278 #17 Apr 01 2019 15:37:56
%S A321278 0,1,4,18,105,699,5285,45128,431223,4540775,52268029,653096124,
%T A321278 8810538490,127622293057,1975379879871,32537074533872,568268861724191,
%U A321278 10490690233451583,204118868130889733,4174977363687339452,89554055679215605982,2010207472655266461533
%N A321278 One half of the sum over all permutations of [n] of the squared difference between the length of the longest increasing subsequence and the length of the longest decreasing subsequence.
%H A321278 Alois P. Heinz, <a href="/A321278/b321278.txt">Table of n, a(n) for n = 1..80</a>
%H A321278 Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>
%F A321278 a(n) = (1/2) * Sum_{k=1-n..n-1} k^2 * A321316(n,k).
%p A321278 h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
%p A321278     l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
%p A321278 f:= l-> h(l)^2*(l[1]-nops(l))^2/2:
%p A321278 g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
%p A321278      g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
%p A321278 a:= n-> g(n$2, []):
%p A321278 seq(a(n), n=1..23);
%Y A321278 Cf. A003316, A321273, A321274, A321275, A321276, A321277, A321316.
%K A321278 nonn
%O A321278 1,3
%A A321278 _Alois P. Heinz_, Nov 01 2018