2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Mar 7, 2022 at 13:13
  • $\begingroup$ Sorry, I meant to exclude functions with fixed points, but forgot to do so. $\endgroup$ Commented Mar 7, 2022 at 13:28

1 Answer 1

3
$\begingroup$

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}$$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Mar 8, 2022 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.