[Math] Permutations with a cycle $>\frac{n}{2}$

Question

I'm interested in the following question:

Let $S_n$ be the set of all permutations over $\{1,…,n\}$. We know that $|S_n|=n!$.

How many permutations of this set has a cycle larger than $\frac{n}{2}$?

Thanks

PS – not hw.

Answer 1

All permutations can be written as a product of disjoint cycles. Let $\sigma$ be a permutation that has a cycle of length greater than $n/2$. Clearly, $\sigma$ has exactly one such cycle. Let the longest in cycle $\sigma$ be $(a_1,a_2,...,a_k$). Now think of $\sigma$ restricted to $\{1,2,...,n\}-\{a_1,a_2,...,a_k\}$. Restricting $\sigma$ to this set yields a permutation of the set $\{1,2,...,n\}-\{a_1,a_2,...,a_k\}$.

The number of ways to select the subset $\{a_1,a_2,...,a_k\}$ is: $$\binom{n}{k}$$

The number of ways to select distinct cycles $(a_1,a_2,...,a_k)$ is:$$(k-1)!$$ The number of ways to choose the restricted $\sigma$ is : $$(n-k)!$$ Thus the total number of ways is: $$\sum_{k>\frac{n}{2}}\binom{n}{k}(k-1)!(n-k)!$$ $$n!\sum_{k>\frac{n}{2}}\frac{1}{k}$$