# Baxter permutations¶

class sage.combinat.baxter_permutations.BaxterPermutations

The combinatorial class of Baxter permutations.

A Baxter permutation is a permutation avoiding the generalized permutation patterns $$2-41-3$$ and $$3-14-2$$. In other words, a permutation $$\sigma$$ is a Baxter permutation if for any subword $$u := u_1u_2u_3u_4$$ of $$\sigma$$ such that the letters $$u_2$$ and $$u_3$$ are adjacent in $$\sigma$$, the standardized version of $$u$$ is neither $$2413$$ nor $$3142$$.

See [Gir2012] for a study of Baxter permutations.

INPUT:

• n – (default: None) a nonnegative integer, the size of the permutations.

OUTPUT:

Return the combinatorial class of the Baxter permutations of size n if n is not None. Otherwise, return the combinatorial class of all Baxter permutations.

EXAMPLES:

sage: BaxterPermutations(5)
Baxter permutations of size 5
sage: BaxterPermutations()
Baxter permutations

class sage.combinat.baxter_permutations.BaxterPermutations_all(n=None)

The enumerated set of all Baxter permutations.

See BaxterPermutations for the definition of Baxter permutations.

EXAMPLES:

sage: from sage.combinat.baxter_permutations import BaxterPermutations_all
sage: BaxterPermutations_all()
Baxter permutations

to_pair_of_twin_binary_trees(p)

Apply a bijection between Baxter permutations of size self._n and the set of pairs of twin binary trees with self._n nodes.

INPUT:

• p – a Baxter permutation.

OUTPUT:

The pair of twin binary trees $$(T_L, T_R)$$ where $$T_L$$ (resp. $$T_R$$) is obtained by inserting the letters of p from left to right (resp. right to left) following the binary search tree insertion algorithm. This is called the Baxter P-symbol in [Gir2012] Definition 4.1.

Note

This method only works when p is a permutation. For words with repeated letters, it would return two “right binary search trees” (in the terminology of [Gir2012]), which conflicts with the definition in [Gir2012].

EXAMPLES:

sage: BaxterPermutations().to_pair_of_twin_binary_trees(Permutation([]))
(., .)
sage: BaxterPermutations().to_pair_of_twin_binary_trees(Permutation([1, 2, 3]))
(1[., 2[., 3[., .]]], 3[2[1[., .], .], .])
sage: BaxterPermutations().to_pair_of_twin_binary_trees(Permutation([3, 4, 1, 2]))
(3[1[., 2[., .]], 4[., .]], 2[1[., .], 4[3[., .], .]])

class sage.combinat.baxter_permutations.BaxterPermutations_size(n)

The enumerated set of Baxter permutations of a given size.

See BaxterPermutations for the definition of Baxter permutations.

EXAMPLES:

sage: from sage.combinat.baxter_permutations import BaxterPermutations_size
sage: BaxterPermutations_size(5)
Baxter permutations of size 5

cardinality()

Return the number of Baxter permutations of size self._n.

For any positive integer $$n$$, the number of Baxter permutations of size $$n$$ equals

$\sum_{k=1}^n \dfrac {\binom{n+1}{k-1} \binom{n+1}{k} \binom{n+1}{k+1}} {\binom{n+1}{1} \binom{n+1}{2}} .$

This is OEIS sequence A001181.

EXAMPLES:

sage: [BaxterPermutations(n).cardinality() for n in range(13)]
[1, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560]

sage: BaxterPermutations(3r).cardinality()
6
sage: parent(_)
Integer Ring