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.

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.
