Baxter permutation

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

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

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

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

For n = 1 , 2 , 3 , … {\displaystyle n=1,2,3,\ldots } , the number a n {\displaystyle a_{n}} of Baxter permutations of length n {\displaystyle n} is

1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560, 67329992, 414499438, 2593341586, 16458756586,...

This is sequence (sequence A001181 in the OEIS) in the OEIS. In general, a n {\displaystyle a_{n}} has the following formula:

a n = ∑ k = 1 n ( n + 1 k − 1 ) ( n + 1 k ) ( n + 1 k + 1 ) ( n + 1 1 ) ( n + 1 2 ) . {\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 ( n + 1 k − 1 ) ( n + 1 k ) ( n + 1 k + 1 ) ( n + 1 1 ) ( n + 1 2 ) {\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 S n {\displaystyle S_{n}} with k − 1 {\displaystyle k-1} descents. ^[3]

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

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

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

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

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

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

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

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

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

• Enumerations of specific permutation classes

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