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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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}$$