<> Definition & Example ==================== - An **ordered tree** is a rooted tree where the children of each node are ordered. - Equivalently, an **ordered tree** is recursively defined to be either a *leaf* (*external node*) or an ordered list of ordered trees (*internal node*). <> - There are $\operatorname{Cat}(n) = \frac{1}{n+1}\binom{2n}{n}$ ordered trees with $n+1$ nodes, see [OEIS:A000108](http://oeis.org/A000108). Additional information ====================== **Feel free to add further combinatorial information here!** References ========== - [Wikipedia](https://en.wikipedia.org/wiki/Ordered_tree) <> Sage examples ============= {{{#!sagecell for n in [2,3,4]: BTs = OrderedTrees(n) print n, BTs.cardinality() for bt in OrderedTrees(3): print bt }}} Technical information for database usage ======================================== - An ordered tree is uniquely **represented as an empty list** (leaf) **or as a sorted list of ordered trees** (internal node). - Ordered trees are **graded by its number of nodes**. - The database contains all ordered trees of size at most 9.