number of acyclic graphs on $n$ vertices having $n-m$ edges it's been several days I'm completely stuck on an exercise in Bollobas' Modern graph theory : chapter VIII, exercise 64 page 290. It asks to prove that the number $t(n,m)$ of acyclic graphs on $n$ vertices and $n-m$ edges is 
$$t(n,m)=\frac{1}{m!}\sum_{j=0}^m \frac{(-1)^j}{2^j}{m \choose j}{n-1 \choose m+j-1}n^{n-m-j}(m+j)!.$$
At first sight I though that an application of inclusion-exclusion would do it, but it led nowhere. I can't see how to apply Prüfer codes either.
How could I do this ? Also, is there any closed form for this ? Applied to $m=1,2$ yields nice closed formulas. I suspect that some variations on Abel's identity would yield nice results, but no :(
thanks for helping !
 A: Here is some  additional computational material on  this problem which
may assist the  reader in understanding the excellent  answer that was
linked to  in the  comments. Start by  observing that  acyclic labeled
graphs are  sets of labeled trees  and with trees on  $n$ nodes having
$n-1$ edges when  we take $m$ such trees we  indeed obtain $n-m$ edges
(with $n$ the  total count of nodes  in the set). So the  value $m$ in
the number of edges does in fact give the number of components. 
Recall the species of rooted trees $\mathcal{T}$ with species equation
$$\mathcal{T} = \mathcal{Z} \mathfrak{P}(\mathcal{T}).$$
This gives the functional equation
$$T(z) = z \exp T(z).$$
We have Cayley's result that
$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$
We require  unrooted trees  however which have  the EGF  ($n$ possible
slots for the root)
$$U(z) = \sum_{n\ge 1} n^{n-2} \frac{z^n}{n!}.$$
Our species then becomes
$$\mathfrak{P}_{=m}(\mathcal{U})$$
whith EGF $$\frac{1}{m!} U(z)^m.$$
We get from elementary considerations that $z U'(z) = T(z).$ 
To integrate $T(z)/z$ observe that the functional equation yields
$T'(z) = T(z)/z + T(z) T'(z)$ and $T(z) T'(z) = \frac{1}{2} (T(z)^2)'.$
We thus have
$$U(z) = T(z) - \frac{1}{2} T(z)^2.$$
This also  happens to have the  right constant, which is  zero. We may
now prepare to extract coefficients, starting from
$$\frac{n!}{m!} [z^n] U(z)^m =
\frac{n!}{m!}
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n+1}} \left(T(z) - \frac{1}{2} T(z)^2\right)^m
\; dz.$$
With the  substitution $w=T(z)$ the  functional equation yields  $z= w
\exp(-w)$ and $dz = \exp(-w) (1-w) \; dw.$ Note also that with $T(z) =
z + \cdots$ the image contour in $w$ is deformable to a circle, making
one turn. We find
$$\frac{n!}{m!}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{\exp((n+1)w)}{w^{n+1}} \left(w - \frac{1}{2} w^2\right)^m
\exp(-w) (1-w)
\; dw
\\ = \frac{n!}{m!}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{\exp(nw)}{w^{n+1}} \left(w - \frac{1}{2} w^2\right)^m
(1-w)
\; dw
\\ = \frac{n!}{m!}
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{\exp(nw)}{w^{n-m+1}} \left(1 - \frac{1}{2} w\right)^m
(1-w)\; dw.$$
Extracting coefficients here will produce two pieces, which are
$$\frac{n!}{m!}
\sum_{j=0}^{n-m} \frac{n^{n-m-j}}{(n-m-j)!} 
{m\choose j} (-1)^j \frac{1}{2^j}
\\ - \frac{n!}{m!}
\sum_{j=0}^{n-m-1} \frac{n^{n-m-1-j}}{(n-m-1-j)!}
{m\choose j} (-1)^j \frac{1}{2^j}.$$
With $j\le n-m-1$ we find
$$\frac{n^{n-m-j}}{(n-m-j)!} 
- \frac{n^{n-m-1-j}}{(n-m-1-j)!} 
= \frac{n^{n-m-j}}{(n-m-j)!} 
\left(1 - \frac{n-m-j}{n}\right)
\\ = \frac{n^{n-m-j}}{(n-m-j)!} 
\frac{m+j}{n}.$$
Collecting everything we obtain
$$\frac{n!}{m!} {m\choose n-m} (-1)^{n-m} \frac{1}{2^{n-m}}
\\ + \frac{n!}{m!} \sum_{j=0}^{n-m-1}
\frac{n^{n-m-j}}{(n-m-j)!} {m\choose j} (-1)^j \frac{1}{2^j}
\frac{m+j}{n}.$$
The sum simplifies as follows:
$$\frac{(n-1)!}{m!} \sum_{j=0}^{n-m-1}
\frac{n^{n-m-j}}{(n-m-j)! \times (m+j-1)!} 
{m\choose j} (-1)^j \frac{1}{2^j} (m+j)! 
\\ = \frac{1}{m!} \sum_{j=0}^{n-m-1}
{n-1\choose m+j-1}
{m\choose j} n^{n-m-j} (-1)^j \frac{1}{2^j} (m+j)!.$$
To conclude we note that when we set $j=n-m$ in the sum
we get
$$\frac{1}{m!} {n-1\choose n-1} {m\choose n-m} 
(-1)^{n-m} \frac{1}{2^{n-m}} n!$$
which is  precisely the term in  front, which therefore may  be merged
into the sum, for an end result of
$$\frac{1}{m!} \sum_{j=0}^{n-m} \frac{(-1)^j}{2^j}
{n-1\choose m+j-1}
{m\choose j} n^{n-m-j} (m+j)!$$
as claimed.
A: I got a combinatorial proof using the principle of inclusion-exclusion, I'll still give it even if I already accepted Marko's answer. 
First, $m! t(n,m)$ is the number of labelled forests on $n$ vertices, with $m$ ordered connected components. We want to show that
\begin{equation}
\label{eq}
m! t(n,m) = \sum_{j=0}^m (-1)^j {m \choose j} \frac{1}{2^j}{n-1 \choose m+j-1}(m+j)! n^{n-m-j}.
\end{equation}
If $h$ is an integer we note $[h] = \{1, ..., h\}$. The integer $n$ is fixed for the rest of the proof.
Let $F(k)$ be the set of trees with vertex set $[n+1]$ such that the degree of vertex $n+1$ is $k$. A classical result due to Clarke is that 
\begin{equation}\tag{1}
|F(k)| = {n-1 \choose k-1}n^{n-k-1}.
\end{equation}
This can be seen in several basic ways, see  the book Counting labeled trees by Moon for details. From now on, vertex $n+1$ will be called $\omega$.  We define $G(k)$ as the set of elements of $F(k)$ in which the $k$ edges adjacent to $\omega$ have been ordered, thus $|G(k)|=k!|F(k)|$. Let $t \in G(k)$ and $i \in [k]$. The $i$-th edge adjacent to $\omega$ leads to a vertex called $v_i(t)$ and the branch starting at $v_i$ is named $B_i(t)$. Two elements $t,t'$ in $G(m)$ are called \emph{equivalent} if $(B_i(t))_{i \in [m]}=(B_i(t'))_{i \in [m]}$, meaning that when we erase $\omega$ and its incident edges from $t$ or $t'$, we get the same ordered forest with $m$ elements ; then, $m!t(n,m)$ is the number of equivalence classes in $G(m)$.
We say that a tree $t \in G(m)$ has property $\mathscr{P}_i$ if $v_i(t)$ is not the smallest vertex in $B_i(t)$. In every equivalence class, there is exactly one representative having none of the properties $\mathscr{P}_1,..., \mathscr{P}_m$. Thus, if we set $E_i = \{t \in G(m) : t \text{ has } \mathscr{P}_i \}$, then $m!t(n,m) = |G(m) \setminus E_1 \cup ... \cup E_m |$. The inclusion-exclusion principle thus yields
\begin{align}t(n,m) &= |E| + \sum_{j=1}^m (-1)^j \sum_{i_1 < ... < i_j} |E_{i_1} \cap ... \cap E_{i_j}| \nonumber \\
&= |E|+ \sum_{j=1}^n (-1)^j {m \choose j} |E_1 \cap ... \cap E_j| \label{PIE}
\end{align}
where the second line comes from the fact that $|E_{i_1} \cap ... \cap E_{i_k}|$ does only depend on $k$. 
Lemma : 
Fix $j \in [m]$ and define $\alpha_j := |E_1 \cap ... \cap E_j|$. Then, $2^j \alpha_j = |G(m+j)|$. 
Using $|G(m+j)|=(m+j)!|F(m+j)|$ and (1), we get 
$$\alpha_j = \frac{1}{2^j}(m+j)!{n-1 \choose m+j-1}n^{n-m-j}$$
hence closing the proof. 
Proof of the Lemma. 
Set $X(j):= \{-1, +1\}^{[j]} \times E_1 \cap ... \cap E_j$, so that $|X(j)|=2^j \alpha_j$. We build a bijection $\phi : X(j) \to G(m+j)$. Take $(f,t) \in X(j)$. For every $i \in [j]$ we use the following procedure. Let $u_i(t)$ be the smallest vertex in $B_i(t)$. We know that $t \in E_i$, so $u_i(t)<v_i(t)$. As $B_i(t)$ is a tree, it contains a unique path from $v_i(t)$ to $u_i(t)$ ; we note $w_i(t)$ the first vertex visited by this path when starting from $u_i(t)$. We build $s = \phi(f,t)$ as follows : for every $i \in [j]$, remove the edge $(u_i(t), w_i(t))$ and add the edge $(\omega, w_i(t))$. Now, if $f(i)=1$, label this edge $2i$ and relabel the edge $(\omega, u_i(t))$ with label $2i-1$. Else, $f(i)=-1$ ; then, label the edge $(\omega, w_i(t))$ with label $2i-1$ and relabel the edge $(\omega, u_i(t))$ with label $2i$. We get an element $s \in G(m,j)$. 
The inverse bijection $\psi$ works as follows. Pick an element $s \in G(m+j)$. For every $i \in [j]$, consider the two disjoint trees $B_{2i-1}(s), B_{2i}(s)$. Exactly one of them contains the smallest element $x_i(s)$ of the union of their vertices. 


*

*If $x_i(s) \in B_{2i}(s)$, erase the edge $(\omega, u_{2i}(s))$, add the edge $(u_{2i-1}(s), u_{2i}(s))$ and relabel the edge $(\omega, u_{2i-1}(s))$ with label $i$. Set $f(i) = +1$. 

*Else, $x_i(s) \in B_{2i-1}(s)$ ; then, erase the edge $(\omega, u_{2i-1}(s))$, add the edge $(u_{2i-1}(s), u_{2i}(s))$ and relabel the edge $(\omega, u_{2i}(s))$ with label $i$. Set $f(i) = -1$. 
When this has been done for every $i \in [j]$, we get a couple $(f,t) = \psi(s)$ with $f : [j] \to \{-1, +1\}$ and a tree $t \in G(m)$ such that for every $i \in [j]$, the smallest element in $B_i(t)$ is $x_i(s)$ and is strictly smaller than $u_i(t)$, thus $t$ has property $\mathscr{P}_i$, hence $t \in E_1 \cap ... \cap E_j$. By construction, $\psi$ is an inverse for $\phi$, which is thus a bijection. This ends the proof of the Lemma. 
