|
| |
|
|
A003316
|
|
Sum of lengths of longest increasing subsequences of all permutations of n elements.
(Formerly M2930)
|
|
3
|
|
|
|
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
|
Baer, R. M.; Brock, P.; Natural sorting over permutation spaces. Math. Comp. 22 1968 385-410.
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..55
|
|
|
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
|
|
|
CROSSREFS
|
Cf. A008304 (which is concerned with runs of adjacent elements).
Row sums of A214152.
Sequence in context: A020075 A020030 A121393 * A126959 A181328 A058861
Adjacent sequences: A003313 A003314 A003315 * A003317 A003318 A003319
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane, R. P. Stanley
|
|
|
EXTENSIONS
|
Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012
|
|
|
STATUS
|
approved
|
| |
|
|
