Let $T\_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T\_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is now an Eulerian directed graph with $2(n-1)$ edges and by the B.E.S.T theorem it has $\prod\limits\_{i=1}^n (\deg\_{D(T)}(v\_i)-1)!$ many Euler circuits.


Let $A\_n \subset T\_n$ be the set of all labelled trees with $n$ vertices, with the property that vertices $v\_1$ and $v\_2$ have a distance of $2$, i.e. there is no connection between $v\_1$ and $v\_2$, but there is a $t \in \{3,...,n\}$ such that there are edges $(v\_1,v\_t)$ and $(v\_2,v\_t)$.


**Question:** Is there a simpler formula for the expression
$$
\sum\limits\_{T \in A\_n} \prod\limits\_{i=1}^n (\deg\_{D(T)}(v\_i)-1)! \ ,
$$
which counts the number of Euler circuits through trees from $A\_n$.


If the distance is prescribed as $1$ instead of $2$, then by using the fact that there are ${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)$ the formula is found to be $2 \frac{(2n-3)!}{n!}$.


Another way of formulating the question would be: 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?


Any help is much apprechiated.



Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two
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 empirically also be to sufficient, although a proof eludes me at present.


If so then the number of trees with given vertex degrees $d\_i$ (where each $d\_i \ge 1$ and $d\_n \ge 2$) having subtree $v\_{n-1} - v\_n - v\_{n-2}$ is a sum of three multinomial coefficients which simplifies to $$\binom{n-2}{d\_1-1, \ldots, d\_n-1} \frac{(d\_n - 1)(d\_{n-2} + d\_{n-1} + d\_n - 4)}{(n-3)(n-2)}$$


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 given by relabelling to put the special vertices at $v\_1$, $v\_2$ and summing over all possible intermediate vertices. $$\sum\_{i=3}^n [d\_i \ge 2] \binom{n-2}{d\_1-1, \ldots, d\_n-1} \frac{(d\_i - 1)(d\_1 + d\_2 + d\_i - 4)}{(n-3)(n-2)}$$ simplifies to $$\frac{1}{(n-3)(n-2)} \binom{n-2}{d\_1-1, \ldots, d\_n-1} \left((n - d\_1 - d\_2)(d\_1 + d\_2 - 5) - (n-2) + \sum\_{i=3}^n d\_i^2 \right)$$


