A321274 Sum over all permutations of [n] of the minimum of the lengths of longest increasing subsequence and longest decreasing subsequence.

1, 2, 10, 46, 274, 1894, 14660, 128648, 1259740, 13540882, 158689006, 2018664332, 27699652406, 407457326286, 6395402111042, 106731605965344, 1887716456363316, 35269257369001618, 694027051724655398, 14346767204627002964, 310852440258761877068, 7045172291061429434354

Offset

1,2

Links

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

Wikipedia, Longest increasing subsequence

Formula

a(n) < A003316(n) < A321273(n) for n > 1.

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*min(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);

Crossrefs

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

Sequence in context: A009640 A191684 A081167 * A166107 A034429 A242638

Adjacent sequences: A321271 A321272 A321273 * A321275 A321276 A321277

Keyword

nonn

Author

Alois P. Heinz, Nov 01 2018

Status

approved