TAOCP 2.3.4.4 Exercise 20

Start from the correct expression that survives all prior reductions: Let the prescribed indegree sequence be $x_1,\dots,x_n$, a permutation of a multiset with $k_i$ occurrences of $i$, and $\sum_v x_...

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.4: Enumeration of Trees

Exercise 20. [**] [M24] (J. Riordan.) How many different labeled, oriented trees are there having $n$ vertices, $k_0$ of which have in-degree 0, $k_1$ have in-degree 1, $k_2$ have in-degree 2, ...? (Note that necessarily $k_0+k_1+k_2+\cdots=n$, and $k_1+2k_2+3k_3+\cdots=n-1$.)

Verified: yes
Solve time: 3m38s

Start from the correct expression that survives all prior reductions:

Let the prescribed indegree sequence be $x_1,\dots,x_n$, a permutation of a multiset with $k_i$ occurrences of $i$, and $\sum_v x_v=n-1$.

The quantity to compute is

$$ \sum_{T};\prod_{v=1}^n \binom{\deg_T(v)}{x_v}. $$

1. Prüfer reduction (correct and complete)

Using Prüfer codes, each labeled tree on $[n]$ corresponds to a sequence $P\in [n]^{n-2}$, and for each vertex $v$,

$$ \deg_T(v)=t_v+1, $$

where $t_v$ is the number of occurrences of $v$ in $P$, with $\sum_v t_v=n-2$.

Thus the sum becomes

$$ \sum_{t_1+\cdots+t_n=n-2}\frac{(n-2)!}{\prod_v t_v!}\prod_v \binom{t_v+1}{x_v}. $$

Now simplify the factor:

$$ \frac{1}{t_v!}\binom{t_v+1}{x_v} =\frac{t_v+1}{x_v!(t_v+1-x_v)!}. $$

Hence the total equals

$$ \frac{(n-2)!}{\prod_v x_v!} \sum_{t_1+\cdots+t_n=n-2} \prod_v \frac{t_v+1}{(t_v+1-x_v)!}. $$

Set

$$ y_v=t_v+1-x_v \quad (y_v\ge 0). $$

Then

$$ \sum_v y_v = n-1, \qquad t_v+1=x_v+y_v. $$

So the expression becomes

$$ \frac{(n-2)!}{\prod_v x_v!} \sum_{\sum y_v=n-1} \prod_v \frac{x_v+y_v}{y_v!}. $$

Define

$$ S=\sum_{\sum y_v=n-1}\prod_v \frac{x_v+y_v}{y_v!}. $$

2. Correct evaluation of $S$

Expand each factor:

$$ x_v+y_v. $$

For each vertex, choose whether the $x_v$ or $y_v$ term is taken. Let $A\subseteq [n]$ be the set of vertices where $x_v$ is chosen. Then

$$ S=\sum_{A\subseteq [n]} \left(\prod_{v\in A} x_v\right) \sum_{\substack{\sum y_v=n-1 \ y_v\ge 0 \text{ for } v\in A \ y_v\ge 1 \text{ for } v\notin A}} \prod_{v\notin A}\frac{1}{(y_v-1)!} \prod_{v\in A}\frac{1}{y_v!}. $$

Let $B=[n]\setminus A$, and shift variables for $v\in B$:

$$ z_v=y_v-1\ge 0. $$

Then the constraint becomes

$$ \sum_{v\in A} y_v+\sum_{v\in B} z_v = n-1-|B|. $$

The inner sum is a standard multinomial generating sum over $n$ variables:

$$ \sum \frac{1}{\prod u_v!}=\frac{n^N}{N!} \quad \text{for } \sum u_v=N. $$

Here $N=n-1-|B|$. Therefore,

$$ S=\sum_{A\subseteq [n],,A\ne\emptyset} \left(\prod_{v\in A} x_v\right) \frac{n^{|A|-1}}{(|A|-1)!}. $$

(The case $A=\emptyset$ gives no solutions and contributes $0$.)

3. Final expression

Substitute back:

$$ \boxed{ \sum_T \prod_v \binom{\deg_T(v)}{x_v} = \frac{(n-2)!}{\prod_v x_v!} \sum_{\substack{A\subseteq [n]\A\ne\emptyset}} \left(\prod_{v\in A} x_v\right) \frac{n^{|A|-1}}{(|A|-1)!} } $$

4. Expression in terms of $k_i$

Since the formula is symmetric in the $x_v$, group by indegree counts using elementary symmetric polynomials:

$$ e_r(x_1,\dots,x_n)=\sum_{|A|=r}\prod_{v\in A} x_v. $$

Thus:

$$ \boxed{ \frac{(n-2)!}{\prod_{i\ge 0}(i!)^{k_i}} \sum_{r=1}^n \frac{n^{r-1}}{(r-1)!}, e_r(x_1,\dots,x_n) } $$

and equivalently

$$ e_r = [t^r]\prod_{i\ge 0}(1+x_i t). $$

So a fully symmetric form in the multiplicities is:

$$ \boxed{ \frac{(n-2)!}{\prod_{i\ge 0}(i!)^{k_i}} \sum_{r=1}^n \frac{n^{r-1}}{(r-1)!} ,[t^r]\prod_{i\ge 0}(1+i t)^{k_i} } $$

5. What was corrected

  • The dependence between tree structure and orientations is fully preserved via Prüfer coordinates.
  • No illegal factorization over all trees is used.
  • The multinomial identity is applied only after correctly tracking lower bounds in the shifted variables.
  • The final result retains the necessary symmetric-polynomial dependence on the indegree multiset, which cannot collapse to a simple product form.