Number of spanning trees with $2n$ vertex where exactly $n$ of them are leafs

77 Views Asked by At

I want to find the number of spanning trees with $2n$ vertex where exactly $n$ of them are leafs.

What I did: Lets convert this problem into Prüfer sequence. If we have $n$ vertex in the tree then the Prüfer word contains $n-2$ letters. If a vertex has rank $d$ then this vertex is shown in the Prüfer word exactly $d-1$ times. With this information we want to find the number of Prüfer words that contain $2n-2$ letters over alphabet of $n$ letters. There are ${2n \choose n}$ possibilities to choose the $n$ vertex that are leafs. Those letters will no the shown in the Prüfer word. The other $n$ letters have to be shown. So let's choose $n$ places from $2n-2$ where those letters are going to be. For that we have ${2n-2 \choose n}$ possibilities. Let's put those $n$ letters in those $n$ places with $n!$ possibilities. Now for the other $n-2$ places that are left we can put whatever letter from those $n$ letters. For each place we have $n$ letters we could choose to put and we have $n-2$ places so the number of possibilities is $n^{n-2}$. In total we get:

$$ {2n\choose n}\cdot {2n-2 \choose n}\cdot n!\cdot n^{n-2} $$

Is it corrent? if not, do I need to use the Inclusion–exclusion principle to solve it?

2

There are 2 best solutions below

1
On BEST ANSWER

Unfortunately, your method leads to double counting. When $n=6$, your formula is $\binom{6}3\binom{4}3\cdot 3!\cdot 3=1440,$ but the actual number of valid trees is $\binom{6}3\cdot \binom{4}2\cdot 3!=720$. The problem is you are singling out $n$ special positions in the Prüfer sequence when you multiply by $\binom{2n-2}n n!$, but there may be other selections of $n$ positions whose entries are all different which would lead to the same sequence.

Indeed, inclusion exclusion is the way to go. First, select the $\binom{2n}n$ leaves, as you did. Then, among all the $n^{2n-2}$ sequences where those $n$ entries do not appear, subtract the $\binom{n-2}1(n-1)^{2n-2}$ sequences where one of the non-leaves does not appear. Next, add back in the doubly subtracted sequences where two of the non-leaves are missing, etc.

0
On

By way of an observation: we can encapsulate PIE by using Stirling numbers of the second kind. We then get by inspection the closed form

$$\bbox[5px,border:2px solid #00A000]{ {2n\choose n} {2n-2\brace n} n!.}$$

Choose the $n$ nodes to appear in the Prüfer code (the $n$ leaves do not appear) and partition the slots in the code into $n$ non-empty sets, one for each node, giving the slots where it appears.