Baxter permutation

In combinatorial mathematics, a Baxter permutation is a permutation σ∈Sn which satisfies the following generalized pattern avoidance property:

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 S4 (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 an of Baxter permutations of length n is

1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586, ... (sequence A001181 in the OEIS)

In general, an has the following formula: an=∑k=1n(n+1k−1)(n+1k)(n+1k+1)(n+11)(n+12). In fact, this formula is graded by the number of descents in the permutations, i.e., there are (n+1k−1)(n+1k)(n+1k+1)(n+11)(n+12) Baxter permutations in Sn with k−1 descents.

Other properties

CnCn+1.

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:

{x1,x3,…,x2k+1} and {x2,x4,…,x2k};

f on {x2,x4,…,x2k};

See also