TAOCP 2.3.4.4 Exercise 21

Let $k_i$ denote the number of vertices of in-degree $i$.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.4: Enumeration of Trees

Exercise 21. [**] [M21] Enumerate the number of labeled oriented trees in which each vertex has in-degree zero or two. (See exercise 20 and exercise 2.3-20.)

Verified: yes
Solve time: 1m10s

Let $k_i$ denote the number of vertices of in-degree $i$. By hypothesis, every vertex has in-degree $0$ or $2$, so $k_i=0$ for $i\ne0,2$. Exercise 20 gives the number of labeled oriented trees with prescribed in-degree distribution:

$$ \frac{(n-1)! , n!}{\prod_i k_i!,(i!)^{k_i}}. $$

Since

$$ k_0+k_2=n,\qquad 2k_2=n-1, $$

we obtain

$$ k_2=\frac{n-1}{2},\qquad k_0=\frac{n+1}{2}. $$

Hence such trees exist only when $n$ is odd. Substituting these values into the formula of Exercise 20 yields

$$ \frac{(n-1)!,n!} {\left(\frac{n+1}{2}\right)! \left(\frac{n-1}{2}\right)! (2!)^{(n-1)/2}}. $$

Therefore the number of labeled oriented trees in which every vertex has in-degree $0$ or $2$ is

$$ \boxed{ \frac{(n-1)!,n!} {\left(\frac{n+1}{2}\right)! \left(\frac{n-1}{2}\right)! 2^{(n-1)/2}} } $$

for odd $n$, and

$$ \boxed{0} $$

for even $n$. ∎