Suvarna Garge (Editor)

Baxter permutation

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In combinatorial mathematics, a Baxter permutation is a permutation σ ∈ S n which satisfies the following generalized pattern avoidance property:

Contents

  • There are no indices i < j < k such that σ(j + 1) < σ(i) < σ(k) < σ(j) or σ(j) < σ(k) < σ(i) < σ(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 σ = 2413 in S4 (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, ..., the number an 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  A001181 in the OEIS. In general, an has the following formula:

    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 ) Baxter permutations in Sn with k-1 descents.

    Other properties

  • The number of alternating Baxter permutations of length 2n is (Cn)2, the square of a Catalan number, and of length 2n + 1 is CnCn+1.
  • The number of doubly alternating Baxter permutations of length 2n and 2n + 1 (i.e., those for which both σ and its inverse σ−1 are alternating) is the Catalan number Cn.
  • Baxter permutations are related to Hopf algebras, planar graphs, and tilings.

    • References

    Baxter permutation Wikipedia
    (Text) CC BY-SA