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$
  • $\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$ – Richard Stanley Sep 19 '18 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$ – neverevernever Sep 20 '18 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$ – neverevernever Sep 20 '18 at 2:59
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$
  • $\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$ – neverevernever Sep 20 '18 at 3:37
  • 1
    $\begingroup$ @neverevernever: No, $85 = c(6,6-2) > (6/\sqrt{4})^4 = 81$. $\endgroup$ – Max Alekseyev Sep 20 '18 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$ – neverevernever Sep 20 '18 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$ – Max Alekseyev Sep 20 '18 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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