Rooted (Unordered) Trees#

AUTHORS:

  • Florent Hivert (2011): initial version

class sage.combinat.rooted_tree.LabelledRootedTree(parent, children, label=None, check=True)[source]#

Bases: AbstractLabelledClonableTree, RootedTree

Labelled rooted trees.

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

More formally: The labelled rooted trees are an inductive datatype defined as follows: A labelled rooted tree is a multiset of labelled rooted trees, endowed with a label (which can be any object, including None). The trees that belong to this multiset are said to be the children of the tree. (Notice that the labels of these children may and may not be of the same type as the label of the tree). A labelled rooted tree which has no children (so the only information it carries is its label) is said to be a leaf.

Every labelled rooted tree gives rise to an unlabelled rooted tree (RootedTree) by forgetting the labels. (This is implemented as a conversion.)

INPUT:

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

  • label – any hashable Sage object (default is None)

Note

It is required that all labels are comparable.

EXAMPLES:

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

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

Children are reordered using the value of the sort_key() method:

sage: y = LabelledRootedTree([], label = 5); y
5[]
sage: xyy2 = LabelledRootedTree((x, y, y), label = 2); xyy2
2[3[], 5[], 5[]]
sage: yxy2 = LabelledRootedTree((y, x, y), label = 2); yxy2
2[3[], 5[], 5[]]
sage: xyy2 == yxy2
True

>>> from sage.all import *
>>> y = LabelledRootedTree([], label = Integer(5)); y
5[]
>>> xyy2 = LabelledRootedTree((x, y, y), label = Integer(2)); xyy2
2[3[], 5[], 5[]]
>>> yxy2 = LabelledRootedTree((y, x, y), label = Integer(2)); yxy2
2[3[], 5[], 5[]]
>>> xyy2 == yxy2
True

Converting labelled into unlabelled rooted trees by forgetting the labels, and back (the labels are initialized as None):

sage: yxy2crude = RootedTree(yxy2); yxy2crude
[[], [], []]
sage: LabelledRootedTree(yxy2crude)
None[None[], None[], None[]]

>>> from sage.all import *
>>> yxy2crude = RootedTree(yxy2); yxy2crude
[[], [], []]
>>> LabelledRootedTree(yxy2crude)
None[None[], None[], None[]]
sort_key()[source]#

Return a tuple of nonnegative integers encoding the labelled rooted 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 obtained as follows: List the tuples corresponding to all children (we are regarding the children themselves as trees). Order this list (not the tuples!) in lexicographically increasing order, and flatten it into a single tuple.

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

Note

The tree self must be normalized before calling this method (see normalize()). This does not matter unless you are inside the clone() context manager, because outside of it every rooted tree is already normalized.

Note

This method overrides RootedTree.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 RootedOrderedTree; under some circumstances they could inherit it from another superclass instead of from RootedTree, which would cause the method to forget the labelling. See the docstrings of RootedTree.sort_key() and sage.combinat.ordered_tree.OrderedTree.sort_key().

EXAMPLES:

sage: LRT = LabelledRootedTrees(); LRT
Labelled rooted trees
sage: x = LRT([], label = 3); x
3[]
sage: x.sort_key()
((0, 3),)
sage: y = LRT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.sort_key()
((3, 2), (0, 3), (0, 3), (0, 3))
sage: LRT.an_element().sort_key()
((3, 'alpha'), (0, 3), (1, 5), (0, None), (2, 42), (0, 3), (0, 3))
sage: lb = RootedTrees()([[],[[], []]]).canonical_labelling()
sage: lb.sort_key()
((2, 1), (0, 2), (2, 3), (0, 4), (0, 5))

>>> from sage.all import *
>>> LRT = LabelledRootedTrees(); LRT
Labelled rooted trees
>>> x = LRT([], label = Integer(3)); x
3[]
>>> x.sort_key()
((0, 3),)
>>> y = LRT([x, x, x], label = Integer(2)); y
2[3[], 3[], 3[]]
>>> y.sort_key()
((3, 2), (0, 3), (0, 3), (0, 3))
>>> LRT.an_element().sort_key()
((3, 'alpha'), (0, 3), (1, 5), (0, None), (2, 42), (0, 3), (0, 3))
>>> lb = RootedTrees()([[],[[], []]]).canonical_labelling()
>>> lb.sort_key()
((2, 1), (0, 2), (2, 3), (0, 4), (0, 5))
class sage.combinat.rooted_tree.LabelledRootedTrees[source]#

Bases: UniqueRepresentation, Parent

This is a parent stub to serve as a factory class for labelled rooted trees.

EXAMPLES:

sage: LRT = LabelledRootedTrees(); LRT
Labelled rooted trees
sage: x = LRT([], label = 3); x
3[]
sage: x.parent() is LRT
True
sage: y = LRT([x, x, x], label = 2); y
2[3[], 3[], 3[]]
sage: y.parent() is LRT
True

>>> from sage.all import *
>>> LRT = LabelledRootedTrees(); LRT
Labelled rooted trees
>>> x = LRT([], label = Integer(3)); x
3[]
>>> x.parent() is LRT
True
>>> y = LRT([x, x, x], label = Integer(2)); y
2[3[], 3[], 3[]]
>>> y.parent() is LRT
True

Todo

Add the possibility to restrict the labels to a fixed set.

class sage.combinat.rooted_tree.LabelledRootedTrees_all(category=None)[source]#

Bases: LabelledRootedTrees

Class of all (unordered) labelled rooted trees.

See LabelledRootedTree for a definition.

Element[source]#

alias of LabelledRootedTree

labelled_trees()[source]#

Return the set of labelled trees associated to self.

EXAMPLES:

sage: LabelledRootedTrees().labelled_trees()
Labelled rooted trees

>>> from sage.all import *
>>> LabelledRootedTrees().labelled_trees()
Labelled rooted trees
unlabelled_trees()[source]#

Return the set of unlabelled trees associated to self.

EXAMPLES:

sage: LabelledRootedTrees().unlabelled_trees()
Rooted trees

>>> from sage.all import *
>>> LabelledRootedTrees().unlabelled_trees()
Rooted trees
class sage.combinat.rooted_tree.RootedTree(parent=None, children=[], check=True)[source]#

Bases: AbstractClonableTree, NormalizedClonableList

The class for unordered rooted trees.

The unordered rooted trees are an inductive datatype defined as follows: An unordered rooted tree is a multiset of unordered rooted trees. The trees that belong to this multiset are said to be the children of the tree. The tree that has no children is called a leaf.

The labelled rooted trees (LabelledRootedTree) form a subclass of this class; they carry additional data.

One can create a tree from any list (or more generally iterable) of trees or objects convertible to a tree.

EXAMPLES:

sage: RootedTree([])
[]
sage: RootedTree([[], [[]]])
[[], [[]]]
sage: RootedTree([[[]], []])
[[], [[]]]
sage: O = OrderedTree([[[]], []]); O
[[[]], []]
sage: RootedTree(O)  # this is O with the ordering forgotten
[[], [[]]]

>>> from sage.all import *
>>> RootedTree([])
[]
>>> RootedTree([[], [[]]])
[[], [[]]]
>>> RootedTree([[[]], []])
[[], [[]]]
>>> O = OrderedTree([[[]], []]); O
[[[]], []]
>>> RootedTree(O)  # this is O with the ordering forgotten
[[], [[]]]

One can also enter any small rooted tree (“small” meaning that no vertex has more than \(15\) children) by using a simple numerical encoding of rooted trees, namely, the from_hexacode() function. (This function actually parametrizes ordered trees, and here we make it parametrize unordered trees by forgetting the ordering.)

sage: from sage.combinat.abstract_tree import from_hexacode
sage: RT = RootedTrees()
sage: from_hexacode('32001010', RT)
[[[]], [[]], [[], []]]

>>> from sage.all import *
>>> from sage.combinat.abstract_tree import from_hexacode
>>> RT = RootedTrees()
>>> from_hexacode('32001010', RT)
[[[]], [[]], [[], []]]

Note

Unlike an ordered tree, an (unordered) rooted tree is a multiset (rather than a list) of children. That is, two ordered trees which differ from each other by switching the order of children are equal to each other as (unordered) rooted trees. Internally, rooted trees are encoded as sage.structure.list_clone.NormalizedClonableList instances, and instead of storing their children as an actual multiset, they store their children as a list which is sorted according to their sort_key() value. This is as good as storing them as multisets, since the sort_key() values are sortable and distinguish different (unordered) trees. However, if you wish to define a subclass of RootedTree which implements rooted trees with extra structure (say, a class of edge-colored rooted trees, or a class of rooted trees with a cyclic order on the list of children), then the inherited sort_key() method will no longer distinguish different trees (and, as a consequence, equal trees will be regarded as distinct). Thus, you will have to override the method by one that does distinguish different trees.

graft_list(other)[source]#

Return the list of trees obtained by grafting other on self.

Here grafting means that one takes the disjoint union of self and other, chooses a node of self, and adds the root of other to the list of children of this node. The root of the resulting tree is the root of self. (This can be done for each node of self; this method returns the list of all results.)

This is useful for free pre-Lie algebras.

EXAMPLES:

sage: RT = RootedTree
sage: x = RT([])
sage: y = RT([x, x])
sage: x.graft_list(x)
[[[]]]
sage: l = y.graft_list(x); l
[[[], [], []], [[], [[]]], [[], [[]]]]
sage: [parent(i) for i in l]
[Rooted trees, Rooted trees, Rooted trees]

>>> from sage.all import *
>>> RT = RootedTree
>>> x = RT([])
>>> y = RT([x, x])
>>> x.graft_list(x)
[[[]]]
>>> l = y.graft_list(x); l
[[[], [], []], [[], [[]]], [[], [[]]]]
>>> [parent(i) for i in l]
[Rooted trees, Rooted trees, Rooted trees]
graft_on_root(other)[source]#

Return the tree obtained by grafting other on the root of self.

Here grafting means that one takes the disjoint union of self and other, and adds the root of other to the list of children of self. The root of the resulting tree is the root of self.

This is useful for free Nap algebras.

EXAMPLES:

sage: RT = RootedTree
sage: x = RT([])
sage: y = RT([x, x])
sage: x.graft_on_root(x)
[[]]
sage: y.graft_on_root(x)
[[], [], []]
sage: x.graft_on_root(y)
[[[], []]]

>>> from sage.all import *
>>> RT = RootedTree
>>> x = RT([])
>>> y = RT([x, x])
>>> x.graft_on_root(x)
[[]]
>>> y.graft_on_root(x)
[[], [], []]
>>> x.graft_on_root(y)
[[[], []]]
is_empty()[source]#

Return if self is the empty tree.

For rooted trees, this always returns False.

Note

This is not the same as bool(t), which returns whether t has some child or not.

EXAMPLES:

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

>>> from sage.all import *
>>> t = RootedTrees(Integer(4))([[],[[]]])
>>> t.is_empty()
False
>>> bool(t)
True
>>> t = RootedTrees(Integer(1))([])
>>> t.is_empty()
False
>>> bool(t)
False
normalize()[source]#

Normalize self.

This function is at the core of the implementation of rooted (unordered) trees. The underlying structure is provided by ordered rooted trees. Every rooted tree is represented by a normalized element in the set of its planar embeddings.

There should be no need to call normalize directly as it is called automatically upon creation and cloning or modification (by NormalizedClonableList).

The normalization has a recursive definition. It means first that every sub-tree is itself normalized, and also that sub-trees are sorted. Here the sort is performed according to the values of the sort_key() method.

EXAMPLES:

sage: RT = RootedTree
sage: RT([[],[[]]]) == RT([[[]],[]])  # indirect doctest
True
sage: rt1 = RT([[],[[]]])
sage: rt2 = RT([[[]],[]])
sage: rt1 is rt2
False
sage: rt1 == rt2
True
sage: rt1._get_list() == rt2._get_list()
True

>>> from sage.all import *
>>> RT = RootedTree
>>> RT([[],[[]]]) == RT([[[]],[]])  # indirect doctest
True
>>> rt1 = RT([[],[[]]])
>>> rt2 = RT([[[]],[]])
>>> rt1 is rt2
False
>>> rt1 == rt2
True
>>> rt1._get_list() == rt2._get_list()
True
single_graft(x, grafting_function, path_prefix=())[source]#

Graft subtrees of \(x\) on self using the given function.

Let \(x_1, x_2, \ldots, x_p\) be the children of the root of \(x\). For each \(i\), the subtree of \(x\) comprising all descendants of \(x_i\) is joined by a new edge to the vertex of self specified by the \(i\)-th path in the grafting function (i.e., by the path grafting_function[i]).

The number of vertices of the result is the sum of the numbers of vertices of self and \(x\) minus one, because the root of \(x\) is not used.

This is used to define the product of the Grossman-Larson algebras.

INPUT:

  • \(x\) – a rooted tree

  • grafting_function – a list of paths in self

  • path_prefix – optional tuple (default ())

The path_prefix argument is only used for internal recursion.

EXAMPLES:

sage: LT = LabelledRootedTrees()
sage: y = LT([LT([],label='b')], label='a')
sage: x = LT([LT([],label='d')], label='c')
sage: y.single_graft(x,[(0,)])
a[b[d[]]]
sage: t = LT([LT([],label='b'),LT([],label='c')], label='a')
sage: s = LT([LT([],label='d'),LT([],label='e')], label='f')
sage: t.single_graft(s,[(0,),(1,)])
a[b[d[]], c[e[]]]

>>> from sage.all import *
>>> LT = LabelledRootedTrees()
>>> y = LT([LT([],label='b')], label='a')
>>> x = LT([LT([],label='d')], label='c')
>>> y.single_graft(x,[(Integer(0),)])
a[b[d[]]]
>>> t = LT([LT([],label='b'),LT([],label='c')], label='a')
>>> s = LT([LT([],label='d'),LT([],label='e')], label='f')
>>> t.single_graft(s,[(Integer(0),),(Integer(1),)])
a[b[d[]], c[e[]]]
sort_key()[source]#

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

The first entry of the tuple is the number of children of the root. Then the rest of the tuple is obtained as follows: List the tuples corresponding to all children (we are regarding the children themselves as trees). Order this list (not the tuples!) in lexicographically increasing order, and flatten it into a single tuple.

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

Note

The tree self must be normalized before calling this method (see normalize()). This does not matter unless you are inside the clone() context manager, because outside of it every rooted tree is already normalized.

Note

By default, this method does not encode any extra structure that self might have. If you have a subclass inheriting from RootedTree which allows for some extra structure, you need to override sort_key() in order to preserve this structure (for example, the LabelledRootedTree class does this in LabelledRootedTree.sort_key()). See the note in the docstring of sage.combinat.ordered_tree.OrderedTree.sort_key() for a pitfall.

EXAMPLES:

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

>>> from sage.all import *
>>> RT = RootedTree
>>> RT([[],[[]]]).sort_key()
(2, 0, 1, 0)
>>> RT([[[]],[]]).sort_key()
(2, 0, 1, 0)
class sage.combinat.rooted_tree.RootedTrees[source]#

Bases: UniqueRepresentation, Parent

Factory class for rooted trees.

INPUT:

  • size – (optional) an integer

OUTPUT:

the set of all rooted trees (of the given size size if specified)

EXAMPLES:

sage: RootedTrees()
Rooted trees

sage: RootedTrees(2)
Rooted trees with 2 nodes

>>> from sage.all import *
>>> RootedTrees()
Rooted trees

>>> RootedTrees(Integer(2))
Rooted trees with 2 nodes
class sage.combinat.rooted_tree.RootedTrees_all[source]#

Bases: DisjointUnionEnumeratedSets, RootedTrees

Class of all (unordered, unlabelled) rooted trees.

See RootedTree for a definition.

Element[source]#

alias of RootedTree

labelled_trees()[source]#

Return the set of labelled trees associated to self.

EXAMPLES:

sage: RootedTrees().labelled_trees()
Labelled rooted trees

>>> from sage.all import *
>>> RootedTrees().labelled_trees()
Labelled rooted trees

As a consequence:

sage: lb = RootedTrees()([[],[[], []]]).canonical_labelling()
sage: lb
1[2[], 3[4[], 5[]]]
sage: lb.__class__
<class 'sage.combinat.rooted_tree.LabelledRootedTrees_all_with_category.element_class'>
sage: lb.parent()
Labelled rooted trees

>>> from sage.all import *
>>> lb = RootedTrees()([[],[[], []]]).canonical_labelling()
>>> lb
1[2[], 3[4[], 5[]]]
>>> lb.__class__
<class 'sage.combinat.rooted_tree.LabelledRootedTrees_all_with_category.element_class'>
>>> lb.parent()
Labelled rooted trees
leaf()[source]#

Return a leaf tree with self as parent.

EXAMPLES:

sage: RootedTrees().leaf()
[]

>>> from sage.all import *
>>> RootedTrees().leaf()
[]
unlabelled_trees()[source]#

Return the set of unlabelled trees associated to self.

EXAMPLES:

sage: RootedTrees().unlabelled_trees()
Rooted trees

>>> from sage.all import *
>>> RootedTrees().unlabelled_trees()
Rooted trees
class sage.combinat.rooted_tree.RootedTrees_size(n)[source]#

Bases: RootedTrees

The enumerated set of rooted trees with a given number of nodes.

The number of nodes of a rooted tree is defined recursively: The number of nodes of a rooted tree with \(a\) children is \(a\) plus the sum of the number of nodes of each of these children.

cardinality()[source]#

Return the cardinality of self.

EXAMPLES:

sage: RootedTrees(1).cardinality()
1
sage: RootedTrees(3).cardinality()
2

>>> from sage.all import *
>>> RootedTrees(Integer(1)).cardinality()
1
>>> RootedTrees(Integer(3)).cardinality()
2
check_element(el, check=True)[source]#

Check that a given tree actually belongs to self.

This just checks the number of vertices.

EXAMPLES:

sage: RT3 = RootedTrees(3)
sage: RT3([[],[]])     # indirect doctest
[[], []]
sage: RT3([[],[],[]])  # indirect doctest
Traceback (most recent call last):
...
ValueError: wrong number of nodes

>>> from sage.all import *
>>> RT3 = RootedTrees(Integer(3))
>>> RT3([[],[]])     # indirect doctest
[[], []]
>>> RT3([[],[],[]])  # indirect doctest
Traceback (most recent call last):
...
ValueError: wrong number of nodes
element_class()[source]#
sage.combinat.rooted_tree.number_of_rooted_trees()[source]#

Return the number of rooted trees with \(n\) nodes.

Compute the number \(a(n)\) of rooted trees with \(n\) nodes using the recursive formula ([SL000081]):

\[a(n+1) = \frac{1}{n} \sum_{k=1}^{n} \left( \sum_{d|k} d a(d) \right) a(n-k+1)\]

EXAMPLES:

sage: from sage.combinat.rooted_tree import number_of_rooted_trees
sage: [number_of_rooted_trees(i) for i in range(10)]
[0, 1, 1, 2, 4, 9, 20, 48, 115, 286]

>>> from sage.all import *
>>> from sage.combinat.rooted_tree import number_of_rooted_trees
>>> [number_of_rooted_trees(i) for i in range(Integer(10))]
[0, 1, 1, 2, 4, 9, 20, 48, 115, 286]

REFERENCES: