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).
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
KEYWORD
nonn,nice,easy
AUTHOR
EXTENSIONS
Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012
STATUS
approved