|
| |
|
|
A132889
|
|
Sum of the lengths of the longest increasing subsequence over all 321-avoiding permutations of [n].
|
|
0
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| 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 * A149061 A149062 A066979
Adjacent sequences: A132886 A132887 A132888 * A132890 A132891 A132892
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2007
|
| |
|
|
