Baxter permutations¶
-
class
sage.combinat.baxter_permutations.
BaxterPermutations
¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
The combinatorial class of Baxter permutations.
A Baxter permutation is a permutation avoiding the generalized permutation patterns
and
. In other words, a permutation
is a Baxter permutation if for any subword
of
such that the letters
and
are adjacent in
, the standardized version of
is neither
nor
.
See [Gir12] 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
ifn
is notNone
. Otherwise, return the combinatorial class of all Baxter permutations.EXAMPLES:
sage: BaxterPermutations(5) Baxter permutations of size 5 sage: BaxterPermutations() Baxter permutations
REFERENCES:
[Gir12] (1, 2, 3, 4) Samuele Giraudo, Algebraic and combinatorial structures on pairs of twin binary trees, Arxiv 1204.4776v1.
-
class
sage.combinat.baxter_permutations.
BaxterPermutations_all
(n=None)¶ Bases:
sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets
,sage.combinat.baxter_permutations.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 withself._n
nodes.INPUT:
p
– a Baxter permutation.
OUTPUT:
The pair of twin binary trees
where
(resp.
) is obtained by inserting the letters of
p
from left to right (resp. right to left) following the the binary search tree insertion algorithm. This is called the Baxter P-symbol in [Gir12] 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 [Gir12]), which conflicts with the definition in [Gir12].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)¶ Bases:
sage.combinat.baxter_permutations.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
, the number of Baxter permutations of size
equals
This is OEIS sequence A001181.
EXAMPLES:
sage: [BaxterPermutations(n).cardinality() for n in xrange(13)] [1, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560] sage: BaxterPermutations(3r).cardinality() 6 sage: parent(_) Integer Ring
-