# Number of endofunctions in [n] without fixed points with exactly k two-cycles

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$$ two-cycles, 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.

• With the formal definition you wrote it looks like you're counting fixed points as half of 2-cycles, is that indeed what you want? Commented Mar 7, 2022 at 13:13
• Sorry, I meant to exclude functions with fixed points, but forgot to do so. Commented Mar 7, 2022 at 13:28

First choose your 2-cycles, for a factor of $$\binom{n}{2k}(2k-1)!!$$. (Note that we require the convention that $$(-1)!! = 1$$). Then count functions $$g: [n-2k] \to [n]$$ with no fixed points or 2-cycles. There are $$\binom{n-2k}{2j}(2j-1)!! (n-1)^{n-2k-2j}$$ functions with no fixed points and at least $$j$$ 2-cycles, so an inclusion-exclusion gets $$\binom{n}{2k}(2k-1)!! \sum_{j \ge 0} (-1)^j \binom{n-2k}{2j}(2j-1)!! (n-1)^{n-2k-2j}$$

Alternatively we can just start the whole thing as an inclusion-exclusion from $$j = k$$, but then the Möbius function adds a binomial coefficient:

$$\sum_{j \ge k} (-1)^{j-k} \binom{j}{k} \binom{n}{2j}(2j-1)!! (n-1)^{n-2j}$$

• Thank you! I expected more elaborate theory to be required, but the inclusion-exclusion 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. Commented Mar 8, 2022 at 16:04