This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements. (Formerly M2930) 15
 1, 3, 12, 58, 335, 2261, 17465, 152020, 1473057, 15730705, 183571817, 2324298010, 31737207034, 464904410985, 7272666016725, 121007866402968, 2133917906948645, 39756493513248129, 780313261631908137, 16093326774432620874, 347958942706716524974 (list; graph; refs; listen; history; text; internal format)
 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 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) 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 AUTHOR EXTENSIONS Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 23 05:56 EDT 2019. Contains 328335 sequences. (Running on oeis4.)