This module implements Tamari interval-posets: combinatorial objects which represent intervals of the Tamari order. They have been introduced in [PCh2013] and allow for many combinatorial operations on Tamari intervals. In particular, they are linked to DyckWords and BinaryTrees. An introduction into Tamari interval-posets is given in Chapter 7 of [Pons2013].
The Tamari lattice can be defined as a lattice structure on either of several classes of Catalan objects, especially binary trees and Dyck paths [TamBrack1962] [HuangTamari1972] [Sta-EC2]. An interval can be seen as a pair of comparable elements. The number of intervals has been given in [ChapTamari08].
REFERENCES:
[PCh2013] | Gregory Chatel and Viviane Pons. Counting smaller trees in the Tamari order. FPSAC. (2013). Arxiv 1212.0751v1. |
[Pons2013] | Viviane Pons, Combinatoire algebrique liee aux ordres sur les permutations. PhD Thesis. (2013). Arxiv 1310.1805v1. |
[TamBrack1962] | Dov Tamari. The algebra of bracketings and their enumeration. Nieuw Arch. Wisk. (1962). |
[HuangTamari1972] | Samuel Huang and Dov Tamari. Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law. J. Combinatorial Theory Ser. A. (1972). http://www.sciencedirect.com/science/article/pii/0097316572900039 . |
[ChapTamari08] | (1, 2) Frederic Chapoton. Sur le nombre d’intervalles dans les treillis de Tamari. Sem. Lothar. Combin. (2008). Arxiv math/0602368v1. |
AUTHORS:
Bases: sage.structure.element.Element
The class of Tamari interval-posets.
An interval-poset is a labelled poset of size , with labels
, satisfying the following conditions:
We use the word “precedes” here to distinguish the poset order and the natural order on numbers. “Precedes” means “is smaller than with respect to the poset structure”; this does not imply a covering relation.
Interval-posets of size are in bijection with intervals of
the Tamari lattice of binary trees of size
. Specifically, if
is an interval-poset of size
, then the set of linear
extensions of
(as permutations in
) is an interval in the
right weak order (see
permutohedron_lequal()),
and is in fact the preimage of an interval in the Tamari lattice (of
binary trees of size
) under the operation which sends a
permutation to its right-to-left binary search tree
(binary_search_tree()
with the left_to_right variable set to False)
without its labelling.
INPUT:
Warning
The relations input can be a list or tuple, but not an iterator (nor should its entries be iterators).
NOTATION:
Here and in the following, the signs and
always refer to
the natural ordering on integers, whereas the word “precedes” refers
to the order of the interval-poset. “Minimal” and “maximal” refer
to the natural ordering on integers.
The increasing relations of an interval-poset mean the pairs
of elements of
such that
as integers and
precedes
in
. The initial forest of
is the poset
obtained by imposing (only) the increasing relations on the ground
set of
. It is a sub-interval poset of
, and is a forest with
its roots on top. This forest is usually given the structure of a
planar forest by ordering brother nodes by their labels; it then has
the property that if its nodes are traversed in post-order
(see :meth:~sage.combinat.abstract_tree.AbstractTree.post_order_traversal`,
and traverse the trees of the forest from left to right as well),
then the labels encountered are
in this order.
The decreasing relations of an interval-poset mean the pairs
of elements of
such that
as integers and
precedes
in
. The final forest of
is the poset
obtained by imposing (only) the decreasing relations on the ground
set of
. It is a sub-interval poset of
, and is a forest with
its roots on top. This forest is usually given the structure of a
planar forest by ordering brother nodes by their labels; it then has
the property that if its nodes are traversed in pre-order
(see pre_order_traversal(),
and traverse the trees of the forest from left to right as well),
then the labels encountered are
in this order.
EXAMPLES:
sage: TamariIntervalPoset(0,[])
The tamari interval of size 0 induced by relations []
sage: TamariIntervalPoset(3,[])
The tamari interval of size 3 induced by relations []
sage: TamariIntervalPoset(3,[(1,2)])
The tamari interval of size 3 induced by relations [(1, 2)]
sage: TamariIntervalPoset(3,[(1,2),(2,3)])
The tamari interval of size 3 induced by relations [(1, 2), (2, 3)]
sage: TamariIntervalPoset(3,[(1,2),(2,3),(1,3)])
The tamari interval of size 3 induced by relations [(1, 2), (2, 3)]
sage: TamariIntervalPoset(3,[(1,2),(3,2)])
The tamari interval of size 3 induced by relations [(1, 2), (3, 2)]
sage: TamariIntervalPoset(3,[[1,2],[2,3]])
The tamari interval of size 3 induced by relations [(1, 2), (2, 3)]
sage: TamariIntervalPoset(3,[[1,2],[2,3],[1,2],[1,3]])
The tamari interval of size 3 induced by relations [(1, 2), (2, 3)]
sage: TamariIntervalPoset(3,[(3,4)])
Traceback (most recent call last):
...
ValueError: The relations do not correspond to the size of the poset.
sage: TamariIntervalPoset(2,[(2,1),(1,2)])
Traceback (most recent call last):
...
ValueError: Hasse diagram contains cycles
sage: TamariIntervalPoset(3,[(1,3)])
Traceback (most recent call last):
...
ValueError: This does not satisfy the Tamari interval-poset condition.
It is also possible to transform a poset directly into an interval-poset:
sage: TIP = TamariIntervalPosets()
sage: p = Poset( ([1,2,3], [(1,2)]))
sage: TIP(p)
The tamari interval of size 3 induced by relations [(1, 2)]
sage: TIP(Poset({1: []}))
The tamari interval of size 1 induced by relations []
sage: TIP(Poset({}))
The tamari interval of size 0 induced by relations []
Return an iterator on all the binary trees in the interval represented by self.
EXAMPLES:
sage: list(TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]).binary_trees())
[[., [[., [., .]], .]],
[[., [., [., .]]], .],
[., [[[., .], .], .]],
[[., [[., .], .]], .]]
sage: set(TamariIntervalPoset(4,[]).binary_trees()) == set(BinaryTrees(4))
True
Return the complement of the interval-poset self.
If is a Tamari interval-poset of size
, then the
complement of
is defined as the interval-poset
whose
base set is
(just as for
), but
whose order relation has
precede
if and only if
precedes
in
.
In terms of the Tamari lattice, the complement is the symmetric of self. It is formed from the left-right symmeterized of the binary trees of the interval (switching left and right subtrees, see left_right_symmetry()). In particular, initial intervals are sent to final intervals and vice-versa.
EXAMPLES:
sage: TamariIntervalPoset(3, [(2, 1), (3, 1)]).complement()
The tamari interval of size 3 induced by relations [(1, 3), (2, 3)]
sage: TamariIntervalPoset(0, []).complement()
The tamari interval of size 0 induced by relations []
sage: ip = TamariIntervalPoset(4, [(1, 2), (2, 4), (3, 4)])
sage: ip.complement() == TamariIntervalPoset(4, [(2, 1), (3, 1), (4, 3)])
True
sage: ip.lower_binary_tree() == ip.complement().upper_binary_tree().left_right_symmetry()
True
sage: ip.upper_binary_tree() == ip.complement().lower_binary_tree().left_right_symmetry()
True
sage: ip.is_initial_interval()
True
sage: ip.complement().is_final_interval()
True
Return whether the interval represented by self contains the binary tree binary_tree.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.contains_binary_tree(BinaryTree([[None,[None,[]]],None]))
True
sage: ip.contains_binary_tree(BinaryTree([None,[[[],None],None]]))
True
sage: ip.contains_binary_tree(BinaryTree([[],[[],None]]))
False
sage: ip.contains_binary_tree(ip.lower_binary_tree())
True
sage: ip.contains_binary_tree(ip.upper_binary_tree())
True
sage: all([ip.contains_binary_tree(bt) for bt in ip.binary_trees()])
True
Return whether the interval represented by self contains the Dyck word dyck_word.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.contains_dyck_word(DyckWord([1,1,1,0,0,0,1,0]))
True
sage: ip.contains_dyck_word(DyckWord([1,1,0,1,0,1,0,0]))
True
sage: ip.contains_dyck_word(DyckWord([1,0,1,1,0,1,0,0]))
False
sage: ip.contains_dyck_word(ip.lower_dyck_word())
True
sage: ip.contains_dyck_word(ip.upper_dyck_word())
True
sage: all([ip.contains_dyck_word(bt) for bt in ip.dyck_words()])
True
Return whether the interval represented by other is contained in self as an interval of the Tamari lattice.
In terms of interval-posets, it means that all relations of self are relations of other.
INPUT:
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: ip2 = TamariIntervalPoset(4,[(2,3)])
sage: ip2.contains_interval(ip1)
True
sage: ip3 = TamariIntervalPoset(4,[(2,1)])
sage: ip2.contains_interval(ip3)
False
sage: ip4 = TamariIntervalPoset(3,[(2,3)])
sage: ip2.contains_interval(ip4)
False
Return the children of v in the final forest of self.
INPUT:
OUTPUT:
The list of all children of v in the final forest of self, in increasing order.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.decreasing_children(2)
[3, 5]
sage: ip.decreasing_children(3)
[4]
sage: ip.decreasing_children(1)
[]
Return the cover relations of the final forest of self
(the poset formed by keeping only the relations of the form
precedes
with
).
The final forest of self is a forest with its roots being on top. It is also called the decreasing poset of self.
Warning
This method computes the cover relations of the final forest. This is not identical with the cover relations of self which happen to be decreasing!
See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(2,1),(3,2),(3,4),(4,2)]).decreasing_cover_relations()
[(4, 2), (3, 2), (2, 1)]
sage: TamariIntervalPoset(4,[(2,1),(4,3),(2,3)]).decreasing_cover_relations()
[(4, 3), (2, 1)]
sage: TamariIntervalPoset(3,[(2,1),(3,1),(3,2)]).decreasing_cover_relations()
[(3, 2), (2, 1)]
Return the vertex parent of v in the final forest of self.
This is the highest (as integer!) vertex such that v
precedes a. If there is no such vertex (that is,
is a
decreasing root), then None is returned.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.decreasing_parent(4)
3
sage: ip.decreasing_parent(3)
2
sage: ip.decreasing_parent(5)
2
sage: ip.decreasing_parent(2) is None
True
Return the root vertices of the final forest of self,
i.e., the vertices such that there is no
with
preceding
.
OUTPUT:
The list of all roots of the final forest of self, in increasing order.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.decreasing_roots()
[1, 2]
sage: ip.final_forest().decreasing_roots()
[1, 2]
Return an iterator on all the Dyck words in the interval represented by self.
EXAMPLES:
sage: list(TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]).dyck_words())
[[1, 1, 1, 0, 0, 1, 0, 0],
[1, 1, 1, 0, 0, 0, 1, 0],
[1, 1, 0, 1, 0, 1, 0, 0],
[1, 1, 0, 1, 0, 0, 1, 0]]
sage: set(TamariIntervalPoset(4,[]).dyck_words()) == set(DyckWords(4))
True
Return the final forest of self, i.e., the interval-poset formed with only the decreasing relations of self.
EXAMPLES:
sage: TamariIntervalPoset(4,[(2,1),(3,2),(3,4),(4,2)]).final_forest()
The tamari interval of size 4 induced by relations [(4, 2), (3, 2), (2, 1)]
sage: ip = TamariIntervalPoset(3,[(2,1),(3,1)])
sage: ip.final_forest() == ip
True
Return whether e2 precedes or equals e1 in self.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip.ge(2,1)
True
sage: ip.ge(3,1)
True
sage: ip.ge(3,2)
True
sage: ip.ge(4,3)
False
sage: ip.ge(1,1)
True
Return whether e2 strictly precedes e1 in self.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip.gt(2,1)
True
sage: ip.gt(3,1)
True
sage: ip.gt(3,2)
True
sage: ip.gt(4,3)
False
sage: ip.gt(1,1)
False
Return the children of v in the initial forest of self.
INPUT:
OUTPUT:
The list of all children of v in the initial forest of self, in decreasing order.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.increasing_children(2)
[1]
sage: ip.increasing_children(5)
[4, 3]
sage: ip.increasing_children(1)
[]
Return the cover relations of the initial forest of self
(the poset formed by keeping only the relations of the form
precedes
with
).
The initial forest of self is a forest with its roots being on top. It is also called the increasing poset of self.
Warning
This method computes the cover relations of the initial forest. This is not identical with the cover relations of self which happen to be increasing!
See also
EXAMPLES:
sage: TamariIntervalPoset(4,[(1,2),(3,2),(2,4),(3,4)]).increasing_cover_relations()
[(1, 2), (2, 4), (3, 4)]
sage: TamariIntervalPoset(3,[(1,2),(1,3),(2,3)]).increasing_cover_relations()
[(1, 2), (2, 3)]
Return the vertex parent of v in the initial forest of self.
This is the lowest (as integer!) vertex such that
precedes
. If there is no such vertex (that is,
is an
increasing root), then None is returned.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.increasing_parent(1)
2
sage: ip.increasing_parent(3)
5
sage: ip.increasing_parent(4)
5
sage: ip.increasing_parent(5) is None
True
Return the root vertices of the initial forest of self,
i.e., the vertices of self such that there is no
with
precedes
.
OUTPUT:
The list of all roots of the initial forest of self, in decreasing order.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.increasing_roots()
[6, 5, 2]
sage: ip.initial_forest().increasing_roots()
[6, 5, 2]
Return the initial forest of self, i.e., the interval-poset formed from only the increasing relations of self.
EXAMPLES:
sage: TamariIntervalPoset(4,[(1,2),(3,2),(2,4),(3,4)]).initial_forest()
The tamari interval of size 4 induced by relations [(1, 2), (2, 4), (3, 4)]
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip.initial_forest() == ip
True
Return the Tamari insertion of an integer into the
interval-poset self.
If is a Tamari interval-poset of size
and
is an
integer with
, then the Tamari insertion of
into
is defined as the Tamari interval-poset of size
which corresponds to the interval
on the
Tamari lattice, where the binary trees
and
are
defined as follows: We write the interval-poset
as
for two binary trees
and
. We label
the vertices of each of these two trees with the integers
in such a way that
the trees are binary search trees (this labelling is unique).
Then, we insert
into each of these trees (in the way as
explained in
binary_search_insert()).
The shapes of the resulting two trees are denoted
and
.
An alternative way to construct the insertion of into
is by relabeling each vertex
of
satisfying
(as integers) as
, and then adding a vertex
which should precede
and
.
Todo
To study this, it would be more natural to define
interval-posets on arbitrary ordered sets rather than just
on .
EXAMPLES:
sage: ip = TamariIntervalPoset(4, [(2, 3), (4, 3)]); ip
The tamari interval of size 4 induced by relations [(2, 3), (4, 3)]
sage: ip.insertion(1)
The tamari interval of size 5 induced by relations [(1, 2), (3, 4), (5, 4)]
sage: ip.insertion(2)
The tamari interval of size 5 induced by relations [(2, 3), (3, 4), (5, 4), (2, 1)]
sage: ip.insertion(3)
The tamari interval of size 5 induced by relations [(2, 4), (3, 4), (5, 4), (3, 2)]
sage: ip.insertion(4)
The tamari interval of size 5 induced by relations [(2, 3), (4, 5), (5, 3), (4, 3)]
sage: ip.insertion(5)
The tamari interval of size 5 induced by relations [(2, 3), (5, 4), (4, 3)]
sage: ip = TamariIntervalPoset(0, [])
sage: ip.insertion(1)
The tamari interval of size 1 induced by relations []
sage: ip = TamariIntervalPoset(1, [])
sage: ip.insertion(1)
The tamari interval of size 2 induced by relations [(1, 2)]
sage: ip.insertion(2)
The tamari interval of size 2 induced by relations [(2, 1)]
TESTS:
Verifying that the two ways of computing insertion are equivalent:
sage: def insert_alternative(T, i):
....: # Just another way to compute the insertion of i into T.
....: from sage.combinat.binary_tree import LabelledBinaryTree
....: B1 = T.lower_binary_tree().canonical_labelling()
....: B2 = T.upper_binary_tree().canonical_labelling()
....: # We should relabel the trees to "make space" for a label i,
....: # but we don't, because it doesn't make a difference: The
....: # binary search insertion will go precisely the same, because
....: # an integer equal to the label of the root gets sent onto
....: # the left branch.
....: C1 = B1.binary_search_insert(i)
....: C2 = B2.binary_search_insert(i)
....: return TamariIntervalPosets.from_binary_trees(C1, C2)
sage: def test_equivalence(n):
....: for T in TamariIntervalPosets(n):
....: for i in range(1, n + 2):
....: if not (insert_alternative(T, i) == T.insertion(i)):
....: print T, i
....: return False
....: return True
sage: test_equivalence(3)
True
Return the interval-poset formed by combining the relations from both self and other. It corresponds to the intersection of the two corresponding intervals of the Tamari lattice.
INPUT:
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip2 = TamariIntervalPoset(4,[(4,3)])
sage: ip1.intersection(ip2)
The tamari interval of size 4 induced by relations [(1, 2), (2, 3), (4, 3)]
sage: ip3 = TamariIntervalPoset(4,[(2,1)])
sage: ip1.intersection(ip3)
Traceback (most recent call last):
...
ValueError: This intersection is empty, it does not correspond to an interval-poset.
sage: ip4 = TamariIntervalPoset(3,[(2,3)])
sage: ip2.intersection(ip4)
Traceback (most recent call last):
...
ValueError: Intersections are only possible on interval-posets of the same size.
Return the cardinality of the interval, i.e., the number of elements (binary trees or Dyck words) in the interval represented by self.
Not to be confused with size() which is the number of vertices.
EXAMPLES:
sage: TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)]).interval_cardinality()
4
sage: TamariIntervalPoset(4,[]).interval_cardinality()
14
sage: TamariIntervalPoset(4,[(1,2),(2,3),(3,4)]).interval_cardinality()
1
Return if self corresponds to a final interval of the Tamari lattice, i.e. if its upper end is the largest element of the lattice. It consists of checking that self does not contain any increasing relations.
EXAMPLES:
sage: ip = TamariIntervalPoset(4, [(4, 3), (3, 1), (2, 1)])
sage: ip.is_final_interval()
True
sage: ip.upper_dyck_word()
[1, 1, 1, 1, 0, 0, 0, 0]
sage: ip = TamariIntervalPoset(4, [(4, 3), (3, 1), (2, 1), (2, 3)])
sage: ip.is_final_interval()
False
sage: ip.upper_dyck_word()
[1, 1, 0, 1, 1, 0, 0, 0]
sage: all([ dw.tamari_interval(DyckWord([1, 1, 1, 0, 0, 0])).is_final_interval() for dw in DyckWords(3)])
True
Return if self corresponds to an initial interval of the Tamari lattice, i.e. if its lower end is the smallest element of the lattice. It consists of checking that self does not contain any decreasing relations.
EXAMPLES:
sage: ip = TamariIntervalPoset(4, [(1, 2), (2, 4), (3, 4)])
sage: ip.is_initial_interval()
True
sage: ip.lower_dyck_word()
[1, 0, 1, 0, 1, 0, 1, 0]
sage: ip = TamariIntervalPoset(4, [(1, 2), (2, 4), (3, 4), (3, 2)])
sage: ip.is_initial_interval()
False
sage: ip.lower_dyck_word()
[1, 0, 1, 1, 0, 0, 1, 0]
sage: all([ DyckWord([1,0,1,0,1,0]).tamari_interval(dw).is_initial_interval() for dw in DyckWords(3)])
True
Return whether the permutation perm is a linear extension of self.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: ip.is_linear_extension([1,4,2,3])
True
sage: ip.is_linear_extension(Permutation([1,4,2,3]))
True
sage: ip.is_linear_extension(Permutation([1,4,3,2]))
False
Return the latex options for use in the _latex_ function as a dictionary. The default values are set using the global options.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.latex_options()['color_decreasing']
'red'
sage: ip.latex_options()['hspace']
1
Return whether e1 precedes or equals e2 in self.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip.le(1,2)
True
sage: ip.le(1,3)
True
sage: ip.le(2,3)
True
sage: ip.le(3,4)
False
sage: ip.le(1,1)
True
Return an iterator on the permutations which are linear extensions of self.
They form an interval of the right weak order (also called the right permutohedron order – see permutohedron_lequal() for a definition).
EXAMPLES:
sage: ip = TamariIntervalPoset(3,[(1,2),(3,2)])
sage: list(ip.linear_extensions())
[[3, 1, 2], [1, 3, 2]]
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: list(ip.linear_extensions())
[[4, 1, 2, 3], [1, 4, 2, 3], [1, 2, 4, 3]]
Return the lowest binary tree in the interval of the Tamari lattice represented by self.
This is a binary tree. It is the shape of the unique binary search tree whose left-branch ordered forest (i.e., the result of applying to_ordered_tree_left_branch() and cutting off the root) is the final forest of self.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.lower_binary_tree()
[[., .], [[., [., .]], [., .]]]
sage: TamariIntervalPosets.final_forest(ip.lower_binary_tree()) == ip.final_forest()
True
sage: ip == TamariIntervalPosets.from_binary_trees(ip.lower_binary_tree(),ip.upper_binary_tree())
True
If self represents the interval of the Tamari
lattice, return an iterator on all intervals
with
for the Tamari lattice.
In terms of interval-posets, it corresponds to adding all possible
relations of the form precedes
with
.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: list(ip.lower_contained_intervals())
[The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(1, 4), (2, 4), (3, 4), (3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(2, 3), (3, 4), (3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(1, 4), (2, 3), (3, 4), (3, 1), (2, 1)]]
sage: ip = TamariIntervalPoset(4,[])
sage: len(list(ip.lower_contained_intervals()))
14
Return whether the interval represented by other is contained in self as an interval of the Tamari lattice and if they share the same lower bound.
As interval-posets, it means that other contains the relations of self plus some extra increasing relations.
INPUT:
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)]);
sage: ip2 = TamariIntervalPoset(4,[(4,3)])
sage: ip2.lower_contains_interval(ip1)
True
sage: ip2.contains_interval(ip1) and ip2.lower_binary_tree() == ip1.lower_binary_tree()
True
sage: ip3 = TamariIntervalPoset(4,[(4,3),(2,1)])
sage: ip2.contains_interval(ip3)
True
sage: ip2.lower_binary_tree() == ip3.lower_binary_tree()
False
sage: ip2.lower_contains_interval(ip3)
False
Return the lowest Dyck word in the interval of the Tamari lattice represented by self.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.lower_dyck_word()
[1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0]
sage: TamariIntervalPosets.final_forest(ip.lower_dyck_word()) == ip.final_forest()
True
sage: ip == TamariIntervalPosets.from_dyck_words(ip.lower_dyck_word(),ip.upper_dyck_word())
True
Return whether e1 strictly precedes e2 in self.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip.lt(1,2)
True
sage: ip.lt(1,3)
True
sage: ip.lt(2,3)
True
sage: ip.lt(3,4)
False
sage: ip.lt(1,1)
False
Return the maximal permutation for the right weak order which is a linear extension of self.
This is also the maximal permutation in the sylvester class of self.upper_binary_tree() and is a 132-avoiding permutation.
The right weak order is also known as the right permutohedron order. See permutohedron_lequal() for its definition.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: ip.max_linear_extension()
[4, 1, 2, 3]
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.max_linear_extension()
[6, 4, 5, 3, 1, 2]
sage: ip = TamariIntervalPoset(0,[]); ip
The tamari interval of size 0 induced by relations []
sage: ip.max_linear_extension()
[]
sage: ip = TamariIntervalPoset(5, [(1, 4), (2, 4), (3, 4), (5, 4)]); ip
The tamari interval of size 5 induced by relations [(1, 4), (2, 4), (3, 4), (5, 4)]
sage: ip.max_linear_extension()
[5, 3, 2, 1, 4]
Return an iterator on the binary trees forming a longest chain of self (regarding self as an interval of the Tamari lattice).
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: list(ip.maximal_chain_binary_trees())
[[[., [[., .], .]], .], [., [[[., .], .], .]], [., [[., [., .]], .]]]
sage: ip = TamariIntervalPoset(4,[])
sage: list(ip.maximal_chain_binary_trees())
[[[[[., .], .], .], .],
[[[., [., .]], .], .],
[[., [[., .], .]], .],
[., [[[., .], .], .]],
[., [[., [., .]], .]],
[., [., [[., .], .]]],
[., [., [., [., .]]]]]
Return an iterator on the Dyck words forming a longest chain of self (regarding self as an interval of the Tamari lattice).
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: list(ip.maximal_chain_dyck_words())
[[1, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 0, 0], [1, 1, 1, 0, 0, 1, 0, 0]]
sage: ip = TamariIntervalPoset(4,[])
sage: list(ip.maximal_chain_dyck_words())
[[1, 0, 1, 0, 1, 0, 1, 0],
[1, 1, 0, 0, 1, 0, 1, 0],
[1, 1, 0, 1, 0, 0, 1, 0],
[1, 1, 0, 1, 0, 1, 0, 0],
[1, 1, 1, 0, 0, 1, 0, 0],
[1, 1, 1, 0, 1, 0, 0, 0],
[1, 1, 1, 1, 0, 0, 0, 0]]
Return an iterator on the upper contained intervals of one longest chain of the Tamari interval represented by self.
If self represents the interval of the Tamari
lattice, this returns intervals
with
following
one longest chain between
and
.
To obtain a longest chain, we use the Tamari inversions of self.
The elements of the chain are obtained by adding one by one the
relations from each Tamari inversion
to self,
where the Tamari inversions are taken in lexicographic order.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: list(ip.maximal_chain_tamari_intervals())
[The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (4, 1), (3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(2, 4), (3, 4), (4, 1), (3, 2), (2, 1)]]
sage: ip = TamariIntervalPoset(4,[])
sage: list(ip.maximal_chain_tamari_intervals())
[The tamari interval of size 4 induced by relations [],
The tamari interval of size 4 induced by relations [(2, 1)],
The tamari interval of size 4 induced by relations [(3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(4, 1), (3, 1), (2, 1)],
The tamari interval of size 4 induced by relations [(4, 1), (3, 2), (2, 1)],
The tamari interval of size 4 induced by relations [(4, 2), (3, 2), (2, 1)],
The tamari interval of size 4 induced by relations [(4, 3), (3, 2), (2, 1)]]
Return the minimal permutation for the right weak order which is a linear extension of self.
This is also the minimal permutation in the sylvester class of self.lower_binary_tree() and is a 312-avoiding permutation.
The right weak order is also known as the right permutohedron order. See permutohedron_lequal() for its definition.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: ip.min_linear_extension()
[1, 2, 4, 3]
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)])
sage: ip.min_linear_extension()
[1, 4, 3, 6, 5, 2]
sage: ip = TamariIntervalPoset(0,[])
sage: ip.min_linear_extension()
[]
sage: ip = TamariIntervalPoset(5, [(1, 4), (2, 4), (3, 4), (5, 4)]); ip
The tamari interval of size 5 induced by relations [(1, 4), (2, 4), (3, 4), (5, 4)]
sage: ip.min_linear_extension()
[1, 2, 3, 5, 4]
Return the number of Tamari inversions of self. This is also the length the longest chain of the Tamari interval represented by self.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.number_of_tamari_inversions()
2
sage: ip = TamariIntervalPoset(4,[])
sage: ip.number_of_tamari_inversions()
6
sage: ip = TamariIntervalPoset(3,[])
sage: ip.number_of_tamari_inversions()
3
Return self as a labelled poset.
An interval-poset is indeed constructed from a labelled poset which is stored internally. This method allows to access the poset and all the associated methods.
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(3,2),(2,4),(3,4)])
sage: pos = ip.poset(); pos
Finite poset containing 4 elements
sage: pos.maximal_chains()
[[3, 2, 4], [1, 2, 4]]
sage: pos.maximal_elements()
[4]
sage: pos.is_lattice()
False
Set the latex options for use in the _latex_ function. The default values are set in the __init__ function.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.latex_options()["color_decreasing"]
'red'
sage: ip.set_latex_options({"color_decreasing":'green'})
sage: ip.latex_options()["color_decreasing"]
'green'
sage: ip.set_latex_options({"color_increasing":'black'})
sage: ip.latex_options()["color_increasing"]
'black'
To change the default options for all interval-posets, use the parent’s global latex options:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip2 = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip.latex_options()["color_decreasing"]
'red'
sage: ip2.latex_options()["color_decreasing"]
'red'
sage: TamariIntervalPosets.global_options(latex_color_decreasing='green')
sage: ip.latex_options()["color_decreasing"]
'green'
sage: ip2.latex_options()["color_decreasing"]
'green'
Next we set a local latex option and show the global does not override it:
sage: ip.set_latex_options({"color_decreasing": 'black'})
sage: ip.latex_options()["color_decreasing"]
'black'
sage: TamariIntervalPosets.global_options(latex_color_decreasing='blue')
sage: ip.latex_options()["color_decreasing"]
'black'
sage: ip2.latex_options()["color_decreasing"]
'blue'
sage: TamariIntervalPosets.global_options.reset()
Return the size (number of vertices) of the interval-poset.
EXAMPLES:
sage: TamariIntervalPoset(3,[(2,1),(3,1)]).size()
3
Return the renormalized sub-poset of self consisting solely of integers from start (inclusive) to end (not inclusive).
“Renormalized” means that these integers are relabelled
in the obvious way (i.e., by subtracting
start - 1).
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(3,5),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (3, 5), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.sub_poset(1,3)
The tamari interval of size 2 induced by relations [(1, 2)]
sage: ip.sub_poset(1,4)
The tamari interval of size 3 induced by relations [(1, 2), (3, 2)]
sage: ip.sub_poset(1,5)
The tamari interval of size 4 induced by relations [(1, 2), (4, 3), (3, 2)]
sage: ip.sub_poset(1,7) == ip
True
sage: ip.sub_poset(1,1)
The tamari interval of size 0 induced by relations []
Return the Tamari inversions of self. A Tamari inversion is
a pair of vertices such that:
“Smaller” and “bigger” refer to the numerical values of the elements, not to the poset order.
This method returns the list of all Tamari inversions in lexicographic order.
The number of Tamari inversions is the length of the longest chain of the Tamari interval represented by self.
Indeed, when an interval consists of just one binary tree, it has
no inversion. One can also prove that if a Tamari interval
is a proper subset of a Tamari interval
, then the inversion number of
is strictly
lower than the inversion number of
. And finally, by adding
the relation
to the interval-poset where
is the
first inversion of
in lexicographic order, one reduces the
inversion number by exactly
.
See also
EXAMPLES:
sage: ip = TamariIntervalPoset(3,[])
sage: ip.tamari_inversions()
[(1, 2), (1, 3), (2, 3)]
sage: ip = TamariIntervalPoset(3,[(2,1)])
sage: ip.tamari_inversions()
[(1, 3), (2, 3)]
sage: ip = TamariIntervalPoset(3,[(1,2)])
sage: ip.tamari_inversions()
[(2, 3)]
sage: ip = TamariIntervalPoset(3,[(1,2),(3,2)])
sage: ip.tamari_inversions()
[]
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.tamari_inversions()
[(1, 4), (2, 3)]
sage: ip = TamariIntervalPoset(4,[])
sage: ip.tamari_inversions()
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
sage: all([len(TamariIntervalPosets.from_binary_trees(bt,bt).tamari_inversions())==0 for bt in BinaryTrees(3)])
True
sage: all([len(TamariIntervalPosets.from_binary_trees(bt,bt).tamari_inversions())==0 for bt in BinaryTrees(4)])
True
Iterate over the Tamari inversions of self, in lexicographic order.
See tamari_inversions() for the definition of the terms involved.
EXAMPLES:
sage: T = TamariIntervalPoset(5, [[1,2],[3,4],[3,2],[5,2],[4,2]])
sage: list(T.tamari_inversions_iter())
[(4, 5)]
sage: T = TamariIntervalPoset(8, [(2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (8, 7), (6, 4), (5, 4), (4, 3), (3, 2)])
sage: list(T.tamari_inversions_iter())
[(1, 2), (1, 7), (5, 6)]
sage: T = TamariIntervalPoset(1, [])
sage: list(T.tamari_inversions_iter())
[]
sage: T = TamariIntervalPoset(0, [])
sage: list(T.tamari_inversions_iter())
[]
Return the highest binary tree in the interval of the Tamari lattice represented by self.
This is a binary tree. It is the shape of the unique binary search tree whose right-branch ordered forest (i.e., the result of applying to_ordered_tree_right_branch() and cutting off the root) is the initial forest of self.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.upper_binary_tree()
[[., .], [., [[., .], [., .]]]]
sage: TamariIntervalPosets.initial_forest(ip.upper_binary_tree()) == ip.initial_forest()
True
sage: ip == TamariIntervalPosets.from_binary_trees(ip.lower_binary_tree(),ip.upper_binary_tree())
True
Return whether the interval represented by other is contained in self as an interval of the Tamari lattice and if they share the same upper bound.
As interval-posets, it means that other contains the relations of self plus some extra decreasing relations.
INPUT:
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: ip2 = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: ip2.upper_contains_interval(ip1)
True
sage: ip2.contains_interval(ip1) and ip2.upper_binary_tree() == ip1.upper_binary_tree()
True
sage: ip3 = TamariIntervalPoset(4,[(1,2),(2,3),(3,4)])
sage: ip2.upper_contains_interval(ip3)
False
sage: ip2.contains_interval(ip3)
True
sage: ip2.upper_binary_tree() == ip3.upper_binary_tree()
False
Return the highest Dyck word in the interval of the Tamari lattice represented by self.
EXAMPLES:
sage: ip = TamariIntervalPoset(6,[(3,2),(4,3),(5,2),(6,5),(1,2),(4,5)]); ip
The tamari interval of size 6 induced by relations [(1, 2), (4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: ip.upper_dyck_word()
[1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0]
sage: TamariIntervalPosets.initial_forest(ip.upper_dyck_word()) == ip.initial_forest()
True
sage: ip == TamariIntervalPosets.from_dyck_words(ip.lower_dyck_word(),ip.upper_dyck_word())
True
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
Factory for interval-posets.
INPUT:
OUTPUT:
EXAMPLES:
sage: TamariIntervalPosets()
Interval-posets
sage: TamariIntervalPosets(2)
Interval-posets of size 2
Note
This is a factory class whose constructor returns instances of subclasses.
Check if the given poset poset is a interval-poset, that is, if it satisfies the following properties:
INPUT:
EXAMPLES:
sage: p = Poset(([1,2,3],[(1,2),(3,2)]))
sage: TamariIntervalPosets.check_poset(p)
True
sage: p = Poset(([2,3],[(3,2)]))
sage: TamariIntervalPosets.check_poset(p)
False
sage: p = Poset(([1,2,3],[(3,1)]))
sage: TamariIntervalPosets.check_poset(p)
False
sage: p = Poset(([1,2,3],[(1,3)]))
sage: TamariIntervalPosets.check_poset(p)
False
Return the final forest of a binary tree, an interval-poset or a Dyck word.
A final forest is an interval-poset corresponding to a final interval of the Tamari lattice, i.e., containing only decreasing relations.
It can be constructed from a binary tree by its binary
search tree labeling with the rule: precedes
in the final forest iff
is in the right subtree of
in the binary search tree.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: TamariIntervalPosets.final_forest(ip)
The tamari interval of size 4 induced by relations [(1, 2), (2, 3)]
From binary trees:
sage: bt = BinaryTree(); bt
.
sage: TamariIntervalPosets.final_forest(bt)
The tamari interval of size 0 induced by relations []
sage: bt = BinaryTree([]); bt
[., .]
sage: TamariIntervalPosets.final_forest(bt)
The tamari interval of size 1 induced by relations []
sage: bt = BinaryTree([[],None]); bt
[[., .], .]
sage: TamariIntervalPosets.final_forest(bt)
The tamari interval of size 2 induced by relations []
sage: bt = BinaryTree([None,[]]); bt
[., [., .]]
sage: TamariIntervalPosets.final_forest(bt)
The tamari interval of size 2 induced by relations [(2, 1)]
sage: bt = BinaryTree([[],[]]); bt
[[., .], [., .]]
sage: TamariIntervalPosets.final_forest(bt)
The tamari interval of size 3 induced by relations [(3, 2)]
sage: bt = BinaryTree([[None,[[],None]],[]]); bt
[[., [[., .], .]], [., .]]
sage: TamariIntervalPosets.final_forest(bt)
The tamari interval of size 5 induced by relations [(5, 4), (3, 1), (2, 1)]
From Dyck words:
sage: dw = DyckWord([1,0])
sage: TamariIntervalPosets.final_forest(dw)
The tamari interval of size 1 induced by relations []
sage: dw = DyckWord([1,1,0,1,0,0,1,1,0,0])
sage: TamariIntervalPosets.final_forest(dw)
The tamari interval of size 5 induced by relations [(5, 4), (3, 1), (2, 1)]
Return the interval-poset corresponding to the interval
[tree1,``tree2``] of the Tamari lattice. Raise an exception if
tree1 is not tree2 in the Tamari lattice.
INPUT:
EXAMPLES:
sage: tree1 = BinaryTree([[],None])
sage: tree2 = BinaryTree([None,[]])
sage: TamariIntervalPosets.from_binary_trees(tree1,tree2)
The tamari interval of size 2 induced by relations []
sage: TamariIntervalPosets.from_binary_trees(tree1,tree1)
The tamari interval of size 2 induced by relations [(1, 2)]
sage: TamariIntervalPosets.from_binary_trees(tree2,tree2)
The tamari interval of size 2 induced by relations [(2, 1)]
sage: tree1 = BinaryTree([[],[[None,[]],[]]])
sage: tree2 = BinaryTree([None,[None,[None,[[],[]]]]])
sage: TamariIntervalPosets.from_binary_trees(tree1,tree2)
The tamari interval of size 6 induced by relations [(4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: tree3 = BinaryTree([None,[None,[[],[None,[]]]]])
sage: TamariIntervalPosets.from_binary_trees(tree1,tree3)
Traceback (most recent call last):
...
ValueError: The two binary trees are not comparable on the Tamari lattice.
sage: TamariIntervalPosets.from_binary_trees(tree1,BinaryTree())
Traceback (most recent call last):
...
ValueError: The two binary trees are not comparable on the Tamari lattice.
Return the interval-poset corresponding to the interval
[dw1,``dw2``] of the Tamari lattice. Raise an exception if the
two Dyck words dw1 and dw2 do not satisfy
dw1 dw2 in the Tamari lattice.
INPUT:
EXAMPLES:
sage: dw1 = DyckWord([1,0,1,0])
sage: dw2 = DyckWord([1,1,0,0])
sage: TamariIntervalPosets.from_dyck_words(dw1,dw2)
The tamari interval of size 2 induced by relations []
sage: TamariIntervalPosets.from_dyck_words(dw1,dw1)
The tamari interval of size 2 induced by relations [(1, 2)]
sage: TamariIntervalPosets.from_dyck_words(dw2,dw2)
The tamari interval of size 2 induced by relations [(2, 1)]
sage: dw1 = DyckWord([1,0,1,1,1,0,0,1,1,0,0,0])
sage: dw2 = DyckWord([1,1,1,1,0,1,1,0,0,0,0,0])
sage: TamariIntervalPosets.from_dyck_words(dw1,dw2)
The tamari interval of size 6 induced by relations [(4, 5), (6, 5), (5, 2), (4, 3), (3, 2)]
sage: dw3 = DyckWord([1,1,1,0,1,1,1,0,0,0,0,0])
sage: TamariIntervalPosets.from_dyck_words(dw1,dw3)
Traceback (most recent call last):
...
ValueError: The two Dyck words are not comparable on the Tamari lattice.
sage: TamariIntervalPosets.from_dyck_words(dw1,DyckWord([1,0]))
Traceback (most recent call last):
...
ValueError: The two Dyck words are not comparable on the Tamari lattice.
Set and display the global options for Tamari interval-posets. If no parameters are set, then the function returns a copy of the options dictionary.
The options to Tamari interval-posets can be accessed as the method TamariIntervalPosets.global_options of TamariIntervalPosets and related parent classes.
OPTIONS:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(2,4),(3,4),(2,1),(3,1)])
sage: ip.latex_options()["color_decreasing"]
'red'
sage: TamariIntervalPosets.global_options(latex_color_decreasing='green')
sage: ip.latex_options()["color_decreasing"]
'green'
sage: TamariIntervalPosets.global_options.reset()
sage: ip.latex_options()["color_decreasing"]
'red'
See GlobalOptions for more features of these options.
Return the inital forest of a binary tree, an interval-poset or a Dyck word.
An initial forest is an interval-poset corresponding to an initial interval of the Tamari lattice, i.e., containing only increasing relations.
It can be constructed from a binary tree by its binary
search tree labeling with the rule: precedes
in the
initial forest iff
is in the left subtree of
in the
binary search tree.
INPUT:
EXAMPLES:
sage: ip = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: TamariIntervalPosets.initial_forest(ip)
The tamari interval of size 4 induced by relations [(1, 2), (2, 3)]
with binary trees:
sage: bt = BinaryTree(); bt
.
sage: TamariIntervalPosets.initial_forest(bt)
The tamari interval of size 0 induced by relations []
sage: bt = BinaryTree([]); bt
[., .]
sage: TamariIntervalPosets.initial_forest(bt)
The tamari interval of size 1 induced by relations []
sage: bt = BinaryTree([[],None]); bt
[[., .], .]
sage: TamariIntervalPosets.initial_forest(bt)
The tamari interval of size 2 induced by relations [(1, 2)]
sage: bt = BinaryTree([None,[]]); bt
[., [., .]]
sage: TamariIntervalPosets.initial_forest(bt)
The tamari interval of size 2 induced by relations []
sage: bt = BinaryTree([[],[]]); bt
[[., .], [., .]]
sage: TamariIntervalPosets.initial_forest(bt)
The tamari interval of size 3 induced by relations [(1, 2)]
sage: bt = BinaryTree([[None,[[],None]],[]]); bt
[[., [[., .], .]], [., .]]
sage: TamariIntervalPosets.initial_forest(bt)
The tamari interval of size 5 induced by relations [(1, 4), (2, 3), (3, 4)]
from Dyck words:
sage: dw = DyckWord([1,0])
sage: TamariIntervalPosets.initial_forest(dw)
The tamari interval of size 1 induced by relations []
sage: dw = DyckWord([1,1,0,1,0,0,1,1,0,0])
sage: TamariIntervalPosets.initial_forest(dw)
The tamari interval of size 5 induced by relations [(1, 4), (2, 3), (3, 4)]
Poset stucture on the set of interval-posets through interval containment.
Return whether the interval represented by el1 is contained in the interval represented by el2.
INPUT:
EXAMPLES:
sage: ip1 = TamariIntervalPoset(4,[(1,2),(2,3),(4,3)])
sage: ip2 = TamariIntervalPoset(4,[(1,2),(2,3)])
sage: TamariIntervalPosets().le(ip1,ip2)
True
sage: TamariIntervalPosets().le(ip2,ip1)
False
Bases: sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets, sage.combinat.interval_posets.TamariIntervalPosets
The enumerated set of all Tamari interval-posets.
alias of TamariIntervalPoset
Bases: sage.combinat.interval_posets.TamariIntervalPosets
The enumerated set of interval-posets of a given size.
TESTS:
sage: from sage.combinat.interval_posets import TamariIntervalPosets_size
sage: for i in xrange(6): TestSuite(TamariIntervalPosets_size(i)).run()
The cardinality of self. That is, the number of
interval-posets of size .
The formula was given in [ChapTamari08]:
EXAMPLES:
sage: [TamariIntervalPosets(i).cardinality() for i in range(6)]
[1, 1, 3, 13, 68, 399]
TESTS:
sage: S = TamariIntervalPosets(3)
sage: S.element_class
<class 'sage.combinat.interval_posets.TamariIntervalPosets_all_with_category.element_class'>
sage: S.first().__class__ == TamariIntervalPosets().first().__class__
True