cp's OEIS Frontend

A088532 "Patterns of permutations": Define the "pattern" formed by k positions in a permutation to be the permutation of {1..k} specifying the relative order of the elements in those positions; a(n) = largest number of different patterns that can occur in a permutation of n letters.

%I A088532 #39 Aug 25 2024 09:57:28
%S A088532 1,2,4,8,15,28,55,109,226,452,935
%N A088532 "Patterns of permutations": Define the "pattern" formed by k positions in a permutation to be the permutation of {1..k} specifying the relative order of the elements in those positions; a(n) = largest number of different patterns that can occur in a permutation of n letters.
%C A088532 Apparently Micah Coleman (U. Florida, Gainesville) may have solved part of Wilf's problem. He showed that limit of f(n)^(1/n)=2, by a construction.
%C A088532 Full list of permutations that attain the maximum number of patterns, up to reversal: 1: (1) 2: (12) 3: (132) (213) 4: (2413) 5: (25314) 6: (253614) (264153) (361425) (426315) 7: (2574163) (3614725) (3624715) (3714625) (5274136) 8: (25836147) (36185274) (38527416) (52741836) 9: (385174926) (481639527). - _Joshua Zucker_, Jul 07 2006
%H A088532 Micah Coleman, <a href="https://arxiv.org/abs/math/0404181">An (almost) optimal answer to a question by Herbert S. Wilf</a>, arXiv:math/0404181 [math.CO], 2004.
%H A088532 Micah Spencer Coleman, <a href="https://ufdc.ufl.edu/UFE0022066/00001">Asymptotic enumeration in pattern avoidance and in the theory of set partitions and asymptotic uniformity</a> [From _N. J. A. Sloane_, Sep 18 2010]
%H A088532 H. S. Wilf, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00207-3">Problem 414</a>, Discrete Math. 272 (2003), 303.
%e A088532 n=2: (12) has one pattern of length 1 and one of length 2 and a(2) = 2.
%e A088532 n=4: (2413) has one pattern of length 1, 2 of length 2 (namely 24 and 21), 4 of length 3 (namely 243, 241, 213, 413) and one of length 4 (namely 2413), and this is maximal, and a(4)=8.
%Y A088532 A092603(n) is an upper bound.
%K A088532 nonn,nice,more
%O A088532 1,2
%A A088532 _N. J. A. Sloane_, Nov 20 2003
%E A088532 a(8)-a(9) from _Joshua Zucker_, Jul 07 2006
%E A088532 a(10)-a(11) from _Jon Hart_, Aug 08 2015