Baxter permutation

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.

Enumeration

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,...

This is sequence OEIS: 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.

Other 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, 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_{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.

See also

• Enumerations of specific permutation classes

External links

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