A321276 Sum over all permutations of [n] of the length of the longest increasing subsequence raised to the power of the length of the longest decreasing subsequence.

1, 3, 20, 174, 1915, 25861, 407691, 7330188, 148016449, 3312032213, 81207824255, 2162810487154, 62125097028962, 1913156511113517, 62839800627095263, 2191735865280260976, 80859575674731497805, 3144804693463679033629, 128550453029684197431607

Offset: 1

Author

Alois P. Heinz, Nov 01 2018

Keywords

• nonn

Links

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

Crossrefs

Cf. A003316, A321273, A321274, A321275, A321277, A321278.

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