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

Question

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.

Answer 1

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.

Answer 2

The tree can be see as a poset, and the labeling corresponds to counting linear extensions. This can be interpreted as computing the volume of an order polytope. See the first volume on enumerative combinatorics by Stanley.

There are hook formulas for counting linear extensions of trees. See the result by Knuth.

To sum over all trees should make the problem easier I think, using generating functions.

Answer 3

This tree is called binary tree and what you are asking are all the possible ordered arrangements of it ( when we don't care which arrangement is on the left and which on the right subtree of the root). What you are asking is a famous question and you can find the answer + a couple of mathematical proves and different definitions of the problem here - Catalan Numbers