Permutations containing and avoiding certain patterns

Details Permutations containing and avoiding certain patterns Permutations containing and avoiding certain patterns

1999-11-30

arxiv.org/abs/math/9911243v2

Proc. 12th Conference on Formal Power Series and Algebraic combinatorics, 2000, 706-708

Mathematics

Combinatorics

7 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Permutations containing and avoiding certain patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Permutations containing and avoiding certain patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Permutations containing and avoiding certain patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453812