login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A061061
Maximal number of 132 patterns in a permutation of 1,2,...,n.
7
0, 0, 1, 3, 6, 12, 20, 31, 46, 64, 87, 115, 147, 186, 231, 282, 342, 408, 482, 566, 657, 759, 871, 991, 1126, 1270, 1424, 1594, 1774, 1968, 2177, 2397, 2635, 2887, 3151, 3436, 3735, 4050, 4386, 4736, 5106, 5496, 5901, 6330, 6778, 7244, 7737, 8247, 8778, 9336
OFFSET
1,4
COMMENTS
a(n) = A216499(n) - (n choose 3). lim_{n --> infinity} a(n) / n^3 = (2 sqrt(3) - 3) / 6 = 0.077350... a(n) / n^3 < (2 sqrt(3) - 3) / 6 = 0.077350... for all n > 0. [Chao et al. (2012)]. - Jesper Jansson, Sep 10 2012
REFERENCES
K.-M. Chao, A.-C. Chu, J. Jansson, R. S. Lemence, and A. Mancheron. Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. Proceedings of the Ninth Annual Conference on Theory and Applications of Models of Computation (TAMC 2012), Lecture Notes in Computer Science, Vol. 7287, pp. 177-188, Springer-Verlag Berlin Heidelberg, 2012.
W. Stromquist, Packing layered posets into posets, manuscript.
LINKS
Miklos Bona, Bruce E. Sagan and Vincent R. Vatter, Pattern frequency sequences and internal zeros
Alejandro H. Morales, Igor Pak, Greta Panova, Asymptotics of principal evaluations of Schubert polynomials for layered permutations, arXiv:1805.04341 [math.CO], 2018.
FORMULA
a(n) = max(a(k) + k*C(n-k, 2): 1 <= k < n)
a(n+1)/a(n)=1+3/n+O(1/n^2). n^2*(a(n+1)/a(n)-1-3/n) is bounded but there is no limit; limit n-->infinity a(n)/n^3 = C = 0.0773... - Benoit Cloitre, Jan 25 2003
EXAMPLE
a(8) = 31; the permutation of 1..8 containing the maximum number of 132 patterns is 13287654.
CROSSREFS
Sequence in context: A246147 A066140 A200067 * A361272 A001975 A096220
KEYWORD
easy,nonn
AUTHOR
Michael Albert, May 27 2001
EXTENSIONS
More terms from Vladeta Jovovic, Jun 03 2001
STATUS
approved