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 2−41−3 and 3−14−2. In other words, a permutation σ is a Baxter permutation if for any subword u:=u1u2u3u4 of σ such that the letters u2 and u3 are adjacent in σ, 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
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
-
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 (TL,TR) where TL (resp. TR) 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)¶ 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 n, the number of Baxter permutations of size n equals
n∑k=1(n+1k−1)(n+1k)(n+1k+1)(n+11)(n+12).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
-