Baxter permutation

• There are no indices i < j < k such that σ < σ < σ < σ or σ < σ < σ < σ.

Enumeration

1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586,...

Other properties

• The number of alternating Baxter permutations of length 2n is ², the square of a Catalan number, and of length 2n + 1 is C_nC_n+1.
• The number of doubly alternating Baxter permutations of length 2n and 2n + 1 is the Catalan number C_n.
• Baxter permutations are related to Hopf algebras, planar graphs, and tilings.

  Motivation: commuting functions

• the number of these fixed points is odd;
• if the fixed points are x₁ < x₂ <... < x_{2k + 1} then f and g act as mutually-inverse permutations on and ;
• the permutation induced by f on uniquely determines the permutation induced by f on ;
• under the natural relabeling x₁ → 1, x₃ → 2, etc., the permutation induced on is a Baxter permutation.