# The number of permutations with a special condition

Suppose we are considering $S_n$. For any permutation, let $h$ be the number of derangement and $N$ be the number of cycles with length no less than 2.

I'm interested in the number of permutations such that $h-N=k$. I do not need an exact value. An upper bound depending on $n$ and $k$ for large $n$ is enough. I also have a guess of the order of the upper bound: $$(n/\sqrt{2k})^{2k}$$ I come up with this guess due to the fact that if $h-N=k$, $h$ must be smaller or equal to $2k$. In the case $h=2k$, we have $$\frac{n(n-1)\cdots(n-2k+1)}{(2k)!!}$$ permutations which is roughly the above order. I also guess this case should dominate other cases when $k+1\leq h<2k$, which results in my conjecture.

• What do you mean by a derangement? By the "number of cycles no less than 2" do you mean "number of cycles of length no less than 2"? Sep 19, 2018 at 22:21
• SORRY! I have updated it. For the number of derangement, I mean the number of points that is changed, which is the complement of fixed points. Sep 20, 2018 at 2:50
• Yeah... but it is hardly useful in my case. What I'm really looking for is how that quantity can be upper bounded in a simpler form (just like my guess) where the dependance on $n$ and $k$ can be read easily. Sep 20, 2018 at 2:59

Notice that the number of cycles of length 1 in such a permutation equals $n-h$. Hence, the total number of cycles is $N + (n - h) = n - k$. It follows that the number of such permutations equals the unsigned Stirling number of first kind $c(n,n-k)$. For asymptotic, see the corresponding section in Wikipedia.
P.S. The same answer can be obtained from Ira Gessel's answer to the previous question by setting $c=f$ and taking the coefficient of $f^{n-k}\frac{x^n}{n!}$ in the corresponding generating fuction.
• Thank you! Can $c(n,n-k)$ be upper bounded by $(n/\sqrt{2k})^{2k}$ for $1\leq k\leq n/2$? This seems to be valid for $k=1,2,3$. Sep 20, 2018 at 3:37
• @neverevernever: No, $85 = c(6,6-2) > (6/\sqrt{4})^4 = 81$. Sep 20, 2018 at 4:02
• I see. But I'm wondering what is the scaling of $n$ and $k$ right, by which I mean does there exists constants $a,b$ independent of $n,k$ such that the upper bound is $a(bn/\sqrt{2k})^{2k}$ for all $n$ large enough and all $1\leq k\leq n/2$? Sep 20, 2018 at 13:38
• Wikipedia gives asymptotic $\frac{(n-k)^{2k}}{2^k k!}$ as $n-k$ grows (which is the case when $k<n/2$ and $n$ grows). Sep 20, 2018 at 14:09