A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.
1, 3, 12, 58, 335, 2261, 17465, 152020, 1473057, 15730705, 183571817, 2324298010, 31737207034, 464904410985, 7272666016725, 121007866402968, 2133917906948645, 39756493513248129, 780313261631908137, 16093326774432620874, 347958942706716524974
Offset: 1
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
Crossrefs
Programs
-
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 *)
Formula
From Alois P. Heinz, Nov 04 2018: (Start)
a(n) = Sum_{k=1..n} k * A047874(n,k).
A theorem of Vershik and Kerov (1977) implies that a(n) ~ 2 * sqrt(n) * n!. - Ludovic Schwob, Apr 04 2024
Extensions
Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012