A003316 - OEIS

%I M2930 #57 Apr 24 2024 13:24:43

%S 1,3,12,58,335,2261,17465,152020,1473057,15730705,183571817,

%T 2324298010,31737207034,464904410985,7272666016725,121007866402968,

%U 2133917906948645,39756493513248129,780313261631908137,16093326774432620874,347958942706716524974

%N Sum of lengths of longest increasing subsequences of all permutations of n elements.

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

%H Alois P. Heinz, <a href="/A003316/b003316.txt">Table of n, a(n) for n = 1..80</a>

%H R. M. Baer and P. Brock, <a href="http://dx.doi.org/10.1090/S0025-5718-1968-0228216-8">Natural sorting over permutation spaces</a>, Math. Comp. 22 1968 385-410.

%H R. P. Stanley, <a href="/A003277/a003277.pdf">Letter to N. J. A. Sloane, c. 1991</a>

%H A. M. Vershik and S. V. Kerov, <a href="https://www.mathnet.ru/links/c3b6956691dc50ecab786613a2113123/dan40430.pdf">Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux</a>, Doklady Akademii Nauk SSSR, 1977, Volume 233, Number 6, Pages 1024-1027. In Russian.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>

%F From _Alois P. Heinz_, Nov 04 2018: (Start)

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

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

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

%p h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j+

%p       add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:

%p g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,

%p                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):

%p a:= n-> add(k* (g(n-k, k, [k])), k=1..n):

%p seq(a(n), n=1..22);  # _Alois P. Heinz_, Jul 05 2012

%t 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_ *)

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

%Y Row sums of A214152.

%Y Cf. A047874, A321273, A321274.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_ and _Richard Stanley_

%E Corrected a(13) and extended beyond a(16) by _Alois P. Heinz_, Jul 05 2012