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,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..80

Wikipedia, Longest increasing subsequence

Formula

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

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);

Crossrefs

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

Sequence in context: A231274 A051827 A007711 * A020114 A354015 A009597

Adjacent sequences: A321275 A321276 A321277 * A321279 A321280 A321281

Keyword

nonn

Author

Alois P. Heinz, Nov 01 2018

Status

approved