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$.


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.


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})$$

  • $\begingroup$ yes. I'm referring to the encoding in a proffer's code. sorry for the confusion. $\endgroup$ – B.Li May 18 '18 at 0:54

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}}.$$

  • $\begingroup$ I see. I added a "dumb" approach to the question. I'm not sure if it yields the same answer. $\endgroup$ – B.Li May 18 '18 at 1:13
  • $\begingroup$ @B.Li Your sum is an expression for the number of trees containing the $(1,2)$-edge, which then must be subtracted from $n^{n-3}$ to get the number of trees omitting that edge, right? $\endgroup$ – bof May 18 '18 at 1:27
  • $\begingroup$ right, forgot that part, silly mistake. $\endgroup$ – B.Li May 18 '18 at 1:28
  • $\begingroup$ Your approach looks fine to me. And there's nothing "dumb" about it; solving the same counting problem two different ways is how we prove combinatorial identities. $\endgroup$ – bof May 18 '18 at 1:33
  • $\begingroup$ Your argument proves the identity $$\sum_{k=0}^{n-2}\binom{n-2}k(k+1)^{k-1}(n-1-k)^{n-3-k}=2n^{n-3}.$$ $\endgroup$ – bof May 18 '18 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.