How many spanning trees (undirected) are there with exactly k leaf?

Question

It occurred to me that in order to find how many of those are there, for every $k$ it's a bit different way of thinking, for example:

for $k$ = 3 the answer is:

$\binom{n}{3}(n-3)\frac{(n-2)!}{2!}$

for $k$ = 4 it gets a bit more complicated:

$\binom{n}{4}[(n-4)\frac{(n-2)!}{3!}+\binom{n-4}{2}\frac{(n-2)!}{2!*2!}]$ (which, to be honest, i'm not sure why)

of course I can make it a simple cayley's problem:

How many words with $n-2$ letters from $n$ possible letters are there, when there are exactly $k$ letters that are not in the word? but that won't give me the answer i wrote above.

Answer 1

The answer you want, as you mention in comments is given by the number of lists of length $n-2$ which have exactly $n-k$ different letters inside the list. This is because every vertex in the tree appears in its code expect for the leaves, the leaves never appear.We shall first select the $n-k$ etters we want to appear in $\binom{n}{k}$ ways. Then we shall partition the spots in which the letters appear in the code in $n-k$ parts in ${n-2 \brace {n-k}}$ ways, and finally we shall multiply by $(n-k)!$ to select which part of the partition gets which number.

So the final answer is $\binom{n}{k}{{n-2}\brace{n-k}}(n-k)!$

Where $n\brace k$ is the stirling number of the second kind

Answer 2

I found it. Using the Inclusion - Exclusion principle,

$W(0) = n-k^{n-2}$

$W(r) = \binom{n-k}{r}(n-k-r)^{n-2}$

So, we choose which letters won't appear: $\binom{n}{k}$ and then apply the principle. the answer comes out:

$\binom{n}{k}\sum_{r=0}^{n-k}(-1)^{r}\binom{n-k}{r}(n-k-r)^{n-2}$