Def/Rooted ordered binary tree

Definition of Composition tree: Let $n$ be a positive natural number. A binary composition tree (or rooted ordered binary tree) with $n$ leaves, is defined recursively as follows:

A composition tree with leaf set $\{a,b,c \}$

• A set $L$ called the set of leaves.
• A set $T$, which is one of the following:
  • If $n = 1$, then $L = \{ T \} $.
  • If $n > 1$, then there exist positive natural numbers $n_\ell,n_r$ such that:
    • $n_\ell + n_r = n$.
    • $T = (T_\ell, T_r)$ is an ordered pair.
    • There exist subsets $L_\ell, L_r \subset L$, such that:
      • $(T_\ell, L_\ell)$ is a binary composition tree with $n_\ell$ leaves.
      • $(T_r, L_r)$ is a binary composition tree with $n_r$ leaves.
      • $L_\ell \cup L_r = L$.

Binary composition trees $(T,L)$ are visualized as follows:

• One begins with a point, called the root.
• If $T$ is a binary composition tree with one leaf, $L = \{ T \}$, then the root point is labelled by $T$.
• Otherwise, one draws two edges, one left and one right, but both downward from the root.
• At the ends of these edges, one draws the binary composition trees $(T_\ell, L_\ell)$ (at the left), and $(T_r, L_r)$ at the right.
• One continues recursively, until all leaves are reached.