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 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 in the OEIS. In general, $a_n$ has the following formula:

::$a_n \, = \,\sum_^n \frac .$

In fact, this formula is graded by the number of descents in the permutations, i.e., there are
$\frac$ 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_$.
* The number of doubly alternating Baxter permutations of length $2n$ and $2n+1$ (i.e., those for which both $\sigma$ and its inverse $\sigma^$ 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 $$, 1/math> to itself such that $f(g(x)) = g(f(x))$ for all $x$, and $f(g(x)) = x$ for finitely many
$x$ in $$, 1/math>, then:
* the number of these fixed points is odd;
* if the fixed points are $x_1 < x_2< \ldots < x_$ then $f$ and $g$ act as mutually-inverse permutations on
$\$ and $\$;
* the permutation induced by $f$ on $\$ uniquely determines the permutation induced by
$f$ on $\$;
* under the natural relabeling $x_1\to 1$, $x_3\to 2$, etc., the permutation induced on $\$ is a Baxter permutation.

See also

* Enumerations of specific permutation classes

References

External links

* {{OEIS el, 1=A001181, 2=Number of Baxter permutations of length n

Permutation patterns
Fixed points (mathematics)