I need a (numerically) evaluable function for the number $N_{n,k}$ of endofunctions $f: [n] \rightarrow [n]$ without fixed points that have exactly $k$ twocycles, where $[n] := \{1,\dotsc,n\}$. In formal terms, what is $$N_{n,k} := \lvert \{ f:[n]\rightarrow [n] \mid \forall a: f(a) \neq a \land \lvert\{ a \in [n] \mid f^2(a) = a\}\rvert = 2k\ \}\rvert? $$ I have found a few sources on this, but have trouble to transfer the results to this specific question. An explicit formula would be greatly appreciated, while a proof or indication of a proof would be as well, though less importantly so.

1$\begingroup$ With the formal definition you wrote it looks like you're counting fixed points as half of 2cycles, is that indeed what you want? $\endgroup$– Antoine LabelleCommented Mar 7, 2022 at 13:13

$\begingroup$ Sorry, I meant to exclude functions with fixed points, but forgot to do so. $\endgroup$– Sebastian K.Commented Mar 7, 2022 at 13:28
1 Answer
First choose your 2cycles, for a factor of $\binom{n}{2k}(2k1)!!$. (Note that we require the convention that $(1)!! = 1$). Then count functions $g: [n2k] \to [n]$ with no fixed points or 2cycles. There are $\binom{n2k}{2j}(2j1)!! (n1)^{n2k2j}$ functions with no fixed points and at least $j$ 2cycles, so an inclusionexclusion gets $$\binom{n}{2k}(2k1)!! \sum_{j \ge 0} (1)^j \binom{n2k}{2j}(2j1)!! (n1)^{n2k2j}$$
Alternatively we can just start the whole thing as an inclusionexclusion from $j = k$, but then the Möbius function adds a binomial coefficient:
$$\sum_{j \ge k} (1)^{jk} \binom{j}{k} \binom{n}{2j}(2j1)!! (n1)^{n2j}$$

$\begingroup$ Thank you! I expected more elaborate theory to be required, but the inclusionexclusion principle really does the job (should have remembered that one). I can ensure that the formula does not contain any typos, as it fits perfectly to numerical results. I am happy to provide a detailed explanation of the formula if someone should prefer that, but will of course mark the answer as sufficient. $\endgroup$ Commented Mar 8, 2022 at 16:04