I want to count number of trees with vertex set $V$ = {1, 2, 3,…, 10} that have $\\$
tree $T=$ < {1, 2, 3}, {{1, 2}, {2, 3}} > (looks like 1 — 2 — 3) as a subgraph.
So if I think correctly, I need to find number of labeled trees with n vertices and 2 fixed edges.
By Cayley's formula there are $n^{n-2}$ trees with n vertices.
My take is that tree -> prufer code algorithm is finding smallest leaf, appending sequence with parent of this leaf and removing this leaf and edge connected with it. We will have two slots at our prufer sequence occupied by either (2,2), (3,2), (1, 2). One of these subsequences can start on $n-1$ slots. Other slots can be used by any of n vertices. So we get $3 \cdot (n-1) \cdot n^{n-4}$. But it is completely wrong. I tried to use some of proofs of similiar problems with one fixed edge, but I have problem with understanding these it seems…
Best Answer
Imagine that the tree $T$ (
3---2---1) is contracted to a single vertex labelled $0$. There are $8^6$ labelled trees on the vertex set $\{0,4,5,6,7,8,9,10\}$. For $k=1,\ldots,7$, in how many of these trees does vertex $0$ have degree $k$?Vertex $0$ shows up $k-1$ times in the Prüfer code of such a tree, and each of these Prüfer codes has $6$ slots, so there are $\binom6{k-1}$ ways to place the $k-1$ zeroes in the code. There are then $7$ choices for each of the remaining $6-(k-1)=7-k$ slots, so there are altogether $\binom6{k-1}7^{7-k}$ such trees.
Each of these corresponds to more than one tree on the vertex set $V$ that contains the tree $T$. Specifically, if vertex $0$ has degree $k$ in one of these trees, each of edges leaving it can be attached to any of the three vertices $1,2$, and $3$ when we expand vertex $0$ to $T$, so the tree expands to $3^k$ different trees on the vertex set $V$.
Summing over $k=1,\ldots,7$, we find that there are altogether
$$\begin{align*} \sum_{k=1}^73^k\binom6{k-1}7^{7-k}&=\sum_{k=0}^6\binom6k3^{k+1}7^{6-k}\\ &=3\sum_{k=0}^6\binom6k3^k7^{6-k}\\ &=3(3+7)^6\\ &=3,000,000 \end{align*}$$
trees on the vertex set $V$ that contain $T$. (The penultimate step uses the binomial theorem.)
This analysis generalizes easily to a formula for the number of labelled trees on $n$ vertices that contain a specific subtree $T$ with $m$ vertices.