cp's OEIS Frontend

A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.

%I A003316 M2930 #57 Apr 24 2024 13:24:43
%S A003316 1,3,12,58,335,2261,17465,152020,1473057,15730705,183571817,
%T A003316 2324298010,31737207034,464904410985,7272666016725,121007866402968,
%U A003316 2133917906948645,39756493513248129,780313261631908137,16093326774432620874,347958942706716524974
%N A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.
%D A003316 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003316 Alois P. Heinz, <a href="/A003316/b003316.txt">Table of n, a(n) for n = 1..80</a>
%H A003316 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 A003316 R. P. Stanley, <a href="/A003277/a003277.pdf">Letter to N. J. A. Sloane, c. 1991</a>
%H A003316 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 A003316 Wikipedia, <a href="https://en.wikipedia.org/wiki/Longest_increasing_subsequence">Longest increasing subsequence</a>
%F A003316 From _Alois P. Heinz_, Nov 04 2018: (Start)
%F A003316 a(n) = Sum_{k=1..n} k * A047874(n,k).
%F A003316 A321274(n) < a(n) < A321273(n) for n > 1. (End)
%F A003316 A theorem of Vershik and Kerov (1977) implies that a(n) ~ 2 * sqrt(n) * n!. - _Ludovic Schwob_, Apr 04 2024
%p A003316 h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j+
%p A003316       add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:
%p A003316 g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p A003316                 add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
%p A003316 a:= n-> add(k* (g(n-k, k, [k])), k=1..n):
%p A003316 seq(a(n), n=1..22);  # _Alois P. Heinz_, Jul 05 2012
%t A003316 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 A003316 Cf. A008304 (which is concerned with runs of adjacent elements).
%Y A003316 Row sums of A214152.
%Y A003316 Cf. A047874, A321273, A321274.
%K A003316 nonn,nice,easy
%O A003316 1,2
%A A003316 _N. J. A. Sloane_ and _Richard Stanley_
%E A003316 Corrected a(13) and extended beyond a(16) by _Alois P. Heinz_, Jul 05 2012