pith. sign in

arxiv: math/9911243 · v2 · submitted 1999-11-30 · 🧮 math.CO

Permutations containing and avoiding certain patterns

classification 🧮 math.CO
keywords permutationsequalsnumberpatternsavoidavoidingcontainingexactly
0
0 comments X
read the original abstract

Let T_k^m={\sigma \in S_k | \sigma_1=m}. We prove that the number of permutations which avoid all patterns in T_k^m equals (k-2)!(k-1)^{n+1-k} for k <= n. We then prove that for any \tau in T_k^1 (or any \tau in T_k^k), the number of permutations which avoid all patterns in T_k^1 (or in T_k^k) except for \tau and contain \tau exactly once equals (n+1-k)(k-1)^{n-k} for k <= n. Finally, for any \tau in T_k^m, 2 <= m <= k-1, this number equals (k-1)^{n-k} for k <= n. These results generalize recent results due to Robertson concerning permutations avoiding 123-pattern and containing 132-pattern exactly once.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.