# Let $V=\{1,2,…,n\}$ be a set of vertices. How many directed trees are there over $V$ such that there are exactly 2 vertices with out degree of 0

Let V=$$\{1,2,...,n\}$$ be a set of vertices. How many directed trees are there over V such that there are exactly 2 vertices with out degree of 0?

My first thought was to use symmetry, and that after finding the number of directed trees over $$V$$ such that $$d_{out}(1)=d_{out}(2)=0$$, and then multiplying the answer by $${n \choose 2}$$.

Using the laplacian matrix seems pointless to me because I have no control over other vertices that will have out degree of $$0$$.

I know that over a finite number of vertices, it is enough to make sure that there is $$r\in V$$ such that $$d_{in}(r)=0$$, and that for all $$u\neq r$$, $$d_{in}(u)=1$$, in addition to that that the graph must not have cycles in it.

Now, I tried to use symmetry again. 1 and 2 will never be roots, and by symmetry if I choose a random vertex to be a root, I will need to multiply the result by $$n-2$$ to get all the possibilities.

However this is pretty tricky as well, the best I got is that this number equals to words over $$V$$, with a length of $$n-1$$ with these conditions:

1. 1 and 2 don't appear in the word.

2. All other vertices appear at least once.

3. All vertices except the root (and 1 and 2) has a single place in the word where they can't appear.

4. The root must appear at least once after the first two letters.

Now I am quite stuck however, is there a more simple way to solve this problem that I missed?

Here is an easier way to arrive at Marko Riedel's answer.

Since we are dealing with labeled directed graphs, we will need to choose a root. There are $$n$$ ways to do this.

Now we must choose two nodes from the remaining $$n-1$$ nodes that will serve as our leaves. There are $$n-1 \choose 2$$ ways to do this.

Finally we must figure out what to do with the rest of the nodes. Let P denote the path from the root to one of the leaves and Q denote the path from the root to the other leaf. Since there are only two leaves, each of the remaining nodes either is contained in both P and Q, only P, or only Q.

Thus we must count how many ways are there to put $$n-3$$ nodes into $$3$$ sets keeping order in mind. Note that this is a classic stars and bars problem with $$n-3$$ labeled stars and $$2$$ bars. The number of ways to do this is $$\frac{(n-3+2)!}{2!} = \frac{(n-1)!}{2}$$

Combining these three parts gives us: $$n \cdot {n -1 \choose 2} \cdot \frac{(n-1)!}{2} = \frac{n!(n-1)(n-2)}{4}$$

The combinatorial class of rooted labeled trees with leaves marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{U} \times \mathcal{Z} + \mathcal{Z} \times \textsc{SET}_{\ge 1}(\mathcal{T})$$

Which gives the functional equation (EGF)

$$T(z) = uz + z \times (\exp T(z) - 1)$$

so that

$$z = \frac{T(z)}{\exp T(z)-1+u}$$

We then have (this is an OGF in $$u$$)

$$T_n = (n-1)! [z^{n-1}] T'(z)$$

and from the Cauchy Coefficient Formula

$$(n-1)! [z^{n-1}] T'(z) = \frac{(n-1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} T'(z) \; dz.$$

Now put $$T(z) = w$$ so that $$T'(z) \; dz = dw$$

and we obtain

$$\frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{(\exp(w)-1+u)^n}{w^n} \; dw.$$

Extracting the count of $$k$$ leaves where $$1\le k\le n-1$$ we find

$${n\choose k} \frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{(\exp(w)-1)^{n-k}}{w^n} \; dw \\ = {n\choose k} \frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^n} \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} \exp(qw) \; dw \\ = {n\choose k} (n-1)! \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} \frac{q^{n-1}}{(n-1)!} \; dw.$$

We thus have for the answer

$$\bbox[5px,border:2px solid #00A000]{ {n\choose k} \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} q^{n-1}.}$$

This points us to OEIS A055302 where these data are confirmed. Observe that this simplifies by inspection to

$$\frac{n!}{k!} \frac{1}{(n-k)!} \sum_{q=0}^{n-k} {n-k\choose q} (-1)^{n-k-q} q^{n-1} = \frac{n!}{k!} {n-1\brace n-k}.$$

As a sanity check we should have obtained all of them. The sum may include $$k=0$$ and $$k=n$$ because the corresponding Stirling numbers are zero:

$$\sum_{k=0}^{n} \frac{n!}{k!} {n-1\brace n-k} = \sum_{k=0}^{n} \frac{n!}{k!} (n-1)! [z^{n-1}] \frac{(\exp(z)-1)^{n-k}}{(n-k)!} \\ = (n-1)! [z^{n-1}] \sum_{k=0}^{n} {n\choose k} (\exp(z)-1)^{n-k} \\ = (n-1)! [z^{n-1}] \exp(nz) = (n-1)! \frac{n^{n-1}}{(n-1)!} = n^{n-1}$$

and the check goes through. We get for the case of two leaves the result

$$\frac{1}{2} n! {n-1\brace n-2} = \frac{1}{2} n! {n-1\choose 2}$$

or

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{4} n! \times (n-1) \times (n-2).}$$

This will produce starting at three:

$$3, 36, 360, 3600, 37800, 423360, 5080320, 65318400, \ldots$$

which points to OEIS A055303.

Vertices with out-degree = 0 are leaves.

So you have exactly two leaves in a directed tree. Traverse edges back from those leaves to root (to see how it looks like).

So you order your vertices in a string, then decide who is the root - and you get a tree with two leaves. And leaves can not be roots.

In the end divide by 2, to count for symmetry.

Kind of $$\frac{(n-2)\cdot n!}{2}$$ different trees.