
arXiv: 0704.1489
We consider pattern containment and avoidance with a very tight definition that was used first by Riordan more than 60 years ago. Using this definition, we prove the monotone pattern is easier to avoid than almost any other pattern of the same length. We also show that with this definition, almost all patterns of length $k$ are avoided by the same number of permutations of length $n$. The corresponding statements are not known to be true for more relaxed definitions of pattern containment. This is the first time we know of that expectations are used to compare numbers of permutations avoiding certain patterns.
1 file 10 pages
Permutations, words, matrices, probability, Probability (math.PR), Exact enumeration problems, generating functions, pattern avoiding permutations, Theoretical Computer Science, patterns in permutations, pattern avoidance, 05A05, 60C05, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), expectation, Mathematics - Probability
Permutations, words, matrices, probability, Probability (math.PR), Exact enumeration problems, generating functions, pattern avoiding permutations, Theoretical Computer Science, patterns in permutations, pattern avoidance, 05A05, 60C05, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Combinatorics (math.CO), expectation, Mathematics - Probability
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
