1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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"? $\endgroup$ Sep 19, 2018 at 22:21
  • $\begingroup$ 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. $\endgroup$ Sep 20, 2018 at 2:50
  • $\begingroup$ 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. $\endgroup$ Sep 20, 2018 at 2:59

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Sep 20, 2018 at 3:37
  • 1
    $\begingroup$ @neverevernever: No, $85 = c(6,6-2) > (6/\sqrt{4})^4 = 81$. $\endgroup$ Sep 20, 2018 at 4:02
  • $\begingroup$ 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$? $\endgroup$ Sep 20, 2018 at 13:38
  • $\begingroup$ 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). $\endgroup$ Sep 20, 2018 at 14:09

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.