<>
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.