Bijections from Dyck paths to 321-avoiding permutations revisited

2007/11/16 by David Callan, Callan, David · 3 citations
Mathematics · #05A15 #Advanced Algebra and Geometry #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A15

paper · pdf · doi:10.48550/arxiv.0711.2684

15 pages, LaTeX

arxiv created 2007/11/16 · openalex publication_date 2007/11/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

There are (at least) three bijections from Dyck paths to 321-avoiding permutations in the literature, due to Billey-Jockusch-Stanley, Krattenthaler, and Mansour-Deng-Du. How different are they? Denoting them B,K,M respectively, we show that M = B ∘ L = K ∘ L' where L is the classical Kreweras-Lalanne involution on Dyck paths and L', also an involution, is a sort of derivative of L. Thus K^-1 ∘ B, a measure of the difference between B and K, is the product of involutions L' ∘ L and turns out to be a very curious bijection: as a permutation on Dyck n-paths it is an nth root of the "reverse path" involution. The proof of this fact boils down to a geometric argument involving pairs of nonintersecting lattice paths.

Cited by

• Even with AI, Bijection Discovery is Still Hard: The Opportunities and Challenges of OpenEvolve for Novel Bijection Construction
• A basis and Schur-Weyl duality for the loop Hecke algebra
• Patterns in Random Permutations Avoiding the Pattern 132

Related

• On bijections between 231-avoiding permutations and Dyck paths
• A bijection on Dyck paths and its cycle structure
• Bijections for Dyck paths with all peak heights of the same parity
• Permutation-generated maps between Dyck paths
• A simple and unusual bijection for Dyck paths and its consequences