Baxter permutations

class sage.combinat.baxter_permutations.BaxterPermutations

Bases: UniqueRepresentation, Parent

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)

Bases: DisjointUnionEnumeratedSets, BaxterPermutations

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: BP = BaxterPermutations()
sage: BP.to_pair_of_twin_binary_trees(Permutation([]))                      # needs sage.graphs
(., .)
sage: BP.to_pair_of_twin_binary_trees(Permutation([1, 2, 3]))               # needs sage.graphs
(1[., 2[., 3[., .]]], 3[2[1[., .], .], .])
sage: BP.to_pair_of_twin_binary_trees(Permutation([3, 4, 1, 2]))            # needs sage.graphs
(3[1[., 2[., .]], 4[., .]], 2[1[., .], 4[3[., .], .]])

class sage.combinat.baxter_permutations.BaxterPermutations_size(n)

Bases: BaxterPermutations

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