cp's OEIS Frontend

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.

%I A321277 #16 Apr 01 2019 15:26:52
%S A321277 0,1,2,12,61,367,2805,23372,213317,2189823,24882811,305633678,
%T A321277 4037554628,57447084699,877263905683,14276260437624,246201450585329,
%U A321277 4487236144246511,86286209907252739,1746559569805617910,37106502447954647906,825196425771658993531
%N 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.
%H A321277 Alois P. Heinz, <a href="/A321277/b321277.txt">Table of n, a(n) for n = 1..80</a>
%H A321277 Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>
%F A321277 a(n) = (1/2) * Sum_{k=1-n..n-1} abs(k) * A321316(n,k).
%p A321277 h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>
%p A321277     l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
%p A321277 f:= l-> h(l)^2*abs(l[1]-nops(l))/2:
%p A321277 g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),
%p A321277      g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):
%p A321277 a:= n-> g(n$2, []):
%p A321277 seq(a(n), n=1..23);
%Y A321277 Cf. A003316, A321273, A321274, A321275, A321276, A321278, A321316.
%K A321277 nonn
%O A321277 1,3
%A A321277 _Alois P. Heinz_, Nov 01 2018