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.

0, 1, 4, 18, 105, 699, 5285, 45128, 431223, 4540775, 52268029, 653096124, 8810538490, 127622293057, 1975379879871, 32537074533872, 568268861724191, 10490690233451583, 204118868130889733, 4174977363687339452, 89554055679215605982, 2010207472655266461533

Offset: 1

Author

Alois P. Heinz, Nov 01 2018

Keywords

• nonn

Links

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

Crossrefs

Cf. A003316, A321273, A321274, A321275, A321276, A321277, A321316.

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))^2/2:
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);

Formula

a(n) = (1/2) * Sum_{k=1-n..n-1} k^2 * A321316(n,k).