login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

N. J. A. Sloane and Richard Stanley

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.

License Agreements, Terms of Use, Privacy Policy. .

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