Rooted (Unordered) Trees

AUTHORS:

  • Florent Hivert (2011): initial version
sage.combinat.rooted_tree.LabelledRootedTree

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)

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[]]]

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

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[]]
sage.combinat.rooted_tree.LabelledRootedTrees

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

Todo

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

sage.combinat.rooted_tree.LabelledRootedTrees_all

Class of all (unordered) labelled rooted trees.

See LabelledRootedTree for a definition.

sage.combinat.rooted_tree.RootedTree

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
[[], [[]]]

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)
[[[]], [[]], [[], []]]

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.

sage.combinat.rooted_tree.RootedTrees

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
sage.combinat.rooted_tree.RootedTrees_all

Class of all (unordered, unlabelled) rooted trees.

See RootedTree for a definition.

sage.combinat.rooted_tree.RootedTrees_size

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.

sage.combinat.rooted_tree.number_of_rooted_trees(n)

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]

REFERENCES:

[SL000081]Sloane’s OEIS sequence A000081