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,\dots$, 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, ... Template:Oeis

In general, $a_n$ has the following formula: $$a_n=\sum _{k=1}^n\frac{(\genfrac{}{}{0ex}{}{n+1}{k-1})(\genfrac{}{}{0ex}{}{n+1}{k})(\genfrac{}{}{0ex}{}{n+1}{k+1})}{(\genfrac{}{}{0ex}{}{n+1}{1})(\genfrac{}{}{0ex}{}{n+1}{2})}.$$ In fact, this formula is graded by the number of descents in the permutations, i.e., there are $\frac{(\genfrac{}{}{0ex}{}{n+1}{k-1})(\genfrac{}{}{0ex}{}{n+1}{k})(\genfrac{}{}{0ex}{}{n+1}{k+1})}{(\genfrac{}{}{0ex}{}{n+1}{1})(\genfrac{}{}{0ex}{}{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, tilings, and rectangulations.

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

$\{x_1,x_3,\dots ,x_{2k+1}\}$ and $\{x_2,x_4,\dots ,x_{2k}\}$;

• the permutation induced by $f$ on $\{x_1,x_3,\dots ,x_{2k+1}\}$ uniquely determines the permutation induced by

$f$ on $\{x_2,x_4,\dots ,x_{2k}\}$;

• under the natural relabeling $x_1\to 1$, $x_3\to 2$, etc., the permutation induced on $\{1,2,\dots ,k+1\}$ is a Baxter permutation.

See also

• Enumerations of specific permutation classes

External links

• Template:OEIS el