Permutations with a cycle $>\frac{n}{2}$ 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.

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}$$
