# The expected value under the Yule model of the squared path-difference
distance

Gabriel Cardona<EMAIL_ADDRESS>Arnau Mir<EMAIL_ADDRESS>Francesc
Rosselló<EMAIL_ADDRESS>Department of Mathematics and Computer Science,
University of the Balearic Islands, E-07122 Palma de Mallorca, Spain

###### Abstract

The path-difference metric is one of the oldest and most popular distances for
the comparison of phylogenetic trees, but its statistical properties are still
quite unknown. In this paper we compute the expected value under the Yule
model of evolution of its square on the space of fully resolved rooted
phylogenetic trees with $n$ leaves. This complements previous work by
Steel–Penny and Mir–Rosselló, who computed this mean value for fully resolved
unrooted and rooted phylogenetic trees, respectively, under the uniform
distribution.

###### keywords:

Phylogenetic tree, Nodal distance, Path-difference metric, Yule model, Sackin
index

##  1 Introduction

The definition and study of metrics for the comparison of rooted phylogenetic
trees on the same set of taxa is a classical problem in phylogenetics [6, Ch.
30]. A classical and popular family of such metrics is based on the
comparison, by different methods, of the vectors of lengths of the
(undirected) paths connecting all pairs of taxa in the corresponding trees [4,
5, 14, 20]. These metrics are generically called _nodal distances_ , although
some of them have also specific names. For instance, the metric defined
through the euclidean distance between path-lengths vectors is called _path-
difference metric_ [18], or _cladistic difference_ [4].

In contrast with other metrics, the statistical properties of these nodal
distances are mostly unknown. Actually, the only statistical property that has
been established so far for any one of them is the expected, or mean, value of
the square of the path-difference metric for unrooted [18] and rooted [11]
fully resolved phylogenetic trees under the uniform distribution (that is,
when all phylogenetic trees with the same number of taxa are equiprobable).
The knowledge of the expected value of a metric is useful, because it provides
an indication about the significance of the similarity of two individuals
measured through this metric [18].

But phylogeneticists consider also other probabilistic distributions on the
space of phylogenetic trees on a fixed set of taxa, defined through stochastic
models of evolution [6, Ch. 33]. The most popular such model is Yule’s [7,
21], defined by an evolutionary process where, at each step, each currently
extant species can give rise, with the same probability, to two new species.
Under this model, different phylogenetic trees with the same number of leaves
may have different probabilities. Formal details on this model are given in
the next section.

In this paper we compute the expected value of the square of the path-
difference metric for rooted fully resolved phylogenetic trees under this Yule
model. Besides the aforementioned application of this value in the assessment
of tree comparisons, the knowledge of formulas for this expected value under
different models may allow the use of the path-difference metric to test
stochastic models of tree growth, a popular line of research in the last years
which so far has been mostly based on shape indices [13].

##  2 Preliminaries

In this paper, by a _phylogenetic tree_ on a set $S$ of taxa we mean a fully
resolved, or binary, rooted tree with its leaves bijectively labeled in $S$.
We understand such a rooted tree as a directed graph, with its arcs pointing
away from the root. To simplify the language, we shall always identify a leaf
of a phylogenetic tree with its label. We shall also use the term
_phylogenetic tree with $n$ leaves_ to refer to a phylogenetic tree on the set
$\\{1,\ldots,n\\}$. We shall denote by $\mathcal{T}(S)$ the space of all
phylogenetic trees on $S$ and by $\mathcal{T}_{n}$ the space of all
phylogenetic trees with $n$ leaves.

Whenever there exists a directed path from $u$ to $v$ in a phylogenetic tree
$T$, we shall say that $v$ is a _descendant_ of $u$. The _distance_
$d_{T}(u,v)$ between two nodes $u,v$ in a phylogenetic tree $T$ is the length
(in number of arcs) of the unique undirected path connecting $u$ and $v$. The
_depth_ $\delta_{T}(v)$ of a node $v$ in $T$ is the distance from the root $r$
of $T$ to $v$. The _path-difference distance_ [4, 5] between a pair of trees
$T,T^{\prime}\in\mathcal{T}_{n}$ is

$d_{\nu}(T,T^{\prime})=\sqrt{\sum_{1\leqslant i<j\leqslant
n}(d_{T}(i,j)-d_{T^{\prime}}(i,j))^{2}}.$

The _Yule_ , or _Equal-Rate Markov_ , model of evolution [7, 21] is a
stochastic model of phylogenetic trees’ growth. It starts with a node, and at
every step a leaf is chosen randomly and uniformly and it is splitted into two
leaves. Finally, the labels are assigned randomly and uniformly to the leaves
once the desired number of leaves is reached. Under this model, if $T$ is a
phylogenetic tree with $n$ leaves and set of internal nodes $V_{int}(T)$, and
if for every internal node $v$ we denote by $\ell_{T}(v)$ the number of its
descendant leaves, then the probability of $T$ is [1, 17]

$P_{Y}(T)=\frac{2^{n-1}}{n!}\prod_{v\in V_{int}(T)}\frac{1}{\ell_{T}(v)-1}.$

For every $n\geqslant 1$, let $H_{n}=\sum_{i=1}^{n}1/i$ and
$H_{n}^{(2)}=\sum_{i=1}^{n}1/i^{2}$. Let, moreover, $H_{0}=H_{0}^{(2)}=0$.
$H_{n}$ is called the $n$-th _harmonic number_ , and $H_{n}^{(2)}$, the $n$-th
_generalized harmonic number of power $2$_.

##  3 Main results

Let $N_{n}^{2}$ the random variable that chooses independently a pair of trees
$T,T^{\prime}\in\mathcal{T}_{n}$ and computes

$d_{\nu}(T,T^{\prime})^{2}=\sum_{1\leqslant i<j\leqslant
n}(d_{T}(i,j)-d_{T^{\prime}}(i,j))^{2}.$

In this section we establish the following result.

######  Theorem 1.

The expected value of $N_{n}^{2}$ under the Yule model is

$E_{Y}(N_{n}^{2})=\frac{2n}{n-1}\big{(}2(n^{2}+24n+7)H_{n}+13n^{2}-46n+1-16(n+1)H_{n}^{2}-8(n^{2}-1)H_{n}^{(2)}\big{)}.$

To prove this formula, we shall use the following auxiliary random variables:

  * 1.

$D_{n}$ is the random variable that chooses a tree $T\in\mathcal{T}_{n}$ and
computes $D(T)=\sum\limits_{1\leqslant i<j\leqslant n}d_{T}(i,j)$.

  * 2.

$D_{n}^{(2)}$ is the random variable that chooses a tree $T\in\mathcal{T}_{n}$
and computes $D^{(2)}(T)=\sum\limits_{1\leqslant i<j\leqslant
n}d_{T}(i,j)^{2}$.

The connection between $E_{Y}(N_{n}^{2})$ and the expected values under the
Yule model of $D_{n},D_{n}^{(2)}$ is given by the following result.

######  Proposition 2.

$E_{Y}(N_{n}^{2})=2\big{(}E_{Y}(D^{(2)}_{n})-E_{Y}(D_{n})^{2}/\binom{n}{2}\big{)}.$

###### Proof.

Let us develop $E_{Y}(N_{n}^{2})$ from its raw definition:

$\begin{array}[]{l}\displaystyle
E_{Y}(N_{n}^{2})=\sum_{T,T^{\prime}\in\mathcal{T}_{n}}d_{\nu}(T,T^{\prime})^{2}p_{Y}(T)p_{Y}(T^{\prime})=\sum_{T,T^{\prime}\in\mathcal{T}_{n}}\Big{(}\sum_{1\leqslant
i<j\leqslant
n}(d_{T}(i,j)-d_{T^{\prime}}(i,j))^{2}\Big{)}p_{Y}(T)p_{Y}(T^{\prime})\\\
\quad\displaystyle=\sum_{1\leqslant i<j\leqslant
n}\sum_{T,T^{\prime}}(d_{T}(i,j)^{2}+d_{T^{\prime}}(i,j)^{2}-2d_{T}(i,j)d_{T^{\prime}}(i,j))p_{Y}(T)p_{Y}(T^{\prime})\\\
\quad\displaystyle=\sum_{1\leqslant i<j\leqslant
n}\Big{(}\sum_{T,T^{\prime}}d_{T}(i,j)^{2}p_{Y}(T)p_{Y}(T^{\prime})+\sum_{T,T^{\prime}}d_{T^{\prime}}(i,j)^{2}p_{Y}(T)p_{Y}(T^{\prime})\\\
\quad\qquad\qquad\qquad\displaystyle-2\sum_{T,T^{\prime}}d_{T}(i,j)d_{T^{\prime}}(i,j)p_{Y}(T)p_{Y}(T^{\prime})\Big{)}\\\
\quad\displaystyle=\sum_{1\leqslant i<j\leqslant
n}\Big{(}\sum_{T}d_{T}(i,j)^{2}p_{Y}(T)+\sum_{T^{\prime}}d_{T^{\prime}}(i,j)^{2}p_{Y}(T^{\prime})-2\Big{(}\sum_{T}d_{T}(i,j)p_{Y}(T)\Big{)}\Big{(}\sum_{T^{\prime}}d_{T^{\prime}}(i,j)p_{Y}(T^{\prime})\Big{)}\Big{)}\\\
\quad\displaystyle=\sum_{1\leqslant i<j\leqslant
n}\Big{(}2\sum_{T}d_{T}(i,j)^{2}p_{Y}(T)-2\Big{(}\sum_{T}d_{T}(i,j)p_{Y}(T)\Big{)}^{2}\Big{)}\\\
\quad\displaystyle=2\sum_{T}\Big{(}\sum_{1\leqslant i<j\leqslant
n}d_{T}(i,j)^{2}\Big{)}p_{Y}(T)-2\sum_{1\leqslant i<j\leqslant
n}\Big{(}\sum_{T}d_{T}(i,j)p_{Y}(T)\Big{)}^{2}\\\
\quad\displaystyle=2E_{Y}(D_{n}^{(2)})-2\binom{n}{2}\Big{(}\sum_{T}{d}_{T}(1,2)p_{Y}(T)\Big{)}^{2}\end{array}$

and now

$E_{Y}(D_{n})=\sum_{T\in\mathcal{T}_{n}}\sum_{1\leqslant i<j\leqslant
n}d_{T}(i,j)p_{Y}(T)=\sum_{1\leqslant i<j\leqslant
n}\sum_{T}d_{T}(i,j)p_{Y}(T)=\binom{n}{2}\sum_{T}d_{T}(1,2)p_{Y}(T)$

from where we deduce that
$\Big{(}\sum\limits_{T}{d}_{T}(1,2)p_{Y}(T)\Big{)}^{2}={E_{Y}(D_{n})^{2}}/{\binom{n}{2}^{2}}$,
and the formula in the statement follows. ∎

Now, it is known that the expected value under the Yule model of $D_{n}$ is

$E_{Y}(D_{n})=2n(n+1)H_{n}-4n^{2}\qquad\mbox{\cite[cite]{[\@@bibref{Number}{MRR}{}{}]}}.$

As far as $E_{Y}(D_{n}^{(2)})$ goes, its value is given by the following
result. We postpone the proof until the appendix at the end of the paper.

######  Theorem 3.

$E_{Y}(D_{n}^{(2)})=8n(n+1)(H_{n}^{2}-H_{n}^{(2)})-2n(15n+7)H_{n}+45n^{2}-n$

Then, replacing in the expression for $E_{Y}(N_{n}^{2})$ given in Proposition
2 , $E_{Y}(D_{n})$ and $E_{Y}(D_{n}^{(2)})$ by their values, we obtain the
formula for $E_{Y}(N_{n}^{2})$ given in Theorem 1.

##  4 Conclusions

In this paper we have computed the expected value $E_{Y}(N_{n}^{2})$ of the
square of the path-difference metric for rooted fully resolved phylogenetic
trees under the Yule model:

$E_{Y}(N_{n}^{2})=\frac{2n}{n-1}\big{(}2(n^{2}+24n+7)H_{n}+13n^{2}-46n+1-16(n+1)H_{n}^{2}-8(n^{2}-1)H_{n}^{(2)}\big{)}.$

This complements the computation of this expected value under the uniform
distribution carried out in [11], which turned out to be

$E_{U}(N_{n}^{2})=2\binom{n}{2}\left(4(n-1)+2-\frac{2^{2(n-1)}}{\binom{2(n-1)}{n-1}}-\left(\frac{2^{2(n-1)}}{\binom{2(n-1)}{n-1}}\right)^{2}\right)$

The proof of the formula for $E_{Y}(N_{n}^{2})$ consists of several long
algebraic manipulations of sums of sequences. Since it is not difficult to
slip some mistake in such long algebraic computations, to double-check our
result we have directly computed the value of $E_{Y}(N_{n}^{2})$ for
$n=3,\ldots,7$ and confirmed that our formula gives the right figures. The
Python scripts used to compute them and the results obtained are available in
the Supplementary Material web page
http:/bioinfo.uib.es/~recerca/phylotrees/nodaldistYule/.

The formulas for $E_{Y}(N_{n}^{2})$ and $E_{U}(N_{n}^{2})$ grow in different
orders: $E_{Y}(N_{n}^{2})$ is in $O(n^{2}\ln(n))$, while $E_{U}(N_{n}^{2})$ is
in $O(n^{3})$. Therefore, they can be used to test the Yule and the uniform
models as null stochastic models of evolution for collections of phylogenetic
trees reconstructed by different methods. This kind of analysis has only been
performed so far through shape indices of single trees, not by means of the
comparison of pairs of trees. We shall report on it elsewhere.

## Acknowledgements

The research reported in this paper has been partially supported by the
Spanish government and the UE FEDER program, through projects MTM2009-07165
and TIN2008-04487-E/TIN. We thank J. Miró for several comments on a previous
version of this work.

## References

  * [1] J. Brown, Probabilities of evolutionary trees. Syst. Biol. 43 (1994), 78–91.
  * [2] G. Cardona, A. Mir, F. Rosselló, Exact formulas for the variance of several balance indices under the Yule model. arXiv:1202.6573v1 [q-bio.PE], submitted.
  * [3] Y. Chen, Q. Hou, H. Jin, The Abel-Zeilberger algorithm. Electron. J. Comb. 18 (2011) # P17.
  * [4] J. S. Farris, A successive approximations approach to character weighting. Syst. Zool. 18 (1969) 374–385.
  * [5] J. S. Farris, On comparing the shapes of taxonomic trees. Syst. Zool. 22 (1973) 50–54.
  * [6] J. Felsenstein, Inferring Phylogenies. Sinauer Associates Inc., 2004.
  * [7] E. Harding, The probabilities of rooted tree-shapes generated by random bifurcation. Adv. Appl. Prob. 3 (1971), 44–77.
  * [8] S. B. Heard, Patterns in Tree Balance among Cladistic, Phenetic, and Randomly Generated Phylogenetic Trees. Evolution 46 (1992), 1818–1826
  * [9] M. Kirkpatrick, M. Slatkin, Searching for evolutionary patterns in the shape of a phylogenetic tree. Evolution 47 (1993), 1171–1181.
  * [10] D. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms (3rd Edition). Addison-Wesley (1997).
  * [11] A. Mir, F. Rosselló, The mean value of the squared path-difference distance for rooted phylogenetic trees. Journal of Mathematical Analysis and Applications 371 (2010), 168–176.
  * [12] A. Mir, F. Rosselló, L. Rotger, A new balance index for phylogenetic trees. arXiv:1202.1223v1 [q-bio.PE] (2012), submitted.
  * [13] A. Mooers, S. B. Heard, Inferring evolutionary process from phylogenetic tree shape. Quart. Rev. Biol. 72 (1997) 31–54.
  * [14] J. B. Phipps, Dendrogram topology, Syst. Zool. 20 (1971) 306–308.
  * [15] M. J. Sackin, “Good” and “bad” phenograms. Sys. Zool, 21 (1972), 225–226.
  * [16] M. Steel, A. McKenzie, Distributions of cherries for two models of trees. Math. Biosc. 164 (2000), 81–92.
  * [17] M. Steel, A. McKenzie, Properties of phylogenetic trees generated by Yule-type speciation models. Math. Biosc. 170 (2001), 91–112.
  * [18] M. A. Steel, D. Penny, Distributions of tree comparison metrics—some new results, Syst. Biol. 42 (2) (1993) 126–141.
  * [19] C. Wei, D. Gong, Q. Wang, Chu-Vandermonde convolution and harmonic number identities. arXiv:1201.0420v1 [math.CO] (2012)
  * [20] W. T. Williams, H. T. Clifford, On the comparison of two classifications of the same set of elements, Taxon 20 (4) (1971) 519–522.
  * [21] G. U. Yule, A mathematical theory of evolution based on the conclusions of Dr J. C. Willis. Phil. Trans. Royal Soc. (London) Series B 213 (1924), 21–87.

## Appendix

In this appendix we prove Proposition 3, as well as of some preliminary
lemmas. To begin with, the following identities on harmonic numbers will be
systematically used in the next proofs, usually without any further notice.

######  Lemma.

For every $n\geqslant 2$:

  1. (1)

$\displaystyle\sum_{k=1}^{n-1}H_{k}=n(H_{n}-1)$

  2. (2)

$\sum\limits_{k=1}^{n-1}kH_{k}=\frac{1}{4}n(n-1)(2H_{n}-1)$

  3. (3)

$\sum\limits_{k=1}^{n-1}{H_{k}}/({k+1})=\frac{1}{2}(H_{n}^{2}-H_{n}^{(2)})$

  4. (4)

$\sum\limits_{k=1}^{n-1}kH_{k}H_{n-k}=\binom{n+1}{2}(H_{n+1}^{2}-H_{n+1}^{(2)}-2H_{n+1}+2)$

  5. (5)

$\sum\limits_{k=1}^{n-1}(H_{k}^{2}-H_{k}^{(2)})=n(H_{n}^{2}-H_{n}^{(2)})-2n(H_{n}-1)$

  6. (6)

$\sum\limits_{k=1}^{n-1}k(H_{k}^{2}-H_{k}^{(2)})=\binom{n}{2}(H_{n}^{2}-H_{n}^{(2)})-\frac{1}{4}n(n-1)(2H_{n}-1)$

###### Proof.

Identities (1)–(3) are well known and easily proved by induction on $n$: see,
for instance, [Knuth2, §6.3, 6.4] and [10, §1.2.7]. Identity (4) is proved in
[19, Thm. 2]. We shall prove (5) and (6) using the technique introduced in
[3]. The main ingredient is _Abel’s lemma on summation by parts_ : for every
two sequences $(a_{k})_{k}$ and $(b_{k})_{k}$,

$\sum_{k=1}^{n-1}(a_{k+1}-a_{k})b_{k}=-\sum_{k=1}^{n-1}(b_{k+1}-b_{k})a_{k+1}+a_{n}b_{n}-a_{1}b_{1}.$

To prove (5), take $a_{k}=k$ and $b_{k}=H_{k}^{2}-H_{k}^{(2)}$, so that
$a_{k+1}-a_{k}=1$ and $b_{k+1}-b_{k}={2H_{k}}/({k+1})$. Then, by Abel’s lemma

$\sum_{k=1}^{n-1}(H_{k}^{2}-H_{k}^{(2)})=-\sum_{k=1}^{n-1}(k+1)\frac{2H_{k}}{k+1}+n(H_{n}^{2}-H_{n}^{(2)})=n(H_{n}^{2}-H_{n}^{(2)})-2\sum_{k=1}^{n-1}H_{k}=n(H_{n}^{2}-H_{n}^{(2)})-2n(H_{n}-1).$

To prove (6), take $a_{k}=\binom{k}{2}$, so that $a_{k+1}-a_{k}=k$, and
$b_{k}=H_{k}^{2}-H_{k}^{(2)}$. Then, again by Abel’s lemma,

$\begin{array}[]{rl}\displaystyle\sum_{k=1}^{n-1}k(H_{k}^{2}-H_{k}^{(2)})&\displaystyle=-\sum_{k=1}^{n-1}\binom{k+1}{2}\frac{2H_{k}}{k+1}+\binom{n}{2}(H_{n}^{2}-H_{n}^{(2)})\\\
&\displaystyle=\binom{n}{2}(H_{n}^{2}-H_{n}^{(2)})-2\sum_{k=1}^{n-1}kH_{k}=\binom{n}{2}(H_{n}^{2}-H_{n}^{(2)})-\frac{1}{4}n(n-1)(2H_{n}-1).\end{array}$

∎

Let us consider now the following two random variables:

  * 1.

$S_{n}$, that chooses a tree $T\in\mathcal{T}_{n}$ and computes its _Sackin
index_ [15] $S(T)=\sum\limits_{i=1}^{n}\delta_{T}(i)$.

  * 2.

$S_{n}^{(2)}$, that chooses a tree $T\in\mathcal{T}_{n}$ and computes
$S^{(2)}(T)=\sum\limits_{1\leqslant i<j\leqslant n}\delta_{T}(i)^{2}$.

It is known that the expected value under the Yule model of $S_{n}$ is

$E_{Y}(S_{n})=2n(H_{n}-1)\qquad\qquad\mbox{\cite[cite]{[\@@bibref{Number}{KiSl:93}{}{}]}}.$

We shall compute now the expected values under this model of $S_{n}^{(2)}$ and
$D_{n}^{(2)}$: the first will be used in the computation of the second. To do
this, we shall use the following recursive expressions for
$S^{(2)}(T\,\widehat{\ }\,T^{\prime})$ and $D^{(2)}(T\,\widehat{\
}\,T^{\prime})$.

######  Lemma.

Let $T,T^{\prime}$ be two phylogenetic trees on disjoint sets of taxa
$S,S^{\prime}$, with $|S|=k$ and $|S^{\prime}|=n-k$. Then:

  1. (1)

$S^{(2)}(T\,\widehat{\
}\,T^{\prime})=S^{(2)}(T)+S^{(2)}(T^{\prime})+2(S(T)+S(T^{\prime}))+n$

  2. (2)

$D^{(2)}(T\,\widehat{\
}\,T^{\prime})=D^{(2)}(T)+D^{(2)}(T^{\prime})+(n-k)(S^{(2)}(T)+4S(T))+k(S^{(2)}(T^{\prime})+4S(T^{\prime}))+2S(T)S(T^{\prime})+4k(n-k)$

###### Proof.

Let us assume, without any loss of generality, that $S=\\{1,\ldots,k\\}$ and
$S^{\prime}=\\{k+1,\ldots,n\\}$ . Then, as far as (1) goes, we have that

$\delta_{T\,\widehat{\
}\,T^{\prime}}(i)^{2}=\left\\{\begin{array}[]{ll}(\delta_{T}(i)+1)^{2}&\mbox{
if $1\leqslant i\leqslant k$}\\\ (\delta_{T^{\prime}}(i)+1)^{2}&\mbox{ if
$k+1\leqslant i\leqslant n$}\end{array}\right.$

and therefore

$\begin{array}[]{l}S^{(2)}(T\,\widehat{\
}\,T^{\prime})\displaystyle=\sum_{i=1}^{n}\delta_{T\,\widehat{\
}\,T^{\prime}}(i)^{2}=\sum_{i=1}^{k}(\delta_{T}(i)+1)^{2}+\sum_{i=k+1}^{n}(\delta_{T^{\prime}}(i)+1)^{2}\\\
\quad\displaystyle=\sum_{i=1}^{k}(\delta_{T}(i)^{2}+2\delta_{T}(i)+1)+\sum_{i=k+1}^{n}(\delta_{T^{\prime}}(i)^{2}+2\delta_{T^{\prime}}(i)+1)=S^{(2)}(T)+2S(T)+S^{(2)}(T^{\prime})+2S(T^{\prime})+n.\end{array}$

As far as (2) goes, we have that

$d_{T\,\widehat{\
}\,T^{\prime}}(i,j)^{2}=\left\\{\begin{array}[]{ll}d_{T}(i,j)^{2}&\mbox{ if
$1\leqslant i<j\leqslant k$}\\\ d_{T^{\prime}}(i,j)^{2}&\mbox{ if
$k+1\leqslant i<j\leqslant n$}\\\
(\delta_{T}(i)+\delta_{T^{\prime}}(j)+2)^{2}&\mbox{ if $1\leqslant i\leqslant
k<j\leqslant n$}\end{array}\right.$

and therefore

$\begin{array}[]{l}\displaystyle D^{(2)}(T\,\widehat{\
}\,T^{\prime})=\sum_{1\leqslant i<j\leqslant n}d_{T\,\widehat{\
}\,T^{\prime}}(i,j)^{2}=\sum_{1\leqslant i<j\leqslant
k}d_{T}(i,j)^{2}+\sum_{k+1\leqslant i<j\leqslant
n}d_{T^{\prime}}(i,j)^{2}+\sum_{1\leqslant i\leqslant k\atop k+1\leqslant
j\leqslant n}(\delta_{T}(i)+\delta_{T^{\prime}}(j)+2)^{2}\\\
\displaystyle\quad=D^{(2)}(T)+D^{(2)}(T^{\prime})+\sum_{1\leqslant i\leqslant
k\atop k+1\leqslant j\leqslant
n}(\delta_{T}(i)^{2}+\delta_{T^{\prime}}(j)^{2}+2\delta_{T}(i)\delta_{T^{\prime}}(j)+4\delta_{T}(i)+4\delta_{T^{\prime}}(j)+4)\\\
\displaystyle\quad=D^{(2)}(T)+D^{(2)}(T^{\prime})+(n-k)\sum_{i=1}^{k}(\delta_{T}(i)^{2}+4\delta_{T}(i))+k\sum_{j=k+1}^{n}(\delta_{T^{\prime}}(j)^{2}+4\delta_{T^{\prime}}(j))\\\
\displaystyle\quad\qquad\qquad\qquad+2\Big{(}\sum_{i=1}^{k}\delta_{T}(i)\Big{)}\Big{(}\sum_{j=k+1}^{n}\delta_{T^{\prime}}(j)\Big{)}+4k(n-k)\\\
\displaystyle\quad=D^{(2)}(T)+D^{(2)}(T^{\prime})+(n-k)(S^{(2)}(T)+4S(T))+k(S^{(2)}(T^{\prime})+4S(T^{\prime}))+2S(T)S(T^{\prime})+4k(n-k).\end{array}$

∎

Now we can compute explicit formulas for $E_{Y}(S_{n}^{(2)})$ and
$E_{Y}(D_{n}^{(2)})$

######  Proposition.

$E_{Y}(S_{n}^{(2)})=4n(H_{n}^{2}-H_{n}^{(2)})-6n(H_{n}-1)$.

###### Proof.

We compute $E_{Y}(S_{n}^{(2)})$ using its very definition:

$\begin{array}[]{l}E_{Y}(S_{n}^{(2)})\displaystyle=\sum_{T\in\mathcal{T}_{n}}S^{(2)}(T)\cdot
p_{Y}(T)=\frac{1}{2}\sum_{k=1}^{n-1}\sum_{S_{k}\subsetneq\\{1,\ldots,n\\}\atop|S_{k}|=k}\sum_{T_{k}\in\mathcal{T}(S_{k})}\sum_{T^{\prime}_{n-k}\in\mathcal{T}(S_{k}^{c})}S^{(2)}(T_{k}\widehat{\
}\,{}T^{\prime}_{n-k})\cdot p_{Y}(T_{k}\widehat{\ }\,{}T^{\prime}_{n-k})\\\
\quad\displaystyle=\frac{1}{2}\sum_{k=1}^{n-1}\binom{n}{k}\sum_{T_{k}\in\mathcal{T}_{k}}\sum_{T^{\prime}_{n-k}\in\mathcal{T}_{n-k}}\Big{(}S^{(2)}(T_{k})+S^{(2)}(T_{n-k}^{\prime})+2(S(T_{k})+S(T_{n-k}^{\prime}))+n\Big{)}\\\
\displaystyle\quad\qquad\cdot\dfrac{2}{(n-1)\binom{n}{k}}P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\bigg{(}\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S^{(2)}(T_{k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})+\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S^{(2)}(T^{\prime}_{n-k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+2\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S(T_{k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})+2\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S(T^{\prime}_{n-k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}nP_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\bigg{)}\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\bigg{(}\sum_{T_{k}}S^{(2)}(T_{k})P_{Y}(T_{k})+\sum_{T^{\prime}_{n-k}}S^{(2)}(T^{\prime}_{n-k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+2\sum_{T_{k}}S(T_{k})P_{Y}(T_{k})+2\sum_{T^{\prime}_{n-k}}S(T_{n-k}^{\prime})P_{Y}(T^{\prime}_{n-k})+n\bigg{)}\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\bigg{(}E_{Y}(S^{(2)}_{k})+E_{Y}(S^{(2)}_{n-k})+2E_{Y}(S_{k})+2E_{Y}(S_{n-k})+n\bigg{)}\\\
\quad\displaystyle=\frac{2}{n-1}\sum_{k=1}^{n-1}E_{Y}(S^{(2)}_{k})+\frac{4}{n-1}\sum_{k=1}^{n-1}E_{Y}(S_{k})+n\end{array}$

In particular

$E_{Y}(S_{n-1}^{(2)})=\frac{2}{n-2}\sum_{k=1}^{n-2}E_{Y}(S^{(2)}_{k})+\frac{4}{n-2}\sum_{k=1}^{n-2}E_{Y}(S_{k})+n-1$

and therefore

$\begin{array}[]{l}E_{Y}(S_{n}^{(2)})\displaystyle=\frac{n-2}{n-1}\cdot\frac{2}{n-2}\sum_{k=1}^{n-2}E_{Y}(S^{(2)}_{k})+\frac{2}{n-1}E_{Y}(S^{(2)}_{n-1})\\\
\displaystyle\quad\qquad\quad\qquad+\frac{n-2}{n-1}\cdot\frac{4}{n-2}\sum_{k=1}^{n-2}E_{Y}(S_{k})+\frac{4}{n-1}E_{Y}(S_{n-1})+\frac{n-2}{n-1}\cdot(n-1)+2\\\
\displaystyle\quad=\frac{n-2}{n-1}E_{Y}(S_{n-1}^{(2)})+\frac{2}{n-1}E_{Y}(S^{(2)}_{n-1})+\frac{4}{n-1}E_{Y}(S_{n-1})+2=\frac{n}{n-1}E_{Y}(S_{n-1}^{(2)})+8H_{n-1}-6\end{array}$

Setting $x_{n}=E_{Y}(S_{n}^{(2)})/n$, this recurrence becomes

$x_{n}=x_{n-1}+\frac{8H_{n-1}}{n}-\frac{6}{n}.$

Since $S^{(2)}$ applied to a single node is 0, $x_{1}=E_{Y}(S_{1}^{(2)})=0$,
and the solution of this recursive equation with this initial condition is

$x_{n}=\sum_{k=2}^{n}\Big{(}\frac{8H_{k-1}}{k}-\frac{6}{k}\Big{)}=8\sum_{k=1}^{n-1}\frac{H_{k}}{k+1}-6\sum_{k=2}^{n}\frac{1}{k}=4(H_{n}^{2}-H_{n}^{(2)})-6(H_{n}-1)$

from where we deduce that

$E_{Y}(S_{n}^{(2)})=nx_{n}=4n(H_{n}^{2}-H_{n}^{(2)})-6n(H_{n}-1)$

as we claimed. ∎

######  Theorem 3.

$E_{Y}(D_{n}^{(2)})=8n(n+1)(H_{n}^{2}-H_{n}^{(2)})-2n(15n+7)H_{n}+45n^{2}-n$

###### Proof.

Again, we compute $E_{Y}(D_{n}^{(2)})$ using its very definition:

$\begin{array}[]{l}E_{Y}(D_{n}^{(2)})\displaystyle=\sum_{T\in\mathcal{T}_{n}}D^{(2)}(T)\cdot
p_{Y}(T)\displaystyle=\frac{1}{2}\sum_{k=1}^{n-1}\sum_{S_{k}\subsetneq\\{1,\ldots,n\\}\atop|S_{k}|=k}\sum_{T_{k}\in\mathcal{T}(S_{k})}\sum_{T^{\prime}_{n-k}\in\mathcal{T}(S_{k}^{c})}D^{(2)}(T_{k}\widehat{\
}\,{}T^{\prime}_{n-k})\cdot p_{Y}(T_{k}\widehat{\ }\,{}T^{\prime}_{n-k})\\\
\quad\displaystyle=\frac{1}{2}\sum_{k=1}^{n-1}\binom{n}{k}\sum_{T_{k}\in\mathcal{T}_{k}}\sum_{T^{\prime}_{n-k}\in\mathcal{T}_{n-k}}\Big{(}D^{(2)}(T_{k})+D^{(2)}(T^{\prime}_{n-k})+2S(T_{k})S(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+(n-k)(S^{(2)}(T_{k})+4S(T_{k}))+k(S^{(2)}(T_{n-k}^{\prime})+4S(T_{n-k}^{\prime}))+4k(n-k))\Big{)}\cdot\dfrac{2}{(n-1)\binom{n}{k}}P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\bigg{(}\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}D^{(2)}(T_{k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})+\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}D^{(2)}(T^{\prime}_{n-k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+2\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S(T_{k})S(T^{\prime}_{n-k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})+(n-k)\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S^{(2)}(T_{k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+4(n-k)\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S(T_{k})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})+k\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S^{(2)}(T_{n-k}^{\prime})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+4k\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}S(T_{n-k}^{\prime})P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})+4\sum_{T_{k}}\sum_{T^{\prime}_{n-k}}k(n-k)P_{Y}(T_{k})P_{Y}(T^{\prime}_{n-k})\bigg{)}\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\bigg{(}\sum_{T_{k}}D^{(2)}(T_{k})P_{Y}(T_{k})+\sum_{T^{\prime}_{n-k}}D^{(2)}(T^{\prime}_{n-k})P_{Y}(T^{\prime}_{n-k})\\\
\displaystyle\quad\qquad+2\Big{(}\sum_{T_{k}}S(T_{k})P_{Y}(T_{k})\Big{)}\Big{(}\sum_{T^{\prime}_{n-k}}S(T_{n-k}^{\prime})P_{Y}(T^{\prime}_{n-k})\Big{)}+(n-k)\sum_{T_{k}}S^{(2)}(T_{k})P_{Y}(T_{k})\\\
\displaystyle\quad\qquad+4(n-k)\sum_{T_{k}}S(T_{k})P_{Y}(T_{k})+k\sum_{T^{\prime}_{n-k}}S^{(2)}(T_{n-k}^{\prime})P_{Y}(T^{\prime}_{n-k})+4k\sum_{T^{\prime}_{n-k}}S(T_{n-k}^{\prime})P_{Y}(T^{\prime}_{n-k})+4k(n-k)\bigg{)}\\\
\quad\displaystyle=\frac{1}{n-1}\sum_{k=1}^{n-1}\bigg{(}E_{Y}(D^{(2)}_{k})+E_{Y}(D^{(2)}_{n-k})+2E_{Y}(S_{k})E_{Y}(S_{n-k})+(n-k)E_{Y}(S^{(2)}_{k})\\\
\displaystyle\quad\qquad+4(n-k)E_{Y}(S_{k})+kE_{Y}(S^{(2)}_{n-k})+4kE_{Y}(S_{n-k})+4k(n-k)\bigg{)}\\\
\quad\displaystyle=\frac{2}{n-1}\sum_{k=1}^{n-1}\bigg{(}E_{Y}(D^{(2)}_{k})+E_{Y}(S_{k})E_{Y}(S_{n-k})+(n-k)E_{Y}(S^{(2)}_{k})+4(n-k)E_{Y}(S_{k})\bigg{)}+\frac{2}{3}n(n+1)\\\
\end{array}$

In particular

$\begin{array}[]{l}E_{Y}(D_{n-1}^{(2)})\displaystyle=\frac{2}{n-2}\sum_{k=1}^{n-2}\bigg{(}E_{Y}(D^{(2)}_{k})+E_{Y}(S_{k})E_{Y}(S_{n-1-k})+(n-1-k)E_{Y}(S^{(2)}_{k})\\\
\displaystyle\quad\qquad+4(n-1-k)E_{Y}(S_{k})\bigg{)}+\frac{2}{3}n(n-1)\end{array}$

and therefore

$\begin{array}[]{l}E_{Y}(D_{n}^{(2)})\displaystyle=\frac{n-2}{n-1}\cdot\frac{2}{n-2}\sum_{k=1}^{n-2}E_{Y}(D^{(2)}_{k})+\frac{2}{n-1}E_{Y}(D^{(2)}_{n-1})\\\
\displaystyle\quad\qquad+\frac{n-2}{n-1}\cdot\frac{2}{n-2}\sum_{k=1}^{n-2}E_{Y}(S_{k})E_{Y}(S_{n-1-k})+\frac{2}{n-1}\bigg{(}\sum_{k=1}^{n-1}E_{Y}(S_{k})E_{Y}(S_{n-k})-\sum_{k=1}^{n-2}E_{Y}(S_{k})E_{Y}(S_{n-1-k})\Bigg{)}\\\
\displaystyle\quad\qquad+\frac{n-2}{n-1}\cdot\frac{2}{n-2}\sum_{k=1}^{n-2}(n-1-k)E_{Y}(S^{(2)}_{k})+\frac{2}{n-1}\bigg{(}\sum_{k=1}^{n-1}(n-k)E_{Y}(S^{(2)}_{k})-\sum_{k=1}^{n-2}(n-1-k)E_{Y}(S^{(2)}_{k})\Bigg{)}\\\
\displaystyle\quad\qquad+\frac{n-2}{n-1}\cdot\frac{8}{n-2}\sum_{k=1}^{n-2}(n-1-k)E_{Y}(S_{k})+\frac{8}{n-1}\bigg{(}\sum_{k=1}^{n-1}(n-k)E_{Y}(S_{k})-\sum_{k=1}^{n-2}(n-1-k)E_{Y}(S_{k})\Bigg{)}\\\
\displaystyle\quad\qquad+\frac{n-2}{n-1}\cdot\frac{2}{3}n(n-1)+\frac{2}{3}n(n+1)-\frac{n-2}{n-1}\cdot\frac{2}{3}n(n-1)\\\\[6.45831pt]
\quad\displaystyle=\frac{n-2}{n-1}E_{Y}(D^{(2)}_{n-1})+\frac{2}{n-1}E_{Y}(D^{(2)}_{n-1})+\frac{2}{n-1}\sum_{k=1}^{n-2}E_{Y}(S_{k})(E_{Y}(S_{n-k})-E_{Y}(S_{n-k-1}))\\\
\displaystyle\quad\qquad+\frac{2}{n-1}\sum_{k=1}^{n-1}E_{Y}(S_{k}^{(2)})+\frac{8}{n-1}\sum_{k=1}^{n-1}E_{Y}(S_{k})+2n\\\
\quad\displaystyle=\frac{n}{n-1}E_{Y}(D^{(2)}_{n-1})+\frac{8}{n-1}\sum_{k=1}^{n-2}k(H_{k}-1)H_{n-k-1}+\frac{2}{n-1}\sum_{k=1}^{n-1}(4k(H_{k}^{2}-H_{k}^{(2)})-6k(H_{k}-1))\\\
\displaystyle\quad\qquad+\frac{16}{n-1}\sum_{k=1}^{n-1}k(H_{k}-1)+2n\\\
\quad\displaystyle=\frac{n}{n-1}E_{Y}(D^{(2)}_{n-1})+\frac{8}{n-1}\sum_{k=1}^{n-2}kH_{k}H_{n-k-1}-\frac{8}{n-1}\sum_{k=1}^{n-2}kH_{n-k-1}+\frac{8}{n-1}\sum_{k=1}^{n-1}k(H_{k}^{2}-H_{k}^{(2)})\\\
\displaystyle\quad\qquad+\frac{4}{n-1}\sum_{k=1}^{n-1}k(H_{k}-1)+2n\\\
\quad\displaystyle=\frac{n}{n-1}E_{Y}(D^{(2)}_{n-1})+\frac{8}{n-1}\sum_{k=1}^{n-2}kH_{k}H_{n-k-1}-\frac{8}{n-1}\sum_{k=1}^{n-2}(n-k-1)H_{k}+\frac{8}{n-1}\sum_{k=1}^{n-1}k(H_{k}^{2}-H_{k}^{(2)})\\\
\displaystyle\quad\qquad+\frac{4}{n-1}\sum_{k=1}^{n-1}kH_{k}-\frac{4}{n-1}\sum_{k=1}^{n-1}k+2n\\\
\quad\displaystyle=\frac{n}{n-1}E_{Y}(D^{(2)}_{n-1})+\frac{8}{n-1}\sum_{k=1}^{n-2}kH_{k}H_{n-k-1}-8\sum_{k=1}^{n-2}H_{k}+\frac{8}{n-1}\sum_{k=1}^{n-1}k(H_{k}^{2}-H_{k}^{(2)})\\\
\displaystyle\quad\qquad+\frac{12}{n-1}\sum_{k=1}^{n-1}kH_{k}-8H_{n-1}\\\
\quad\displaystyle=\frac{n}{n-1}E_{Y}(D^{(2)}_{n-1})+4n(H_{n}^{2}-H_{n}^{(2)}-2H_{n}+2)-8(n-1)(H_{n-1}-1)+4n(H_{n}^{2}-H_{n}^{(2)})\\\
\displaystyle\quad\qquad-2n(2H_{n}-1)+3n(2H_{n}-1)-8H_{n-1}\\\
\quad\displaystyle=\frac{n}{n-1}E_{Y}(D^{(2)}_{n-1})+8n(H_{n}^{2}-H_{n}^{(2)})-14nH_{n-1}+15n-14\end{array}$

Setting $x_{n}=E_{Y}(D_{n}^{(2)})/n$, this recurrence becomes

$x_{n}=x_{n-1}+8(H_{n}^{2}-H_{n}^{(2)})-14H_{n-1}+15-\frac{14}{n}.$

The solution of this recursive with $x_{1}=E_{Y}(D_{1}^{(2)})=0$ is

$\begin{array}[]{rl}x_{n}&\displaystyle=\sum_{k=2}^{n}\Big{(}8(H_{k}^{2}-H_{k}^{(2)})-14H_{k-1}+15-\frac{14}{k}\Big{)}\\\
&\displaystyle=8\sum_{k=1}^{n}(H_{k}^{2}-H_{k}^{(2)})-14\sum_{k=1}^{n-1}H_{k}+15(n-1)-14\sum_{k=2}^{n}\frac{1}{k}\\\
&\displaystyle=8(n+1)(H_{n+1}^{2}-H_{n+1}^{(2)})-16(n+1)(H_{n+1}-1)-14n(H_{n}-1)+15(n-1)-14(H_{n}-1)\\\
&\displaystyle=8(n+1)(H_{n}^{2}-H_{n}^{(2)})-2(15n+7)H_{n}+45n-1\end{array}$

from where we deduce that

$E_{Y}(D_{n}^{(2)})=nx_{n}=8n(n+1)(H_{n}^{2}-H_{n}^{(2)})-2n(15n+7)H_{n}+45n^{2}-n$

as we claimed. ∎