|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|