Alternating permutations containing the pattern 123 or 321 exactly once

2011/11/03 by Joel Brewster Lewis, Lewis, Joel Brewster
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Coding theory and cryptography #math.CO #msc:05A05 #msc:05A15

paper · pdf · doi:10.48550/arxiv.1111.0986

arxiv created 2011/11/03 · arxiv updated 2011/11/07

Abstract

Inspired by a recent note of Zeilberger (arXiv:1110.4379), Alejandro Morales asked whether one can count alternating (i.e., up-down) permutations that contain the pattern 123 or 321 exactly once. In this note we answer the question in the affirmative; in particular, we show that for m > 1, a_(2m)(123) = 10 (2m)!/((m - 2)! (m + 3)!), a_(2m)(321) = 4(m - 2) (2m + 3)!/((m + 1)! (m + 4)!), and a_(2m + 1)(123) = a_(2m + 1)(321) = 3(3m + 4)(m - 1) (2m + 2)!/((m + 1)! (m + 4)!) where a_n(p) is the number of alternating permutations of length n containing the pattern p exactly once.

Citations

• Alexander Burstein's Lovely Combinatorial Proof of John Noonan's Beautiful Formula that the number of n-permutations that contain the Pattern 321 Exactly Once Equals (3/n)(2n)!/((n-3)!(n+3)!)

Related

• Permutations Containing and Avoiding 123 and 132 Patterns
• Restricted 132-alternating permutations and Chebyshev polynomials
• The Number of Permutations With A Prescribed Number of 132 and 123 Patterns
• On Pattern Avoiding Alternating Permutations
• A Combinatorial Proof of the Enumeration of Alternating Permutations with Given Peak Set