Baxter permutation

In combinatorial mathematics, a Baxter permutation is a permutation [math]\displaystyle{ \sigma \in S_n }[/math] which satisfies the following generalized pattern avoidance property:

• There are no indices i < j < k such that σ(j + 1) < σ(i) < σ(k) < σ(j) or σ(j) < σ(k) < σ(i) < σ(j + 1).

Equivalently, using the notation for vincular patterns, a Baxter permutation is one that avoids the two dashed patterns 2-41-3 and 3-14-2.

For example, the permutation σ = 2413 in S₄ (written in one-line notation) is not a Baxter permutation because, taking i = 1, j = 2 and k = 4, this permutation violates the first condition.

These permutations were introduced by Glen E. Baxter in the context of mathematical analysis.

Enumeration

For n = 1, 2, 3, ..., the number a_n of Baxter permutations of length n is

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

This is sequence OEIS: A001181 in the OEIS. In general, a_n has the following formula:

[math]\displaystyle{ a_n \, = \,\sum_{k=1}^n \frac{\binom{n+1}{k-1}\binom{n+1}{k}\binom{n+1}{k+1}}{\binom{n+1}{1}\binom{n+1}{2}} . }[/math]

In fact, this formula is graded by the number of descents in the permutations, i.e., there are [math]\displaystyle{ \frac{\binom{n+1}{k-1}\binom{n+1}{k}\binom{n+1}{k+1}}{\binom{n+1}{1}\binom{n+1}{2}} }[/math] Baxter permutations in S_n with k – 1 descents.

Other properties

• The number of alternating Baxter permutations of length 2n is (C_n)², 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 (i.e., those for which both σ and its inverse σ⁻¹ are alternating) is the Catalan number C_n.
• Baxter permutations are related to Hopf algebras, planar graphs, and tilings.

Motivation: commuting functions

Baxter introduced Baxter permutations while studying the fixed points of commuting continuous functions. In particular, if f and g are continuous functions from the interval [0, 1] to itself such that f(g(x)) = g(f(x)) for all x, and f(g(x)) = x for finitely many x in [0, 1], then:

• 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 {x₁, x₃, ..., x_{2k + 1}} and {x₂, x₄, ..., x_2k};
• the permutation induced by f on {x₁, x₃, ..., x_{2k + 1}} uniquely determines the permutation induced by f on {x₂, x₄, ..., x_2k};
• under the natural relabeling x₁ → 1, x₃ → 2, etc., the permutation induced on {1, 2, ..., k + 1} is a Baxter permutation.

See also

• Enumerations of specific permutation classes

External links

• OEIS sequence A001181 (Number of Baxter permutations of length n)