$\lim_{n\to\infty} \frac{\text {No. of elements of order 2 in }S_n}{\text {No. of elements of order 2 in} A_n}=?$

Question

If $\alpha \in S_n$ be an element of order $2$ then $\alpha$ is product of disjoint cycles of lenght $2$.Moreover if $\alpha \in A_n$ then the number of two cycles is even.From this the no. of elements of order $2$ in $S_n$ and $A_n$ can be calculated.If $a_n$ and $b_n$ be the no. of elements of order $2$ in $S_n$ and $A_n$ respectively then it can be shown that $$a_n=\sum_{m=1}^{\lfloor n/2 \rfloor} \frac {n!}{2^m(n-2m)!}$$ and $$b_n=\sum_{m=1}^{\lfloor n/4 \rfloor} \frac {n!}{2^{2m}(n-4m)!}.$$ Now my question is what is $$\lim_{n\to\infty} \frac{a_n}{b_n}?$$

I have taken the values $n$ from $1$ to $20$ which suggest that this limit is $2$ but can't approach this analytically. Please help so solve this.

Answer 1

It seems to me that you're missing a factor in your denominators. The number of ways to choose $m$ disjoint unordered pairs out of $n$ elements ought to be $$ F_n(m) = \frac{n!}{(n-2m)! 2^m m!}$$ where the $m!$ corrects for the fact that we don't care which order the $m$ pairs are selected in.

But the precise shape of this formula is not ultimately important. What is important is that

1. For a fixed $n$, as $m$ goes from $0$ to $\frac12n$, the term $F_n(m)$ first increases monotonically towards a maximum, and then decreases monotonically from it. In fancier words, $F_n$ is unimodal.
2. The peak at that maximum is broad, and becomes broader (in terms of how many different $m$ values it spans) the larger $n$ is.

When this is the case it will always be true that the difference between the sum of the odd positions and the sum of the even positions is small relative to the sum of everything. More precisely, this difference is at most equal to the maximal value of $F_n(m)$, and because the peak is broad, and gets broader the larger $n$ is, as $n\to\infty$ the difference will be a progressively smaller fraction of the entire sum.

Instead of evaluating $F_n(m)$ explicitly, let us just consider how it varies locally: $$ \frac{F_n(m)}{F_n(m-1)} = \frac{\binom{n-2m+2}{2}}{m} = \frac{4 m^2 - (4 n+6 )m + (n^2 + 3 n + 2)}{2 m} $$ because if we have a set of $m-1$ pairs, there are $\binom{n-2m+2}{2}$ ways to extend it with another pair, but each of the resulting sets of $m$ pairs gets counted $m$ times.

We can find the peak by setting this fraction equal to $1$ and solving: $$ 4 m^2 - (4 n+6 )m + (n^2 + 3 n + 2) = 2 m \\ m^2 - (n+2)m + \frac{n^2 + 3 n + 2}4 = 0 \\ m = \frac{n+2 \pm\sqrt{(n+2)^2 - (n^2+3n+2)}}{2} = \frac{n+2 \pm\sqrt{n+2}}2 $$ Only one of these roots is in the interval $[0,\frac n2]$, so $F_n(m)/F_n(m-1)$ is larger than $1$ left of the root and smaller right of it -- that is, $F_n$ is unimodal, as claimed.

Also, as $n$ gets large, the peak is pretty close to $\frac n2-\frac12\sqrt n$, so if we cheat a bit and consider "distance to the closest endpoint of the domain" as a proxy for "width of the peak", we can see that the peak does indeed increase in width as $n$ gets larger -- which is all we needed to know.

---

If we want to be less cheaty, we could estimate the derivative of $F_n(m)/F_n(m-1)$ with respect to $m$ at the location of the peak, and see that it goes to $0$ as $n\to \infty$; if my napkin calculations are right, it will go roughly as $-4n^{-1/2}$. This can then be turned into a more rigorous argument that the peak -- defined as, say, the width of the range of $m$s where $F_n(m)$ is at least half of its maximum value for the particular $n$ -- will get wider as $n$ increases.