login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
1, 2, 4, 8, 15, 28, 55, 109, 226, 452, 935 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

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

LINKS

Table of n, a(n) for n=1..11.

Micah Coleman, An (almost) optimal answer to a question by Herbert S. Wilf [math.CO/0404181]

Micah Spencer Coleman, Asymptotic enumeration in pattern avoidance and in the theory of set partitions and asymptotic uniformity [From N. J. A. Sloane, Sep 18 2010]

H. S. Wilf, Problem 414, Discrete Math. 272 (2003), 303.

EXAMPLE

n=2: (12) has one pattern of length 1 and one of length 2 and a(2) = 2.

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.

CROSSREFS

A092603(n) is an upper bound.

Sequence in context: A118870 A171857 A190160 * A271364 A036621 A001383

Adjacent sequences:  A088529 A088530 A088531 * A088533 A088534 A088535

KEYWORD

nonn,nice,more

AUTHOR

N. J. A. Sloane, Nov 20 2003

EXTENSIONS

a(8)-a(9) from Joshua Zucker, Jul 07 2006

a(10)-a(11) from Jon Hart, Aug 08 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 01:12 EST 2018. Contains 317279 sequences. (Running on oeis4.)