|
Search: id:A088532
|
|
|
| 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. |
|
+0
2
|
| |
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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 (joshua.zucker(AT)stanfordalumni.org), Jul 07 2006
|
|
REFERENCES
|
H. S. Wilf, Problem 414, Discrete Math. 272 (2003), 303.
|
|
LINKS
|
Micah Coleman, An (almost) optimal answer to a question by Herb Wilf [math.CO/0404181]
|
|
EXAMPLE
|
n=2: (12) has one pattern of length 1 and one of length 2 and a(2) = 2.
|
|
CROSSREFS
|
A092603[n] is an upper bound.
Sequence in context: A141018 A049864 A118870 this_sequence A036621 A001383 A108564
Adjacent sequences: A088529 A088530 A088531 this_sequence A088533 A088534 A088535
|
|
KEYWORD
|
nonn,easy,nice,more
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), Nov 20 2003
|
|
EXTENSIONS
|
2 more terms from Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Jul 07 2006
|
|
|
Search completed in 0.002 seconds
|
