Aaron Robertson - Permutations Containing and Avoiding $\textit{123}$ and $\textit{132}$ Patterns

dmtcs:261 - Discrete Mathematics & Theoretical Computer Science, January 1, 1999, Vol. 3 no. 4 - https://doi.org/10.46298/dmtcs.261
Permutations Containing and Avoiding $\textit{123}$ and $\textit{132}$ PatternsArticle

Authors: Aaron Robertson 1

  • 1 Department of Mathematics [Hamilton NY]

We prove that the number of permutations which avoid 132-patterns and have exactly one 123-pattern, equals $(n-2)2^{n-3}$, for $n \ge 3$. We then give a bijection onto the set of permutations which avoid 123-patterns and have exactly one 132-pattern. Finally, we show that the number of permutations which contain exactly one 123-pattern and exactly one 132-pattern is $(n-3)(n-4)2^{n-5}$, for $n \ge 5$.


Volume: Vol. 3 no. 4
Published on: January 1, 1999
Imported on: March 26, 2015
Keywords: Patterns,Words,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 402 times.
This article's PDF has been downloaded 333 times.