Baxter permutation

For $n\; =\; 1,\; 2,\; 3,\; \backslash ldots$, 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}}

.{{citation

| last1 = Chung | first1 = F. R. K. | author1-link = Fan Chung

| last2 = Graham | first2 = R. L. | author2-link = Ronald Graham

| last3 = Hoggatt | first3 = V. E. Jr.| author3-link = Verner Emil Hoggatt, Jr.

| last4 = Kleiman | first4 = M.

| doi = 10.1016/0097-3165(78)90068-7

| issue = 3

| journal = Journal of Combinatorial Theory

| mr = 491652

| pages = 382–394

| series = Series A

| title = The number of Baxter permutations

| url = http://www.math.ucsd.edu/~ronspubs/78_08_baxter.pdf

| volume = 24

| year = 1978| doi-access = free

}}.

In fact, this formula is graded by the number of descents in the permutations, i.e., there are

$\backslash frac\{\backslash binom\{n+1\}\{k-1\}\backslash binom\{n+1\}\{k\}\backslash binom\{n+1\}\{k+1\}\}\{\backslash binom\{n+1\}\{1\}\backslash binom\{n+1\}\{2\}\}$ Baxter permutations in $S\_n$ with $k-1$ descents.

{{citation

| last1 = Dulucq | first1 = S.

| last2 = Guibert | first2 = O.

| doi = 10.1016/S0012-365X(97)00112-X

| issue = 1–3

| journal = Discrete Mathematics

| mr = 1603713

| pages = 143–156

| title = Baxter permutations

| volume = 180

| year = 1998| doi-access = free

}}.

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

$C\_n\; C\_\{n+1\}$.

• The number of doubly alternating Baxter permutations of length $2n$ and $2n+1$ (i.e., those for which both $\backslash sigma$ and its inverse $\backslash sigma^\{-1\}$ are alternating) is the Catalan number $C\_n$.{{citation

| last1 = Guibert | first1 = Olivier

| last2 = Linusson | first2 = Svante

| doi = 10.1016/S0012-365X(99)00261-7

| issue = 1–3

| journal = Discrete Mathematics

| mr = 1766265

| pages = 157–166

| title = Doubly alternating Baxter permutations are Catalan

| volume = 217

| year = 2000| doi-access = free

}}.

• Baxter permutations are related to Hopf algebras,{{citation

| last = Giraudo | first = Samuele

| arxiv = 1011.4288

| contribution = Algebraic and combinatorial structures on Baxter permutations

| mr = 2820726

| pages = 387–398

| publisher = Assoc. Discrete Math. Theor. Comput. Sci., Nancy

| series = Discrete Math. Theor. Comput. Sci. Proc.

| title = 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)

| volume = AO

| year = 2011| bibcode = 2010arXiv1011.4288G

}}. planar graphs,{{citation

| last1 = Bonichon | first1 = Nicolas

| last2 = Bousquet-Mélou | first2 = Mireille | author2-link = Mireille Bousquet-Mélou

| last3 = Fusy | first3 = Éric

| arxiv = 0805.4180

| date = October 2009

| journal = Séminaire Lotharingien de Combinatoire

| mr = 2734180

| at = Art. B61Ah, 29pp

| title = Baxter permutations and plane bipolar orientations

| volume = 61A| bibcode = 2008arXiv0805.4180B}}. and tilings.{{citation

| last = Korn | first = M.

| publisher = Massachusetts Institute of Technology

| series = Ph.D. thesis

| title = Geometric and algebraic properties of polyomino tilings

| url = http://dspace.mit.edu/handle/1721.1/16628

| year = 2004}}.{{citation

| last1 = Ackerman | first1 = Eyal

| last2 = Barequet | first2 = Gill

| last3 = Pinter | first3 = Ron Y.

| doi = 10.1016/j.dam.2006.03.018

| issue = 12

| journal = Discrete Applied Mathematics

| mr = 2233287

| pages = 1674–1684

| title = A bijection between permutations and floorplans, and its applications

| volume = 154

| year = 2006| doi-access = free

}}.

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 then $f$ and $g$ act as mutually-inverse permutations on

$\backslash \{x\_1,x\_3,\; \backslash ldots,\; x\_\{2k\; +\; 1\}\; \backslash \}$ and $\backslash \{x\_2,\; x\_4,\backslash ldots,\; x\_\{2k\}\; \backslash \}$;

• the permutation induced by $f$ on $\backslash \{x\_1,\; x\_3,\; \backslash ldots,\; x\_\{2k+1\}\backslash \}$ uniquely determines the permutation induced by

$f$ on $\backslash \{\; x\_2,\; x\_4,\; \backslash ldots,\; x\_\{2k\}\backslash \}$;

• under the natural relabeling $x\_1\backslash to\; 1$, $x\_3\backslash to\; 2$, etc., the permutation induced on $\backslash \{1,\; 2,\; \backslash ldots,\; k\; +\; 1\backslash \}$ is a Baxter permutation.

• Enumerations of specific permutation classes

{{reflist}}

• {{OEIS el|1=A001181|2=Number of Baxter permutations of length n}}

Category:Permutation patterns

Category:Fixed points (mathematics)