A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements. (Formerly M2930)

1, 3, 12, 58, 335, 2261, 17465, 152020, 1473057, 15730705, 183571817, 2324298010, 31737207034, 464904410985, 7272666016725, 121007866402968, 2133917906948645, 39756493513248129, 780313261631908137, 16093326774432620874, 347958942706716524974

Offset

1,2

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

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

R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.

R. P. Stanley, Letter to N. J. A. Sloane, c. 1991

A. M. Vershik and S. V. Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Doklady Akademii Nauk SSSR, 1977, Volume 233, Number 6, Pages 1024-1027. In Russian.

Wikipedia, Longest increasing subsequence

Formula

From Alois P. Heinz, Nov 04 2018: (Start)

a(n) = Sum_{k=1..n} k * A047874(n,k).

A321274(n) < a(n) < A321273(n) for n > 1. (End)

A theorem of Vershik and Kerov (1977) implies that a(n) ~ 2 * sqrt(n) * n!. - Ludovic Schwob, Apr 04 2024

Maple

h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j+
      add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> add(k* (g(n-k, k, [k])), k=1..n):
seq(a(n), n=1..22);  # Alois P. Heinz, Jul 05 2012

Mathematica

h[l_List] := Module[{n = Length[l]}, Total[l]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_] := Sum[k*g[n-k, k, {k}], {k, 1, n}]; Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)

Crossrefs

Cf. A008304 (which is concerned with runs of adjacent elements).

Row sums of A214152.

Cf. A047874, A321273, A321274.

Sequence in context: A020075 A020030 A121393 * A298419 A126959 A181328

Adjacent sequences: A003313 A003314 A003315 * A003317 A003318 A003319

Keyword

nonn,nice,easy,changed

Author

N. J. A. Sloane and Richard Stanley

Extensions

Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012

Status

approved