# Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:

• The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
• $T$ has a distinguished vertex $v_1$ such that all directions on the edges of $T$ are pointing outward from $v_1$.

$T$ also comes equipped with an ordering on the vertices $f:\{v_1,v_2,\ldots,v_n\}\to\{1,2,\ldots,n\}$ which is consistent with the directions on the edges. That is, if $(v_i,v_j)$ is a directed edge in $T$, then $f(v_i)<f(v_j)$ (thus immediately we have $f(v_1)=1$).

Question: Can we count the number of all such trees with all such orderings?

I asked the more general question (where $T$ is replaced by any connected directed graph $G$) of my graph theory teacher in graduate school, and recall him saying it was NP-complete (a reference for this would be welcome), but I am curious about the restricted question above.

Such trees are sometimes called increasing 0-1-2 trees. The number of them with $n$ vertices is the Euler number $E_n$. See http://oeis.org/A000111.