Problem 1676

Let $A(n)$ be the sum of the number of cycles over all bijective functions from $N$ to $N$. We first prove:

Lemma: $A(n) = n! \sum_{i=1}^{n} \frac{1}{i}$.

Proof: Note that among all bijective functions from $N$ to $N$,

1. Those satisfying $f(n) = n$ number $(n-1)!$ in total, and the total number of cycles of these $f$ is $A(n-1) + (n-1)!$, where the $(n-1)!$ corresponds to the new $\{n\}$-cycle.
2. For any $m \in \{1, 2, \dots, n-1\}$, the functions satisfying $f(n) = m$ number $(n-1)!$ in total, and the total number of cycles of these $f$ is $A(n-1)$.

Hence we obtain the recurrence:
$$\begin{aligned} A(n) &= A(n-1) + (n-1)! + (n-1)A(n-1) = nA(n-1) + (n-1)! \\ \Rightarrow \frac{A(n)}{n!} &= \frac{A(n-1)}{(n-1)!} + \frac{1}{n} \\ \Rightarrow \frac{A(n)}{n!} &= \frac{A(1)}{1!} + \sum_{i=2}^{n} \frac{1}{i} \end{aligned}$$

And clearly $A(1) = 1$, so $A(n) = n! \sum_{i=1}^{n} \frac{1}{i}$.

Returning to the original problem. It is easy to see that when $k \ge 3$, we have $A(n) \le n! \times k$. At this point, if the number of functions whose number of cycles is not less than $\frac{n!}{2}$ is $\ge 2k$, then $A(n) > \frac{n!}{2} \times 2k = n! \times k^1$, a contradiction! Hence the original proposition holds for $k \ge 3$. It is easy to verify that the proposition also holds for $k=1,2$.