In a full binary tree of depth $d$, what is the number of pairs of vertices at distance $t$ from each other? I can come up with a dynamic-programming-type program to compute this number, but I am wondering if a nice closed form formula is known.
By "full" I mean a binary tree where every vertex is within distance $d$ of the root, and the $d$-th level is completely filled with leaves. There are $2^{d+1} - 1$ total nodes.
 A: Here's an attempt. This turned out to be quite messy though.
If $d$ is the depth of the tree and $t$ is even and smaller than $d$, the number of pairs $f(d)$ at distance $d$ is, I believe:
$$f(d) = \frac{1}{4} ( (t+3)2^d+3 \cdot 2^d 2^{t/2}- (t + 3)2^t )$$
Let's take a breath and see why.  Of course any confirmation/opposition will be welcome.  
Call $r$ the root of the tree $T$.
Denote by $R(d)$ the number of nodes at distance $t$ from $r$, and by $C(d)$ the number of pairs at distance $t$ that have $r$ on their shortest path (i.e. the path crosses through $r$ but does not end in $r$.
Then 
$$f(d) = 2f(d - 1) + R(d) + C(d)$$ 
When $d \geq t$, it is straightforward to show that $R(d) = 2^t$.
As for $C(d)$, for a vertex at depth $i$ in the "left" subtree, all vertices at depth $t - i$ in the "right" subtree are at distance $t$.  There are $2^{i - 1}$ such choices left, and $2^{t - i - 1}$ choices right, and $C(d)$ is given by 
$$\sum_{i = 1}^{t - 1}2^{i - 1}2^{t - i - 1} = (t - 1)2^{t - 2}$$
So 
$$f(d) = 2f(d - 1) + 2^t + (t - 1)2^{t - 2}$$ 
If we knew $f(t)$ we could solve the recurrence.  It turns out that $f(t) = \frac{3}{4}(2^{3t/2})$. Plugging stuff into Wolfram, we get the closed form from above. 
Now you may ask "why is $f(t) = \frac{3}{4}(2^{3t/2})$" ?
I'll leave that as an exercise :)
But here's the idea.  If $d < t/2, f(d) = 0$.
Recalling that $t$ is even, you can check that $f(t/2) = C(t/2) = 2^{t - 2}$ and 
for $\delta < t/2$, 
$$f(t/2 + \delta) = 2f(t/2 + \delta - 1) + C(t/2 + \delta) 
=2f(t/2 + \delta - 1) + (2\delta + 1)2^{t - 2}$$
the idea for $C(t/2 + \delta)$ being to apply the same summation as above, but restricted to the allowable $i$'s given $d$.
From this, you can find $f(t - 1)$ using wolfram, and compute $f(t) = 2f(t - 1) + 2^t + (t - 1)2^{t - 2}$.  This gives $\frac{3}{4}(2^{3t/2})$.  The beauty of this expression hints that it should be right :)
The non beauty of $f(d)$ in general leaves doubt though.
And for odd $t$, I guess you could apply the same ideas.  I think only the $C(d)$ for $d < t$ will change.
A: Observe that each interior vertex (other than the root) of a binary tree is the central vertex of three different paths of length two, whereas the root is the central vertex of one such path. Furthermore, there are exactly $2^d-2$ interior vertices (other than the root) in a full binary tree. Writing $p(d,2)$ for the number of paths of length two in a full binary tree of depth $d$:
$$p(d,2)=3(2^d-2)+1=3\cdot 2^d-5.$$
Using a similar direct counting approach for $t=2k$, I have found the following formulae for $p(d,2k)$, the number of pairs of vertices at distance exactly $2k$ in a full binary tree of depth $d$.


*

*if $d<k$, then $p(d,2k)=0$

*if $k\le d<2k$, then $p(d,2k)=2^{2k-2}\left(3\cdot 2^{d-k+1}-2(d-k)-5\right)$

*if $d\ge 2k$, then $p(d,2k)=2^{2k-2}\left(3\cdot 2^{d-k+1}-2k-3\right)$


These appear to give the correct counts for small values of $d$ and $k$. In particular, for $t=2$ ($k=1$) and $d> 1$, the expression above becomes
$$p(d,2)=2^{2-2}\left(3\cdot 2^{d-1+1}-2-3\right)=3\cdot 2^d-5.$$
If you have any exact counts for larger values of $t$, perhaps you could check the validity of these formulae.
