6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.