Baxter permutation

In combinatorial mathematics, a Baxter permutation is a permutation $σ \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)$ .

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

Enumeration

For $n = 1, 2, 3, \dots$ , 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 OEIS: 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})} .

^[2]

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. ^[3]

Other properties

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

$C_{n} C_{n + 1}$ .

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

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 $[0, 1]$ to itself such that $f (g (x)) = g (f (x))$ for all $x$ , and $f (g (x)) = x$ for finitely many $x$ in $[0, 1]$ , then:

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

${x_{1}, x_{3}, \dots, x_{2 k + 1}}$ and ${x_{2}, x_{4}, \dots, x_{2 k}}$ ;

the permutation induced by $f$ on ${x_{1}, x_{3}, \dots, x_{2 k + 1}}$ uniquely determines the permutation induced by

$f$ on ${x_{2} <, x_{4}, \dots, x_{2 k}}$ ;

under the natural relabeling $x_{1} \to 1$ , $x_{3} \to 2$ , etc., the permutation induced on ${1, 2, \dots, k + 1}$ is a Baxter permutation.

References

↑ Baxter, Glen (1964), "On fixed points of the composite of commuting functions", Proceedings of the American Mathematical Society, 15 (6): 851–855, doi:10.2307/2034894, JSTOR 2034894.
↑ 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 0491652.
↑ Dulucq, S.; Guibert, O. (1998), "Baxter permutations", Discrete Mathematics, 180 (1–3): 143–156, doi:10.1016/S0012-365X(97)00112-X, MR 1603713.
↑ 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.
↑ 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., vol. AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 387–398, arXiv:1011.4288, Bibcode:2010arXiv1011.4288G, MR 2820726.
↑ 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, Bibcode:2008arXiv0805.4180B, MR 2734180.
↑ Korn, M. (2004), Geometric and algebraic properties of polyomino tilings, Ph.D. thesis, Massachusetts Institute of Technology.
↑ 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

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

[1] Baxter, Glen (1964), "On fixed points of the composite of commuting functions", Proceedings of the American Mathematical Society, 15 (6): 851–855, doi:10.2307/2034894, JSTOR 2034894.

[2] 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 0491652.

[3] Dulucq, S.; Guibert, O. (1998), "Baxter permutations", Discrete Mathematics, 180 (1–3): 143–156, doi:10.1016/S0012-365X(97)00112-X, MR 1603713.

[4] 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.

[5] 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., vol. AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 387–398, arXiv:1011.4288, Bibcode:2010arXiv1011.4288G, MR 2820726.

[6] 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, Bibcode:2008arXiv0805.4180B, MR 2734180.

[7] Korn, M. (2004), Geometric and algebraic properties of polyomino tilings, Ph.D. thesis, Massachusetts Institute of Technology.

[8] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Baxter permutation

Contents

Enumeration

Other properties

Motivation: commuting functions

See also

References

External links

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools

In other projects

In other languages