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.
 A: 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}$$
A: This answer is to provide additional insight through the use of generating function techniques. As we shall see the result may be derived using some classic algebraic manipulations that are familiar to anyone working with permutations.
First, start with the exponential generating function $G(z, u)$ of the class $\mathcal{P}$ of permutations according to size where cycles of length more than $n/2$ are marked with the variable $u$:
$$G(z, u) = \exp\left(u \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} +
\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{z^k}{k} \right).$$
There can only be one cycle of length more than $\frac{n}{2}$, hence the answer to the question is given by
$$n! [u z^n] G(z, u) = n! [z^n]
\exp\left(\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{z^k}{k}\right)
\sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} $$ or $$
n! [z^n] \exp\left(\log \frac{1}{1-z} 
- \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right)
\sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k}$$
which is
$$n! [z^n] \frac{1}{1-z}
\exp\left( - \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right)
\sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty \frac{z^k}{k} =
n! [z^n] \frac{1}{1-z} \sum_{m=0}^\infty \frac{(-1)^m}{m!} 
\left( \sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k}\right)^{m+1}$$
The exponent of $z$ in the term being raised to the power $m+1$ is larger than $\lfloor\frac{n}{2} \rfloor $ and hence no value for $m>0$ can possibly contribute to $[z^n].$
It follows that the answer is
$$n![z^n] \frac{1}{1-z}\sum_{k>\lfloor\frac{n}{2}\rfloor}^\infty\frac{z^k}{k} =
n! \sum_{k=\lfloor\frac{n}{2}\rfloor +1}^n \frac{1}{k}.$$
The sum has an alternate representation that one encounters e.g. in the OEIS.
$$ \sum_{k=1}^n \frac{1}{k} - \sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{1}{k} =
\sum_{k=1}^n \frac{1}{k} - 2\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} \frac{1}{2k} =
\sum_{k=1\atop k\; \text{even}}^n (1-2) \frac{1}{k}
+ \sum_{k=1\atop k \;\text{odd}}^n  \frac{1}{k} $$
finally giving $$ n!\sum_{k=1}^n \frac{(-1)^{k+1}}{k} \sim n! \log 2.$$
While these ideas have been around for some time, the formalism used is essentially due to P. Flajolet. There is more at INRIA.
A: Take all the $n!$ permutations of $n$ elements. If we take a cycle of length $r > \frac{n}{2}$, there are $\binom{n}{r}$ ways of selecting the elements of the cycle, and they can be arranged in $(r - 1)!$ different cycles (pick any element as first, the others get $(r - 1)!$ orders; now glue the first to the last for a cycle). The other $n - r$ elements can be arranged in $(n - r)!$ ways. Pulling everything together:
$$
\binom{n}{r} \cdot (r - 1)! \cdot (n - r)! = \frac{n!}{r}
$$
Now we need to add over $r > \frac{n}{2}$:
$$
\sum_{\frac{n}{2} < r \le n} \frac{n!}{r} = n! \left( H_n - H_{\frac{n}{2}} \right)
$$
(the $H_k$ are harmonic numbers, it is known that $H_k = \ln k + \gamma + O(1/n)$, so this turns out approximately $n! \ln 2$).
