Ordered Rooted Trees

AUTHORS:

  • Florent Hivert (2010-2011): initial revision

  • Frédéric Chapoton (2010): contributed some methods

class sage.combinat.ordered_tree.LabelledOrderedTree(parent, children, label=None, check=True)[source]

Bases: AbstractLabelledClonableTree, OrderedTree

Labelled ordered trees.

A labelled ordered tree is an ordered tree with a label attached at each node.

INPUT:

  • children – list or tuple or more generally any iterable of trees or object convertible to trees

  • label – any Sage object (default: None)

EXAMPLES:

sage: x = LabelledOrderedTree([], label = 3); x
3[]
sage: LabelledOrderedTree([x, x, x], label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree((x, x, x), label = 2)
2[3[], 3[], 3[]]
sage: LabelledOrderedTree([[],[[], []]], label = 3)
3[None[], None[None[], None[]]]

>>> from sage.all import *
>>> x = LabelledOrderedTree([], label = Integer(3)); x
3[]
>>> LabelledOrderedTree([x, x, x], label = Integer(2))
2[3[], 3[], 3[]]
>>> LabelledOrderedTree((x, x, x), label = Integer(2))
2[3[], 3[], 3[]]
>>> LabelledOrderedTree([[],[[], []]], label = Integer(3))
3[None[], None[None[], None[]]]
left_right_symmetry()[source]

Return the symmetric tree of self.

The symmetric tree \(s(T)\) of a labelled ordered tree \(T\) is defined as follows: If \(T\) is a labelled ordered tree with children \(C_1, C_2, \ldots, C_k\) (listed from left to right), then the symmetric tree \(s(T)\) of \(T\) is a labelled ordered tree with children \(s(C_k), s(C_{k-1}), \ldots, s(C_1)\) (from left to right), and with the same root label as \(T\).

Note

If you have a subclass of LabelledOrderedTree() which also inherits from another subclass of OrderedTree() which does not come with a labelling, then (depending on the method resolution order) it might happen that this method gets overridden by an implementation from that other subclass, and thus forgets about the labels. In this case you need to manually override this method on your subclass.

EXAMPLES:

sage: L2 = LabelledOrderedTree([], label=2)
sage: L3 = LabelledOrderedTree([], label=3)
sage: T23 = LabelledOrderedTree([L2, L3], label=4)
sage: T23.left_right_symmetry()
4[3[], 2[]]
sage: T223 = LabelledOrderedTree([L2, T23], label=17)
sage: T223.left_right_symmetry()
17[4[3[], 2[]], 2[]]
sage: T223.left_right_symmetry().left_right_symmetry() == T223
True

>>> from sage.all import *
>>> L2 = LabelledOrderedTree([], label=Integer(2))
>>> L3 = LabelledOrderedTree([], label=Integer(3))
>>> T23 = LabelledOrderedTree([L2, L3], label=Integer(4))
>>> T23.left_right_symmetry()
4[3[], 2[]]
>>> T223 = LabelledOrderedTree([L2, T23], label=Integer(17))
>>> T223.left_right_symmetry()
17[4[3[], 2[]], 2[]]
>>> T223.left_right_symmetry().left_right_symmetry() == T223
True
sort_key()[source]

Return a tuple of nonnegative integers encoding the labelled tree self.

The first entry of the tuple is a pair consisting of the number of children of the root and the label of the root. Then the rest of the tuple is the concatenation of the tuples associated to these children (we view the children of a tree as trees themselves) from left to right.

This tuple characterizes the labelled tree uniquely, and can be used to sort the labelled ordered trees provided that the labels belong to a type which is totally ordered.

Warning

This method overrides OrderedTree.sort_key() and returns a result different from what the latter would return, as it wants to encode the whole labelled tree including its labelling rather than just the unlabelled tree. Therefore, be careful with using this method on subclasses of LabelledOrderedTree; under some circumstances they could inherit it from another superclass instead of from OrderedTree, which would cause the method to forget the labelling. See the docstring of OrderedTree.sort_key().

EXAMPLES:

sage: L2 = LabelledOrderedTree([], label=2)
sage: L3 = LabelledOrderedTree([], label=3)
sage: T23 = LabelledOrderedTree([L2, L3], label=4)
sage: T23.sort_key()
((2, 4), (0, 2), (0, 3))
sage: T32 = LabelledOrderedTree([L3, L2], label=5)
sage: T32.sort_key()
((2, 5), (0, 3), (0, 2))
sage: T23322 = LabelledOrderedTree([T23, T32, L2], label=14)
sage: T23322.sort_key()
((3, 14), (2, 4), (0, 2), (0, 3), (2, 5), (0, 3), (0, 2), (0, 2))

>>> from sage.all import *
>>> L2 = LabelledOrderedTree([], label=Integer(2))
>>> L3 = LabelledOrderedTree([], label=Integer(3))
>>> T23 = LabelledOrderedTree([L2, L3], label=Integer(4))
>>> T23.sort_key()
((2, 4), (0, 2), (0, 3))
>>> T32 = LabelledOrderedTree([L3, L2], label=Integer(5))
>>> T32.sort_key()
((2, 5), (0, 3), (0, 2))
>>> T23322 = LabelledOrderedTree([T23, T32, L2], label=Integer(14))
>>> T23322.sort_key()
((3, 14), (2, 4), (0, 2), (0, 3), (2, 5), (0, 3), (0, 2), (0, 2))
class sage.combinat.ordered_tree.LabelledOrderedTrees(category=None)[source]

Bases: UniqueRepresentation, Parent

This is a parent stub to serve as a factory class for trees with various label constraints.

EXAMPLES:

sage: LOT = LabelledOrderedTrees(); LOT
Labelled ordered trees
sage: x = LOT([], label = 3); x
3[]
sage: x.parent() is LOT
True
sage: y = LOT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.parent() is LOT
True

>>> from sage.all import *
>>> LOT = LabelledOrderedTrees(); LOT
Labelled ordered trees
>>> x = LOT([], label = Integer(3)); x
3[]
>>> x.parent() is LOT
True
>>> y = LOT([x, x, x], label = Integer(2)); y
2[3[], 3[], 3[]]
>>> y.parent() is LOT
True
Element[source]

alias of LabelledOrderedTree

cardinality()[source]

Return the cardinality of self.

EXAMPLES:

sage: LabelledOrderedTrees().cardinality()
+Infinity

>>> from sage.all import *
>>> LabelledOrderedTrees().cardinality()
+Infinity
labelled_trees()[source]

Return the set of labelled trees associated to self.

This is precisely self, because self already is the set of labelled ordered trees.

EXAMPLES:

sage: LabelledOrderedTrees().labelled_trees()
Labelled ordered trees
sage: LOT = LabelledOrderedTrees()
sage: x = LOT([], label = 3)
sage: y = LOT([x, x, x], label = 2)
sage: y.canonical_labelling()
1[2[], 3[], 4[]]

>>> from sage.all import *
>>> LabelledOrderedTrees().labelled_trees()
Labelled ordered trees
>>> LOT = LabelledOrderedTrees()
>>> x = LOT([], label = Integer(3))
>>> y = LOT([x, x, x], label = Integer(2))
>>> y.canonical_labelling()
1[2[], 3[], 4[]]
unlabelled_trees()[source]

Return the set of unlabelled trees associated to self.

This is the set of ordered trees, since self is the set of labelled ordered trees.

EXAMPLES:

sage: LabelledOrderedTrees().unlabelled_trees()
Ordered trees

>>> from sage.all import *
>>> LabelledOrderedTrees().unlabelled_trees()
Ordered trees
class sage.combinat.ordered_tree.OrderedTree(parent=None, children=None, check=True)[source]

Bases: AbstractClonableTree, ClonableList

The class of (ordered rooted) trees.

An ordered tree is constructed from a node, called the root, on which one has grafted a possibly empty list of trees. There is a total order on the children of a node which is given by the order of the elements in the list. Note that there is no empty ordered tree (so the smallest ordered tree consists of just one node).

INPUT:

One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree. Alternatively a string is also accepted. The syntax is the same as for printing: children are grouped by square brackets.

EXAMPLES:

sage: x = OrderedTree([])
sage: x1 = OrderedTree([x,x])
sage: x2 = OrderedTree([[],[]])
sage: x1 == x2
True
sage: tt1 = OrderedTree([x,x1,x2])
sage: tt2 = OrderedTree([[], [[], []], x2])
sage: tt1 == tt2
True

sage: OrderedTree([]) == OrderedTree()
True

>>> from sage.all import *
>>> x = OrderedTree([])
>>> x1 = OrderedTree([x,x])
>>> x2 = OrderedTree([[],[]])
>>> x1 == x2
True
>>> tt1 = OrderedTree([x,x1,x2])
>>> tt2 = OrderedTree([[], [[], []], x2])
>>> tt1 == tt2
True

>>> OrderedTree([]) == OrderedTree()
True
is_empty()[source]

Return if self is the empty tree.

For ordered trees, this always returns False.

Note

this is different from bool(t) which returns whether t has some child or not.

EXAMPLES:

sage: t = OrderedTrees(4)([[],[[]]])
sage: t.is_empty()
False
sage: bool(t)
True

>>> from sage.all import *
>>> t = OrderedTrees(Integer(4))([[],[[]]])
>>> t.is_empty()
False
>>> bool(t)
True
left_right_symmetry()[source]

Return the symmetric tree of self.

The symmetric tree \(s(T)\) of an ordered tree \(T\) is defined as follows: If \(T\) is an ordered tree with children \(C_1, C_2, \ldots, C_k\) (listed from left to right), then the symmetric tree \(s(T)\) of \(T\) is the ordered tree with children \(s(C_k), s(C_{k-1}), \ldots, s(C_1)\) (from left to right).

EXAMPLES:

sage: T = OrderedTree([[],[[]]])
sage: T.left_right_symmetry()
[[[]], []]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.left_right_symmetry()
[[[[]], []], [[], []], []]

>>> from sage.all import *
>>> T = OrderedTree([[],[[]]])
>>> T.left_right_symmetry()
[[[]], []]
>>> T = OrderedTree([[], [[], []], [[], [[]]]])
>>> T.left_right_symmetry()
[[[[]], []], [[], []], []]
normalize(inplace=False)[source]

Return the normalized tree of self.

INPUT:

  • inplace – boolean (default: False); if True, then self is modified and nothing returned. Otherwise the normalized tree is returned.

The normalization of an ordered tree \(t\) is an ordered tree \(s\) which has the property that \(t\) and \(s\) are isomorphic as unordered rooted trees, and that if two ordered trees \(t\) and \(t'\) are isomorphic as unordered rooted trees, then the normalizations of \(t\) and \(t'\) are identical. In other words, normalization is a map from the set of ordered trees to itself which picks a representative from every equivalence class with respect to the relation of “being isomorphic as unordered trees”, and maps every ordered tree to the representative chosen from its class.

This map proceeds recursively by first normalizing every subtree, and then sorting the subtrees according to the value of the sort_key() method.

Consider the quotient map \(\pi\) that sends a planar rooted tree to the associated unordered rooted tree. Normalization is the composite \(s \circ \pi\), where \(s\) is a section of \(\pi\).

EXAMPLES:

sage: OT = OrderedTree
sage: ta = OT([[],[[]]])
sage: tb = OT([[[]],[]])
sage: ta.normalize() == tb.normalize()
True
sage: ta == tb
False

>>> from sage.all import *
>>> OT = OrderedTree
>>> ta = OT([[],[[]]])
>>> tb = OT([[[]],[]])
>>> ta.normalize() == tb.normalize()
True
>>> ta == tb
False

An example with inplace normalization:

sage: OT = OrderedTree
sage: ta = OT([[],[[]]])
sage: tb = OT([[[]],[]])
sage: ta.normalize(inplace=True); ta
[[], [[]]]
sage: tb.normalize(inplace=True); tb
[[], [[]]]

>>> from sage.all import *
>>> OT = OrderedTree
>>> ta = OT([[],[[]]])
>>> tb = OT([[[]],[]])
>>> ta.normalize(inplace=True); ta
[[], [[]]]
>>> tb.normalize(inplace=True); tb
[[], [[]]]
plot()[source]

Plot the tree self.

Warning

For a labelled tree, this will fail unless all labels are distinct. For unlabelled trees, some arbitrary labels are chosen. Use _latex_(), view, _ascii_art_() or pretty_print for more faithful representations of the data of the tree.

EXAMPLES:

sage: p = OrderedTree([[[]],[],[]])
sage: ascii_art(p)
  _o__
 / / /
o o o
|
o
sage: p.plot()                                                              # needs sage.plot
Graphics object consisting of 10 graphics primitives

>>> from sage.all import *
>>> p = OrderedTree([[[]],[],[]])
>>> ascii_art(p)
  _o__
 / / /
o o o
|
o
>>> p.plot()                                                              # needs sage.plot
Graphics object consisting of 10 graphics primitives
../../_images/ordered_tree-1.svg

Now a labelled example:

sage: g = OrderedTree([[],[[]],[]]).canonical_labelling()
sage: ascii_art(g)
  _1__
 / / /
2 3 5
  |
  4
sage: g.plot()                                                              # needs sage.plot
Graphics object consisting of 10 graphics primitives

>>> from sage.all import *
>>> g = OrderedTree([[],[[]],[]]).canonical_labelling()
>>> ascii_art(g)
  _1__
 / / /
2 3 5
  |
  4
>>> g.plot()                                                              # needs sage.plot
Graphics object consisting of 10 graphics primitives
../../_images/ordered_tree-2.svg
sort_key()[source]

Return a tuple of nonnegative integers encoding the ordered tree self.

The first entry of the tuple is the number of children of the root. Then the rest of the tuple is the concatenation of the tuples associated to these children (we view the children of a tree as trees themselves) from left to right.

This tuple characterizes the tree uniquely, and can be used to sort the ordered trees.

Note

By default, this method does not encode any extra structure that self might have – e.g., if you were to define a class EdgeColoredOrderedTree which implements edge-colored trees and which inherits from OrderedTree, then the sort_key() method it would inherit would forget about the colors of the edges (and thus would not characterize edge-colored trees uniquely). If you want to preserve extra data, you need to override this method or use a new method. For instance, on the LabelledOrderedTree subclass, this method is overridden by a slightly different method, which encodes not only the numbers of children of the nodes of self, but also their labels. Be careful with using overridden methods, however: If you have (say) a class BalancedTree which inherits from OrderedTree and which encodes balanced trees, and if you have another class BalancedLabelledOrderedTree which inherits both from BalancedOrderedTree and from LabelledOrderedTree, then (depending on the MRO) the default sort_key() method on BalancedLabelledOrderedTree (unless manually overridden) will be taken either from BalancedTree or from LabelledOrderedTree, and in the former case will ignore the labelling!

EXAMPLES:

sage: RT = OrderedTree
sage: RT([[],[[]]]).sort_key()
(2, 0, 1, 0)
sage: RT([[[]],[]]).sort_key()
(2, 1, 0, 0)

>>> from sage.all import *
>>> RT = OrderedTree
>>> RT([[],[[]]]).sort_key()
(2, 0, 1, 0)
>>> RT([[[]],[]]).sort_key()
(2, 1, 0, 0)
to_binary_tree_left_branch()[source]

Return a binary tree of size \(n-1\) (where \(n\) is the size of \(t\), and where \(t\) is self) obtained from \(t\) by the following recursive rule:

  • if \(x\) is the left brother of \(y\) in \(t\), then \(x\) becomes the left child of \(y\);

  • if \(x\) is the last child of \(y\) in \(t\), then \(x\) becomes the right child of \(y\),

and removing the root of \(t\).

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_left_branch()
[[., .], .]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_left_branch()
[[[., .], [[., .], .]], [[., .], [., .]]]

>>> from sage.all import *
>>> T = OrderedTree([[],[]])
>>> T.to_binary_tree_left_branch()
[[., .], .]
>>> T = OrderedTree([[], [[], []], [[], [[]]]])
>>> T.to_binary_tree_left_branch()
[[[., .], [[., .], .]], [[., .], [., .]]]
to_binary_tree_right_branch()[source]

Return a binary tree of size \(n-1\) (where \(n\) is the size of \(t\), and where \(t\) is self) obtained from \(t\) by the following recursive rule:

  • if \(x\) is the right brother of \(y\) in \(t\), then`x` becomes the right child of \(y\);

  • if \(x\) is the first child of \(y\) in \(t\), then \(x\) becomes the left child of \(y\),

and removing the root of \(t\).

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_binary_tree_right_branch()
[., [., .]]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_binary_tree_right_branch()
[., [[., [., .]], [[., [[., .], .]], .]]]

>>> from sage.all import *
>>> T = OrderedTree([[],[]])
>>> T.to_binary_tree_right_branch()
[., [., .]]
>>> T = OrderedTree([[], [[], []], [[], [[]]]])
>>> T.to_binary_tree_right_branch()
[., [[., [., .]], [[., [[., .], .]], .]]]
to_dyck_word()[source]

Return the Dyck path corresponding to self where the maximal height of the Dyck path is the depth of self .

EXAMPLES:

sage: T = OrderedTree([[],[]])
sage: T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 0]
sage: T = OrderedTree([[],[[]]])
sage: T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 1, 0, 0]
sage: T = OrderedTree([[], [[], []], [[], [[]]]])
sage: T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]

>>> from sage.all import *
>>> T = OrderedTree([[],[]])
>>> T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 0]
>>> T = OrderedTree([[],[[]]])
>>> T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 1, 0, 0]
>>> T = OrderedTree([[], [[], []], [[], [[]]]])
>>> T.to_dyck_word()                                                      # needs sage.combinat
[1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0]
to_parallelogram_polyomino(bijection=None)[source]

Return a polyomino parallelogram.

INPUT:

  • bijection – (default: 'Boussicault-Socci') is the name of the bijection to use. Possible values are 'Boussicault-Socci', 'via dyck and Delest-Viennot'.

EXAMPLES:

sage: # needs sage.combinat sage.modules
sage: T = OrderedTree([[[], [[], [[]]]], [], [[[],[]]], [], []])
sage: T.to_parallelogram_polyomino(bijection='Boussicault-Socci')
[[0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
 [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]]
sage: T = OrderedTree( [] )
sage: T.to_parallelogram_polyomino()
[[1], [1]]
sage: T = OrderedTree( [[]] )
sage: T.to_parallelogram_polyomino()
[[0, 1], [1, 0]]
sage: T = OrderedTree( [[],[]] )
sage: T.to_parallelogram_polyomino()
[[0, 1, 1], [1, 1, 0]]
sage: T = OrderedTree( [[[]]] )
sage: T.to_parallelogram_polyomino()
[[0, 0, 1], [1, 0, 0]]

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> T = OrderedTree([[[], [[], [[]]]], [], [[[],[]]], [], []])
>>> T.to_parallelogram_polyomino(bijection='Boussicault-Socci')
[[0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
 [1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0]]
>>> T = OrderedTree( [] )
>>> T.to_parallelogram_polyomino()
[[1], [1]]
>>> T = OrderedTree( [[]] )
>>> T.to_parallelogram_polyomino()
[[0, 1], [1, 0]]
>>> T = OrderedTree( [[],[]] )
>>> T.to_parallelogram_polyomino()
[[0, 1, 1], [1, 1, 0]]
>>> T = OrderedTree( [[[]]] )
>>> T.to_parallelogram_polyomino()
[[0, 0, 1], [1, 0, 0]]
to_poset(root_to_leaf=False)[source]

Return the poset obtained by interpreting the tree as a Hasse diagram. The default orientation is from leaves to root but you can pass root_to_leaf=True to obtain the inverse orientation.

INPUT:

  • root_to_leaf – boolean (default: False); True if the poset orientation should be from root to leaves

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_poset()
Finite poset containing 1 elements
sage: p = OrderedTree([[[]],[],[]]).to_poset()
sage: p.height(), p.width()                                                 # needs networkx
(3, 3)

>>> from sage.all import *
>>> t = OrderedTree([])
>>> t.to_poset()
Finite poset containing 1 elements
>>> p = OrderedTree([[[]],[],[]]).to_poset()
>>> p.height(), p.width()                                                 # needs networkx
(3, 3)

If the tree is labelled, we use its labelling to label the poset. Otherwise, we use the poset canonical labelling:

sage: t = OrderedTree([[[]],[],[]]).canonical_labelling().to_poset()
sage: t.height(), t.width()                                                 # needs networkx
(3, 3)

>>> from sage.all import *
>>> t = OrderedTree([[[]],[],[]]).canonical_labelling().to_poset()
>>> t.height(), t.width()                                                 # needs networkx
(3, 3)
to_undirected_graph()[source]

Return the undirected graph obtained from the tree nodes and edges.

The graph is endowed with an embedding, so that it will be displayed correctly.

EXAMPLES:

sage: t = OrderedTree([])
sage: t.to_undirected_graph()
Graph on 1 vertex
sage: t = OrderedTree([[[]],[],[]])
sage: t.to_undirected_graph()
Graph on 5 vertices

>>> from sage.all import *
>>> t = OrderedTree([])
>>> t.to_undirected_graph()
Graph on 1 vertex
>>> t = OrderedTree([[[]],[],[]])
>>> t.to_undirected_graph()
Graph on 5 vertices

If the tree is labelled, we use its labelling to label the graph. This will fail if the labels are not all distinct. Otherwise, we use the graph canonical labelling which means that two different trees can have the same graph.

EXAMPLES:

sage: t = OrderedTree([[[]],[],[]])
sage: t.canonical_labelling().to_undirected_graph()
Graph on 5 vertices

>>> from sage.all import *
>>> t = OrderedTree([[[]],[],[]])
>>> t.canonical_labelling().to_undirected_graph()
Graph on 5 vertices
class sage.combinat.ordered_tree.OrderedTrees[source]

Bases: UniqueRepresentation, Parent

Factory for ordered trees.

INPUT:

  • size – integer (optional)

OUTPUT:

  • the set of all ordered trees (of the given size if specified)

EXAMPLES:

sage: OrderedTrees()
Ordered trees

sage: OrderedTrees(2)
Ordered trees of size 2

>>> from sage.all import *
>>> OrderedTrees()
Ordered trees

>>> OrderedTrees(Integer(2))
Ordered trees of size 2

Note

this is a factory class whose constructor returns instances of subclasses.

Note

the fact that OrderedTrees is a class instead of a simple callable is an implementation detail. It could be changed in the future and one should not rely on it.

leaf()[source]

Return a leaf tree with self as parent.

EXAMPLES:

sage: OrderedTrees().leaf()
[]

>>> from sage.all import *
>>> OrderedTrees().leaf()
[]
class sage.combinat.ordered_tree.OrderedTrees_all[source]

Bases: DisjointUnionEnumeratedSets, OrderedTrees

The set of all ordered trees.

EXAMPLES:

sage: OT = OrderedTrees(); OT
Ordered trees
sage: OT.cardinality()
+Infinity

>>> from sage.all import *
>>> OT = OrderedTrees(); OT
Ordered trees
>>> OT.cardinality()
+Infinity
Element[source]

alias of OrderedTree

labelled_trees()[source]

Return the set of labelled trees associated to self.

EXAMPLES:

sage: OrderedTrees().labelled_trees()
Labelled ordered trees

>>> from sage.all import *
>>> OrderedTrees().labelled_trees()
Labelled ordered trees
unlabelled_trees()[source]

Return the set of unlabelled trees associated to self.

EXAMPLES:

sage: OrderedTrees().unlabelled_trees()
Ordered trees

>>> from sage.all import *
>>> OrderedTrees().unlabelled_trees()
Ordered trees
class sage.combinat.ordered_tree.OrderedTrees_size(size)[source]

Bases: OrderedTrees

The enumerated sets of binary trees of a given size.

EXAMPLES:

sage: S = OrderedTrees(3); S
Ordered trees of size 3
sage: S.cardinality()
2
sage: S.list()
[[[], []], [[[]]]]

>>> from sage.all import *
>>> S = OrderedTrees(Integer(3)); S
Ordered trees of size 3
>>> S.cardinality()
2
>>> S.list()
[[[], []], [[[]]]]
cardinality()[source]

The cardinality of self.

This is a Catalan number.

element_class()[source]

The class of the element of self.

EXAMPLES:

sage: from sage.combinat.ordered_tree import OrderedTrees_size, OrderedTrees_all
sage: S = OrderedTrees_size(3)
sage: S.element_class is OrderedTrees().element_class
True
sage: S.first().__class__ == OrderedTrees_all().first().__class__
True

>>> from sage.all import *
>>> from sage.combinat.ordered_tree import OrderedTrees_size, OrderedTrees_all
>>> S = OrderedTrees_size(Integer(3))
>>> S.element_class is OrderedTrees().element_class
True
>>> S.first().__class__ == OrderedTrees_all().first().__class__
True
random_element()[source]

Return a random OrderedTree with uniform probability.

This method generates a random DyckWord and then uses a bijection between Dyck words and ordered trees.

EXAMPLES:

sage: OrderedTrees(5).random_element()  # random                            # needs sage.combinat
[[[], []], []]
sage: OrderedTrees(0).random_element()
Traceback (most recent call last):
...
EmptySetError: there are no ordered trees of size 0
sage: OrderedTrees(1).random_element()                                      # needs sage.combinat
[]

>>> from sage.all import *
>>> OrderedTrees(Integer(5)).random_element()  # random                            # needs sage.combinat
[[[], []], []]
>>> OrderedTrees(Integer(0)).random_element()
Traceback (most recent call last):
...
EmptySetError: there are no ordered trees of size 0
>>> OrderedTrees(Integer(1)).random_element()                                      # needs sage.combinat
[]