|
Search: id:A132889
|
|
|
| A132889 |
|
Sum of the lengths of the longest increasing subsequence over all 321-avoiding permutations of [n]. |
|
+0
1
|
|
| 1, 3, 11, 39, 144, 530, 1987, 7455, 28268, 107334, 410354, 1570954, 6042984, 23273172, 89948835, 348000975, 1350028020, 5241881150, 20396787070, 79426533758, 309829067496, 1209384071532, 4727454837846, 18490127530394
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
a(n)=sum(k*A126217(n,k), k=1..n).
|
|
REFERENCES
|
E. Deutsch, A. J. Hildebrand, and H. S. Wilf, Longest increasing subsequences in pattern-restricted permutations, The Electronic Journal of Combinatorics, 9(2), 2003, #R12.
|
|
FORMULA
|
a(n)=Sum(k(2k-n+1)^2*binom(n+1,n-k)^2, k=floor((n+1)/2)..n)/(n+1)^2.
|
|
EXAMPLE
|
a(3)=11 because in the 321-avoiding permutations of 123, namely 123,132,312,213, and 231, the lengths of the longest increasing subsequences are 3,2,2,2, and 2, respectively.
|
|
MAPLE
|
a:=proc(n) options operator, arrow: (sum(k*(2*k-n+1)^2*binomial(n+1, n-k)^2, k =floor((1/2)*n+1/2)..n))/(n+1)^2 end proc: seq(a(n), n=1..25);
|
|
CROSSREFS
|
Cf. A126217.
Sequence in context: A002783 A007482 A134760 this_sequence A149061 A149062 A066979
Adjacent sequences: A132886 A132887 A132888 this_sequence A132890 A132891 A132892
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2007
|
|
|
Search completed in 0.002 seconds
|
