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

0, 1, 2, 12, 61, 367, 2805, 23372, 213317, 2189823, 24882811, 305633678, 4037554628, 57447084699, 877263905683, 14276260437624, 246201450585329, 4487236144246511, 86286209907252739, 1746559569805617910, 37106502447954647906, 825196425771658993531

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, A321278, 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*abs(l[1]-nops(l))/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} abs(k) * A321316(n,k).