Encyclopedia

Baxter permutation

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated August 28, 2026

In combinatorial mathematics, a Baxter permutation is a permutation $\sigma \in S_{n}$ which satisfies the following generalized pattern avoidance property:

There are no indices $i<j<k$ such that $\sigma (j+1)<\sigma (i)<\sigma (k)<\sigma (j)$ or $\sigma (j)<\sigma (k)<\sigma (i)<\sigma (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 $\sigma =2413$ in $S_{4}$ (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.

01Enumeration

For $n=1,2,3,\ldots$ , 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, ... (sequence A001181 in the OEIS)

In general, $a_{n}$ has the following formula: $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}}}}.$ In fact, this formula is graded by the number of descents in the permutations, i.e., there are ${\frac {{\binom {n+1}{k-1}}{\binom {n+1}{k}}{\binom {n+1}{k+1}}}{{\binom {n+1}{1}}{\binom {n+1}{2}}}}$ Baxter permutations in $S_{n}$ with $k-1$ descents.

02Other properties

The number of alternating Baxter permutations of length $2n$ is $(C_{n})^{2}$ , the square of a Catalan number, and of length $2n+1$ is

$C_{n}C_{n+1}$ .

The number of doubly alternating Baxter permutations of length $2n$ and $2n+1$ (i.e., those for which both $\sigma$ and its inverse $\sigma ^{-1}$ are alternating) is the Catalan number $C_{n}$ .
Baxter permutations are related to Hopf algebras, planar graphs, tilings, and rectangulations.

03Motivation: 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_{1}<x_{2}<\ldots <x_{2k+1}$ then $f$ and $g$ act as mutually-inverse permutations on

$\{x_{1},x_{3},\ldots ,x_{2k+1}\}$ and $\{x_{2},x_{4},\ldots ,x_{2k}\}$ ;

the permutation induced by $f$ on $\{x_{1},x_{3},\ldots ,x_{2k+1}\}$ uniquely determines the permutation induced by

$f$ on $\{x_{2},x_{4},\ldots ,x_{2k}\}$ ;

under the natural relabeling $x_{1}\to 1$ , $x_{3}\to 2$ , etc., the permutation induced on $\{1,2,\ldots ,k+1\}$ is a Baxter permutation.

Watch videos about Baxter permutationExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Baxter permutation”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Baxter permutation

01Enumeration

02Other properties

03Motivation: commuting functions

Sources and credits

Related topics

Enumerations of specific permutation classes