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 treeslabel
– any hashable Sage object (default isNone
)
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 theirsort_key()
value. This is as good as storing them as multisets, since thesort_key()
values are sortable and distinguish different (unordered) trees. However, if you wish to define a subclass ofRootedTree
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 inheritedsort_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