combinatorics - 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?

Answer

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.