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 σ(j + 1) < σ(i) < σ(k) < σ(j) or σ(j) < σ(k) < σ(i) < σ(j + 1).

For example, the permutation σ = 2413 in S₄ (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 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  A001181 in the OEIS. In general, a_n has the following formula:

$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}} .$^[1]

In fact, this formula is graded by the number of descents in the permutations, i.e., there are $\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 with k-1 descents.

Other properties

• The number of alternating Baxter permutations of length 2n is (C_n)², the square of a Catalan number, and of length 2n + 1 is C_nC_n+1.^[2]
• The number of doubly alternating permutations of length 2n and 2n + 1 (i.e., those for which both σ and its inverse σ⁻¹ are alternating) is the Catalan number C_n.^[3]
• Baxter permutations are related to Hopf algebras,^[4] planar graphs,^[5] and tilings.^[6][7]

See also

• Enumerations of specific permutation classes

References

1. Chung, F. R. K.; Graham, R. L.; Hoggatt, V. E., Jr.; Kleiman, M. (1978), "The number of Baxter permutations" (PDF), Journal of Combinatorial Theory, Series A 24 (3): 382–394, doi:10.1016/0097-3165(78)90068-7, MR 491652.
2. Dulucq, S.; Guibert, O. (1998), "Baxter permutations", Discrete Mathematics 180 (1-3): 143–156, doi:10.1016/S0012-365X(97)00112-X, MR 1603713.
3. Guibert, Olivier; Linusson, Svante (2000), "Doubly alternating Baxter permutations are Catalan", Discrete Mathematics 217 (1-3): 157–166, doi:10.1016/S0012-365X(99)00261-7, MR 1766265.
4. Giraudo, Samuele (2011), "Algebraic and combinatorial structures on Baxter permutations", 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Math. Theor. Comput. Sci. Proc. AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 387–398, arXiv:1011.4288, MR 2820726.
5. Bonichon, Nicolas; Bousquet-Mélou, Mireille; Fusy, Éric (October 2009), "Baxter permutations and plane bipolar orientations", Séminaire Lotharingien de Combinatoire 61A, Art. B61Ah, 29pp, arXiv:0805.4180, MR 2734180.
6. Korn, M. (2004), Geometric and algebraic properties of polyomino tilings, Ph.D. thesis, Massachusetts Institute of Technology.
7. Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), "A bijection between permutations and floorplans, and its applications", Discrete Applied Mathematics 154 (12): 1674–1684, doi:10.1016/j.dam.2006.03.018, MR 2233287.

External links

• Sequence A001181 in OEIS.