A321275 - OEIS

%I #9 Nov 03 2018 15:34:23

%S 1,4,22,132,890,6812,58422,555900,5819658,66554180,825839718,

%T 11054124886,158795559000,2437248222710,39809464449676,

%U 689538524084168,12625142440334342,243656361772961292,4943801229819987022,105212500452414418118,2343513475564027153128

%N Sum over all permutations of [n] of the product of the lengths of longest increasing subsequence and longest decreasing subsequence.

%H Alois P. Heinz, <a href="/A321275/b321275.txt">Table of n, a(n) for n = 1..70</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>

%p h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(j>

%p     l[k], 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):

%p f:= l-> h(l)^2*l[1]*nops(l):

%p g:= (n, i, l)-> `if`(n=0 or i=1, f([l[], 1$n]),

%p      g(n, i-1, l) +g(n-i, min(i, n-i), [l[], i])):

%p a:= n-> g(n$2, []):

%p seq(a(n), n=1..23);

%Y Cf. A003316, A321273, A321274, A321276, A321277, A321278.

%K nonn

%O 1,2

%A _Alois P. Heinz_, Nov 01 2018