Planted Planar Tree

A planted plane tree $(V, E, v, \alpha)$ is defined as a vertex set $V$, edges set $E$, Root $v$, and order relation $\alpha$ on $V$ which satisfies

1. For $x,y\in V$ if $\rho(x)<\rho(y)$, then $x\mathop\alpha y$, where $\rho(x)$ is the length of the path from $v$ to $x$,

2. If $\{r,s\}$, $\{x,y\}\in E$, $\rho(r)=\rho(x)=\rho(s)-1=\rho(y)-1$ and $r\mathop\alpha x$, then $s\mathop\alpha y$

(Klarner 1969, Chorneyko and Mohanty 1975). The Catalan Numbers give the number of planar trivalent planted trees.

See also Catalan Number, Tree

References

Chorneyko, I. Z. and Mohanty, S. G. ``On the Enumeration of Certain Sets of Planted Plane Trees.'' J. Combin. Th. Ser. B 18, 209-221, 1975.

Harary, F.; Prins, G.; and Tutte, W. T. ``The Number of Plane Trees.'' Indag. Math. 26, 319-327, 1964.

Klarner, D. A. ``A Correspondence Between Sets of Trees.'' Indag. Math. 31, 292-296, 1969.