In combinatorial mathematics, a Baxter permutation is a permutation 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 and .
For example, the permutation in (written in one-line notation) is not a Baxter permutation because, taking , and , this permutation violates the first condition.
These permutations were introduced by Glen E. Baxter in the context of mathematical analysis.
For , the number of Baxter permutations of length is
1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586, ... (sequence A001181 in the OEIS)
In general, has the following formula: In fact, this formula is graded by the number of descents in the permutations, i.e., there are Baxter permutations in with descents.
.
Baxter introduced Baxter permutations while studying the fixed points of commuting continuous functions. In particular, if and are continuous functions from the interval to itself such that for all , and for finitely many in , then:
and ;
on ;