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.

Enumeration

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

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.

Other properties

  • 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}}.
  • 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 {\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.

See also

External links

  • OEIS