How many labeled n-trees are there that do not contain a $(1,2)$ edge?
Clarification: The problem is referring to the encodings of a prufer's code. $(1,2)$ edge is referring to the edge that joins the vertex labeled $1$ and $2$.
Thoughts:
I'm not exactly sure how to do this problem. I know there are $n^{n-2}$ labeled trees, each with $n-1$ edges. I also know there are two cases, 1) being when either $1$ or $2$ appears as a leaf, 2) when they do not.
In case 1), we can consider a tree with $n-1$ vertices, without $1$ as a semantic encoding. Find the encoding of a $(n-1)$ tree, add $1$ to $2$ as a leaf. There's $(n-1)^{n-3}$ labeled trees on $(n-1)$ vertices, switch the position of $1$ and $2$ and we have $2(n-1)^{n-3}$ possibilities.
However, if neither $1$ or $2$ appear as a leaf, then I'm lost. I'm not sure how to better approach this problem without these two cases.
EDIT:
New approach (not sure about correctness):
If $1$ and $2$ form an edge, then the removal of that edge will separate the tree into two components, each with at least one vertex. Each component is then it's own tree. So take a iterative approach:
For a set of vertices $\{1,2,...,n\}$, divide it into two sets, with $1$ and $2$ in separate sets. Of the remaining $n-2$ vertices, pick $k$ elements to be with vertex $1$, and let the remaining be with vertex $2$. Let each set form its own tree. Hence we have, for some $0\le k \le n-2$:
1) Put $1$ into set $A$, $2$ into set $B$, choose $k$ additional elements to be in $A$. Hence $\binom{n-2}{k}$ ways.
2) For set $A$, there are $(k+1)^{k-1}$ ways to form a tree.
3) For set $B$, there are $(n-k-1)^{n-k-3}$ ways to form a tree.
Summing it all up, we have:
$$(n)^{n-2} - \sum_{k=0}^{n-2} \binom{n-2}{k} ((k+1)^{k-1}(n-k-1)^{n-k-3})$$
We suppose $n\ge2.$ A tree on the vertex set $\{1,2,\dots,n\}$ contains $n-1$ of the $n(n-1)/2$ possible edges. The probability that a random tree contains a given edge (say the edge $\{1,2\}$) is $$\frac{n-1}{n(n-1)/2}=\frac2n.$$ The probability that a random tree omits the edge $\{1,2\}$ is $$1-\frac2n=\frac{n-2}n.$$ As there are $n^{n-2}$ trees all told, the number of trees omitting the edge $\{1,2\}$ is $$\frac{n-2}n\cdot n^{n-2}=\boxed{(n-2)n^{n-3}}.$$
Here is the same argument presented in the style of counting rather than probability.
Let $K_n$ be the complete graph on the vertex set $V=[n]=\{1,2,\dots,n\}.$
Then $a(n)=n^{n-2}$ is the number of spanning trees in $K_n.$
For $e\in V$ let $b(n)$ be the number of spanning trees that contain the edge $e;$ clearly this number does not depend on the choice of $e.$
Let's count the number $N$ of pairs $(T,e),$ where $T$ is a spanning tree of $K_n$ and $e$ is an edge of $T,$ in two different ways.
Counting by trees: each tree has $n-1$ edges, so $$N=a(n)(n-1).$$
Counting by edges: there are $\binom n2$ edges, each edge is in $b(n)$ spanning trees, so $$N=\binom n2b(n).$$ From these two equations for $N,$ $$\frac{b(n)}{a(n)}=\frac{n-1}{\binom n2}=\frac2n,$$ so $$a(n)-b(n)=\left(1-\frac2n\right)a(n)=\boxed{(n-2)n^{n-3}}.$$