Bijective counting of involutive Baxter permutations

2010/10/19 by Éric Fusy, Eric Fusy, Fusy, Eric
Computer Science · Mathematics · #05A15 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A15

paper · pdf · doi:10.48550/arxiv.1010.3850

8 pages

openalex publication_date 2010/10/19 · arxiv created 2011/10/28 · arxiv updated 2011/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We enumerate bijectively the family of involutive Baxter permutations according to various parameters; in particular we obtain an elementary proof that the number of involutive Baxter permutations of size 2n with no fixed points is \frac3⋅ 2^n-1(n+1)(n+2)\binom2nn, a formula originally discovered by M. Bousquet-Mélou using generating functions. The same coefficient also enumerates planar maps with n edges, endowed with an acyclic orientation having a unique source, and such that the source and sinks are all incident to the outer face.

Related

• Involutions on Baxter Objects
• Proof of Dilks' bijectivity conjecture on Baxter permutations
• Quarter-Turn Baxter Permutations
• Exact enumeration of 1342-avoiding permutations: A close link with\n labeled trees and planar maps
• Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence