Skip to main content
1 of 3
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

Wlog we can use $v_{n-2}$ and $v_{n-1}$ instead of $v_1$ and $v_2$. Then if we let $B_n \subset T_n$ be the set of labelled trees with edges $(v_{n-2}, v_n)$ and $(v_{n-1}, v_n)$, the count for $A_n$ is just $(n-2)$ times the count for $B_n$ (there are $n-2$ choices for $v_t$; swap $v_t$ for $v_n$ if they're different).

The advantage to numbering things this way is that when constructing the Prüfer codes for the trees in $B_n$ the three labelled vertices are the last survivors. The final label in the Prüfer code will be $n$, and the penultimate one (if $n > 3$) will be in $\{n-2, n-1, n\}$. This appears also be to sufficient. If so then taking the alternative formulation

For given $d_1,...,d_{n} \in \{1,...,n-1\}^n$ with $d_1+...+d_n = 2n-2$, how many of the ${n-2 \choose d_1-1,...,d_{n}-1}$ many $T \in T_n$ with $d_i = \deg_{T}(v_i) = \deg_{D(T)}(v_i)$ satisfy the condition that $v_1$ and $v_2$ have distance two?

the answer is $(n-2)$ times a sum of three multinomial coefficients, and simplifies to $$(n-2) \binom{n-4}{d_1-1, \ldots, d_{n-1}-1, d_n-2, 1} (d_{n-2} + d_{n-1} + d_n - 4)$$

Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29