Baxter permutation

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

• There are no indices ${\displaystyle i<j<k}$ such that ${\displaystyle \sigma (j+1)<\sigma (i)<\sigma (k)<\sigma (j)}$ or ${\displaystyle \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 ${\displaystyle 2-41-3}$ and ${\displaystyle 3-14-2}$.

For example, the permutation ${\displaystyle \sigma =2413}$ in ${\displaystyle S_{4}}$ (written in one-line notation) is not a Baxter permutation because, taking ${\displaystyle i=1}$, ${\displaystyle j=2}$ and ${\displaystyle k=4}$, this permutation violates the first condition.

These permutations were introduced by Glen E. Baxter in the context of mathematical analysis.^[1]

Enumeration

For ${\displaystyle n=1,2,3,\ldots }$, the number ${\displaystyle a_{n}}$ of Baxter permutations of length ${\displaystyle 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, ${\displaystyle a_{n}}$ has the following formula:

${\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}}}}.}$^[2]

In fact, this formula is graded by the number of descents in the permutations, i.e., there are ${\displaystyle {\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 ${\displaystyle S_{n}}$ with ${\displaystyle k-1}$ descents. ^[3]

Other properties

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

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

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

Motivation: commuting functions

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

• the number of these fixed points is odd;
• if the fixed points are ${\displaystyle x_{1}<x_{2}<\ldots <x_{2k+1}}$ then ${\displaystyle f}$ and ${\displaystyle g}$ act as mutually-inverse permutations on

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

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

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

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

See also

• Enumerations of specific permutation classes