Counting functional graphs with no 1 or 2-cycles. I can easily work out that the number of functional graphs (directed graphs in which all vertices have out-degree one) of size $n$ is $n^n$ and the number of functional graphs without one-cycles is ${(n-1)}^n$. Is there an straight-forward way to work out the number of functional graphs of size $n$ which have no 1-cycles (fixed points) or 2-cycles? 
 A: The   problem  of   restricted   endofunctions  is   a  classic   from
combinatorics, gives rise  to some fascinating deep math  and has been
studied in considerable detail.
Labelled trees are given by
$$\mathcal{T} = 
\mathcal{Z} \times \mathfrak{P}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$
The species of endofunctions is then given by
$$\mathcal{Q} = \mathfrak{P}(\mathfrak{C}(\mathcal{T})).$$
Translating to generating functions we get
$$Q(z) = \exp \log \frac{1}{1-T(z)} =
\frac{1}{1-T(z)}.$$
In this particular case we have that there are no 
fixed points or two-cycles so we get the species
$$\mathcal{Q} = 
\mathfrak{P}(\mathfrak{C}_{\ge 3}(\mathcal{T})).$$
This yields the generating function
$$Q(z) = \exp
\left(-T(z)-T(z)^2/2\right)
\frac{1}{1-T(z)}.$$
Extracting coefficients via poor man's Lagrange inversion we have
$$Q_n
= n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\exp\left(-T(z)-T(z)^2/2\right)
\frac{1}{1-T(z)} dz.$$
Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and 
$dz = \exp(-w) - w\exp(-w)$ 
to get
$$n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+1))}{w^{n+1}} 
\frac{\exp(-w-w^2/2)}{1-w} (\exp(-w) - w\exp(-w)) dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(wn)}{w^{n+1}} 
\frac{\exp(-w-w^2/2)}{1-w} (1 - w) dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n-1)-w^2/2)}{w^{n+1}} dw.$$
Extracting coefficients from this we obtain the closed formula
$$n! \sum_{q=0}^{\lfloor n/2 \rfloor}
\frac{(-1)^q}{2^q \times q!}
\frac{(n-1)^{n-2q}}{(n-2q)!}.$$
This yields the following sequence  which we have started at index one
to make things clear:
$$0, 0, 2, 30, 444, 7360, 138690, 2954364, 70469000, 1864204416, 
\\ 54224221050, 1721080885480, 
59217131089908, 2195990208122880,\ldots$$
This  is   OEIS  A134362  where   we  find
confirmation of the above analysis as well as many useful links.
Finally note that this 
MSE link  I and this 
MSE link II 
may prove useful reading.
